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

Alois P. Heinz, Table of n, a(n) for n = 1..10000

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

KEYWORD

nonn

AUTHOR

Leroy Quet, Mar 23 2006

EXTENSIONS

Edited by N. J. A. Sloane, Sep 16 2006

STATUS

approved