A390863 The number of integers k from 1 to n such that gcd(n, k) is an infinitary divisor of n.

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

Offset

1,2

Links

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

Formula

Multiplicative with a(p^e) = 1 + (p-1) * Sum_{k=1..e} [bitand(k, e) == k] * p^(k-1), where [] is the Iverson bracket, and bitand is the bitwise AND function (A004198).

For example, for a prime p, a(p) = p, a(p^2) = p^2 - p + 1, a(p^3) = p^3, a(p^4) = p^4 - p^3 + 1, ...

a(n) = n - A390864(n).

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

a(n) = n if and only if n is squarefree (A005117).

a(n) = A055653(n) if and only if n is in A138302.

Mathematica

f[p_, e_] := 1 + (p-1) * Total[p^(Select[Range[e], BitAnd[#, e] == # &] - 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~, 1 + (f[i, 1]-1) * sum(k=1, f[i, 2], if(bitand(k, f[i, 2]) == k, f[i, 1]^(k-1)))); }

Crossrefs

Cf. A000010 (phi), A004198, A005117, A077609, A138302.

The number of integers k from 1 to n such that gcd(n, k) is a divisor of n of type: A003557 (coreful), A055653 (unitary), A055654 (nonunitary), A010848 (non-coreful), this sequence (infinitary), A390864 (noninfinitary), A390865 (exponential), A390866 (nonexponential), A390867 (bi-unitary), A390868 (non-bi-unitary).

Sequence in context: A239904 A384041 A384048 * A390867 A384054 A334819

Adjacent sequences: A390860 A390861 A390862 * A390864 A390865 A390866

Keyword

nonn,mult,easy

Author

Amiram Eldar, Nov 22 2025

Status

approved