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

Links

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

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

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]

Prog

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

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

Sequence in context: A070321 A378363 A239904 * A384048 A390863 A390867

Adjacent sequences: A384038 A384039 A384040 * A384042 A384043 A384044

Keyword

nonn,easy,mult

Author

Amiram Eldar, May 18 2025

Status

approved