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,3

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

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... .

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]

Prog

(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)))); }

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).

Sequence in context: A236628 A390606 A078429 * A360523 A358039 A171751

Adjacent sequences: A384037 A384038 A384039 * A384041 A384042 A384043

Keyword

nonn,easy,mult

Author

Amiram Eldar, May 18 2025

Status

approved