|
%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
|
