A384041 The number of integers k from 1 to n such that gcd(n,k) is an exponentially odd number.

1, 2, 3, 3, 5, 6, 7, 7, 8, 10, 11, 9, 13, 14, 15, 13, 17, 16, 19, 15, 21, 22, 23, 21, 24, 26, 25, 21, 29, 30, 31, 27, 33, 34, 35, 24, 37, 38, 39, 35, 41, 42, 43, 33, 40, 46, 47, 39, 48, 48, 51, 39, 53, 50, 55, 49, 57, 58, 59, 45, 61, 62, 56, 53, 65, 66, 67, 51

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

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

Programs

Mathematica

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

PARI

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

Formula

Multiplicative with a(p^e) = ((p^2+p-1)*p^(e-1) - (-1)^e)/(p+1).

a(n) >= A000010(n), with equality if and only if n = 1.

Dirichlet g.f.: (zeta(s-1)*zeta(2*s)/zeta(s)) * 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^2+1)) = 0.93749428273130025078... .