A384040 The number of integers k from 1 to n such that gcd(n,k) is a cubefull number.

1, 1, 2, 2, 4, 2, 6, 5, 6, 4, 10, 4, 12, 6, 8, 10, 16, 6, 18, 8, 12, 10, 22, 10, 20, 12, 19, 12, 28, 8, 30, 20, 20, 16, 24, 12, 36, 18, 24, 20, 40, 12, 42, 20, 24, 22, 46, 20, 42, 20, 32, 24, 52, 19, 40, 30, 36, 28, 58, 16, 60, 30, 36, 40, 48, 20, 66, 32, 44, 24

Offset: 1

Author

Amiram Eldar, May 18 2025

Keywords

• nonn
• easy
• mult

Comments

The number of integers k from 1 to n such that the cubefree part (A360539) of gcd(n,k) is 1.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A005117, A036966, A078429, A360539, A254926.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), A384039 (powerful), this sequence (cubefull), A384041 (exponentially odd), A384042 (5-rough).

Programs

Mathematica

f[p_, e_] := Switch[e, 1, p-1, 2, p^2-p, , (p^3-p^2+1)*p^(e-3)]; a[1] = 1; a[n] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

PARI

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,2] == 1, f[i,1]-1, if(f[i,2] == 2, f[i,1]*(f[i,1]-1), (f[i,1]^3-f[i,1]^2+1)*f[i,1]^(f[i,2]-3))));}

Formula

Multiplicative with a(p^e) = (p^3-p^2+1)*p^(e-3) if e >= 3, p*(p-1) if e = 2, and p-1 otherwise.

a(n) >= A384039(n), with equality if and only if n is squarefree (A005117).

Dirichlet g.f.: zeta(s-1) * Product_{p prime} (1 - 1/p^s + 1/p^(3*s)).

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/p^6) = 0.62159731307414305346... .