login
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
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).
Sequence in context: A302032 A291326 A291325 * A276836 A291324 A075388
KEYWORD
nonn
AUTHOR
Leroy Quet, Mar 23 2006
EXTENSIONS
More terms from R. J. Mathar, Emeric Deutsch and Giovanni Resta, Apr 01 2006
Edited by N. J. A. Sloane, Sep 16 2006
STATUS
approved