login
A015634
Number of ordered quadruples of integers from [ 1..n ] with no global factor.
7
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
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.
Sequence in context: A212247 A213801 A301886 * A266891 A241399 A264536
KEYWORD
nonn
STATUS
approved