|
| |
|
|
A116512
|
|
a(n) = number of positive integers each of which is <= n and is divisible by exactly one prime dividing n (but is coprime to every other prime dividing n). a(1) = 0.
|
|
5
|
|
|
|
0, 1, 1, 2, 1, 3, 1, 4, 3, 5, 1, 6, 1, 7, 6, 8, 1, 9, 1, 10, 8, 11, 1, 12, 5, 13, 9, 14, 1, 14, 1, 16, 12, 17, 10, 18, 1, 19, 14, 20, 1, 20, 1, 22, 18, 23, 1, 24, 7, 25, 18, 26, 1, 27, 14, 28, 20, 29, 1, 28, 1, 31, 24, 32, 16, 32, 1, 34, 24, 34, 1, 36, 1, 37, 30, 38, 16, 38, 1, 40, 27, 41, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
a(n) = number of m's, 1 <= m <= n, where gcd(m,n) is a power of a prime (> 1).
We could also have taken a(1) = 1, but a(1) = 0 is better since there are no numbers <= 1 with the desired property. - N. J. A. Sloane, Sep 16 2006
|
|
|
LINKS
|
|
|
|
FORMULA
|
Dirichlet g.f.: A(s)*zeta(s-1)/zeta(s) where A(s) is the Dirichlet g.f. for A069513. - Geoffrey Critzer, Feb 22 2015
a(n) = Sum_{d|n, d is a prime power} phi(n/d), where phi(k) is the Euler totient function. - Daniel Suteu, Jun 27 2018
a(n) = phi(n)*Sum_{p|n} 1/(p-1), where p is a prime and phi(k) is the Euler totient function. - Ridouane Oudra, Apr 29 2019
a(n) = Sum_{k=1..n, gcd(n,k) = 1} omega(gcd(n,k-1)). - Ilya Gutkovskiy, Sep 26 2021
a(n) = Sum_{p|n, p prime} p^(v(n,p)-1)*phi(n/p^v(n,p)), where p^v(n,p) is the highest power of p dividing n. - Ridouane Oudra, Oct 06 2023
|
|
|
EXAMPLE
|
12 is divisible by 2 and 3. The positive integers which are <= 12 and which are divisible by 2 or 3, but not by both 2 and 3, are: 2,3,4,8,9,10. Since there are six such integers, a(12) = 6.
|
|
|
MAPLE
|
with(numtheory): a:=proc(n) local c, j: c:=0: for j from 1 to n do if nops(factorset(gcd(j, n)))=1 then c:=c+1 else c:=c: fi od: c; end: seq(a(n), n=1..90); # Emeric Deutsch, Apr 01 2006
|
|
|
MATHEMATICA
|
Table[Length@Select[GCD[n, Range@n], MatchQ[FactorInteger@#, {{_, _}}] && # != 1 &], {n, 93}] (* Giovanni Resta, Apr 04 2006; corrected by Ilya Gutkovskiy, Sep 26 2021 *)
|
|
|
PROG
|
(PARI) { for(n=1, 60, hav=0; for(i=1, n, g = gcd(i, n); d = factor(g); dec=matsize(d); if( dec[1] == 1, hav++; ); ); print1(hav, ", "); ); } \\ R. J. Mathar, Mar 29 2006
(PARI) a(n) = sumdiv(n, d, eulerphi(n/d) * (isprimepower(d) >= 1)); \\ Daniel Suteu, Jun 27 2018
|
|
|
CROSSREFS
|
Cf. A095112 (Inverse Möbius transform), A354109 (positions of even terms).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
