A384042 The number of integers k from 1 to n such that gcd(n,k) is a 5-rough number (A007310).

1, 1, 2, 2, 5, 2, 7, 4, 6, 5, 11, 4, 13, 7, 10, 8, 17, 6, 19, 10, 14, 11, 23, 8, 25, 13, 18, 14, 29, 10, 31, 16, 22, 17, 35, 12, 37, 19, 26, 20, 41, 14, 43, 22, 30, 23, 47, 16, 49, 25, 34, 26, 53, 18, 55, 28, 38, 29, 59, 20, 61, 31, 42, 32, 65, 22, 67, 34, 46

Offset: 1

Author

Amiram Eldar, May 18 2025

Keywords

• nonn
• easy
• mult

Links

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

Crossrefs

Cf. A000010, A003586, A007310, A065330, A065331, A372671.

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), A384040 (cubefull), A384041 (exponentially odd), this sequence (5-rough).

Programs

Mathematica

f[p_, e_] := If[p < 5, (p-1)*p^(e-1), p^e]; 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,1] < 5, (f[i,1]-1)*f[i,1]^(f[i,2]-1), f[i,1]^f[i,2]));}

Formula

Multiplicative with a(p^e) = (p-1)*p^(e-1) if p <= 3 and p^e if p >= 5.

a(n) >= A000010(n), with equality if and only if n is 3-smooth (A003586).

a(n) = A000010(A065331(n)) * A065330(n).

a(n) = 2 * n * phi(n)/phi(6*n) = n * A000010(n) / A372671(n).

Dirichlet g.f.: zeta(s-1) * (1-1/2^s) * (1-1/3^s).

Sum_{k=1..n} a(k) ~ n^2 / 3.