Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #48 Nov 24 2023 08:08:40
%S 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,
%T 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,
%U 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
%N 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.
%C a(n) = number of m's, 1 <= m <= n, where gcd(m,n) is a power of a prime (> 1).
%C 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
%H Alois P. Heinz, <a href="/A116512/b116512.txt">Table of n, a(n) for n = 1..10000</a>
%F 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
%F 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
%F 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
%F a(n) = Sum_{k=1..n, gcd(n,k) = 1} omega(gcd(n,k-1)). - _Ilya Gutkovskiy_, Sep 26 2021
%F 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
%e 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.
%p 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
%t Table[Length@Select[GCD[n, Range@n], MatchQ[FactorInteger@#, {{_, _}}] && # != 1 &], {n, 93}] (* _Giovanni Resta_, Apr 04 2006; corrected by _Ilya Gutkovskiy_, Sep 26 2021 *)
%o (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
%o (PARI) a(n) = sumdiv(n, d, eulerphi(n/d) * (isprimepower(d) >= 1)); \\ _Daniel Suteu_, Jun 27 2018
%Y Cf. A069513, A119790, A119794, A120499.
%Y Cf. A095112 (Inverse Möbius transform), A354109 (positions of even terms).
%K nonn
%O 1,4
%A _Leroy Quet_, Mar 23 2006
%E More terms from _R. J. Mathar_, _Emeric Deutsch_ and _Giovanni Resta_, Apr 01 2006
%E Edited by _N. J. A. Sloane_, Sep 16 2006