A015650 Number of ordered 5-tuples of integers from [ 1..n ] with no global factor.

1, 5, 19, 49, 118, 225, 434, 729, 1209, 1850, 2850, 4059, 5878, 8044, 11020, 14566, 19410, 24789, 32103, 40213, 50615, 62260, 77209, 93099, 113504, 135431, 162341, 191396, 227355, 264463, 310838, 359322, 417212, 478408, 551944, 626971, 718360, 812311, 922407, 1036667

Offset: 1

Author

Olivier Gérard

Keywords

• nonn

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000

Crossrefs

Column k=5 of A177976.

Partial sums of A117109.

Cf. A000389, A002088, A013663, A015631, A015634.

Programs

Mathematica

a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#]*Binomial[# + 3, 4] &], {k, 1, n}]; Array[a, 40] (* Amiram Eldar, Jun 07 2025 *)

PARI

a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+3, 4))); \\ Seiichi Manyama, Jun 12 2021

PARI

a(n) = binomial(n+4, 5)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021

PARI

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k/(1-x^k)^5)/(1-x)) \\ Seiichi Manyama, Jun 12 2021

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A015650(n):
    if n == 0:
        return 0
    c, j = n+1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A015650(k1)
        j, k1 = j2, n//j2
    return n*(n+1)*(n+2)*(n+3)*(n+4)//120-c+j # Chai Wah Wu, Apr 18 2021

Formula

G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^5. - Ilya Gutkovskiy, Feb 14 2020

a(n) = n*(n+1)*(n+2)*(n+3)*(n+4)/120 - Sum_{j=2..n} a(floor(n/j)) = A000389(n+4) - Sum_{j=2..n} a(floor(n/j)). - Chai Wah Wu, Apr 18 2021

a(n) ~ n^5 / (120*zeta(5)). - Amiram Eldar, Jun 08 2025