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
Examples
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.
Links
- Amiram Eldar, Table of n, a(n) for n = 1..10000
Crossrefs
The unitary analog of A131233.
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).
Programs
-
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] -
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)));}
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).
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... .