A385199 The number of integers k from 1 to n such that the greatest divisor of k that is either 1 or a prime power (A000961).

1, 2, 3, 4, 5, 5, 7, 8, 9, 9, 11, 11, 13, 13, 14, 16, 17, 17, 19, 19, 20, 21, 23, 23, 25, 25, 27, 27, 29, 22, 31, 32, 32, 33, 34, 35, 37, 37, 38, 39, 41, 32, 43, 43, 44, 45, 47, 47, 49, 49, 50, 51, 53, 53, 54, 55, 56, 57, 59, 50, 61, 61, 62, 64, 64, 52, 67, 67

Offset

1,2

Links

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

Formula

The unitary convolution of A047994 (the unitary totient phi) with A010055 (the characteristic function of 1 and prime powers): a(n) = Sum_{d | n, gcd(d, n/d) == 1} A047994(d) * A010055(n/d).

a(n) = uphi(n) * (1 + Sum_{p^e || n} (1/(p^e-1))), where uphi = A047994, and p^e || n denotes that the prime power p^e unitarily divides n (i.e., p^e divides n but p^(e+1) does not divide n).

a(n) = A385198(n) + A047994(n).

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = c1 * c2 = 0.96700643911290683406......, c1 = Product_{p prime}(1 - 1/(p*(p+1))) = A065463, and c2 = (1 + Sum_{p prime}(1/(p^2+p-1))) = 1.37272644617447080939... .

Example

For n = 6, the greatest divisor of k that is a unitary divisor of 6 for k = 1 to 6 is 1, 2, 3, 2, 1 and 6, respectively. 5 of the values are either 1 or a prime power, and therefore a(6) = 5.

Mathematica

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

Prog

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

Crossrefs

The unitary analog of A131233.

Cf. A000961, A010055, A065463, A077610, A384047.

The number of integers k from 1 to n such that the greatest divisor of k that is a unitary divisor of n is: A047994 (1), A384048 (squarefree), A384049 (cubefree), A384050 (powerful), A384051 (cubefull), A384052 (square), A384053 (cube), A384054 (exponentially odd), A384055 (odd), A384056 (power of 2), A384057 (3-smooth), A384058 (5-rough), A385195 (1 or 2), A385196 (prime), A385197 (noncomposite), A385198 (prime power), this sequence (1 or prime power).

Sequence in context: A131233 A136623 A031218 * A357004 A357005 A267508

Adjacent sequences: A385196 A385197 A385198 * A385200 A385201 A385202

Keyword

nonn,easy

Author

Amiram Eldar, Jun 21 2025

Status

approved