A015634 Number of ordered quadruples of integers from [ 1..n ] with no global factor.

1, 4, 13, 29, 63, 106, 189, 289, 444, 626, 911, 1203, 1657, 2130, 2766, 3462, 4430, 5359, 6688, 7992, 9670, 11405, 13704, 15840, 18730, 21548, 25037, 28521, 33015, 37067, 42522, 47690, 53940, 60108, 67760, 74748, 83886, 92433, 102629, 112469

Offset

1,2

Links

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

Formula

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

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

Prog

(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A015634(n):
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A015634(k1)
        j, k1 = j2, n//j2
    return n*(n+1)*(n+2)*(n+3)//24-c+j-n # Chai Wah Wu, Apr 18 2021
(PARI) a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+2, 3))); \\ Seiichi Manyama, Jun 12 2021
(PARI) a(n) = binomial(n+3, 4)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021
(PARI) my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k/(1-x^k)^4)/(1-x)) \\ Seiichi Manyama, Jun 12 2021

Crossrefs

Column k=4 of A177976.

Cf. A000332, A002088, A015631, A015650, A117108.

Sequence in context: A212247 A213801 A301886 * A266891 A241399 A264536

Adjacent sequences: A015631 A015632 A015633 * A015635 A015636 A015637

Keyword

nonn

Author

Olivier Gérard

Status

approved