cp's OEIS Frontend

A116512 a(n) is the 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.

%I A116512 #56 Jun 21 2025 11:49:42
%S A116512 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 A116512 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 A116512 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 A116512 a(n) is the 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 A116512 a(n) = number of m's, 1 <= m <= n, where gcd(m,n) is a power of a prime (> 1).
%C A116512 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 A116512 Alois P. Heinz, <a href="/A116512/b116512.txt">Table of n, a(n) for n = 1..10000</a>
%F A116512 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 A116512 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 A116512 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 A116512 a(n) = Sum_{k=1..n, gcd(n,k) = 1} omega(gcd(n,k-1)). - _Ilya Gutkovskiy_, Sep 26 2021
%F A116512 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
%F A116512 From _Amiram Eldar_, Jun 21 2025: (Start)
%F A116512 a(n) = A131233(n) - A000010(n).
%F A116512 Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c =  Sum_{p prime} (1/(p^2-1)) / zeta(2) = A154945 / A013661 = 0.3353893075569103736099... . (End)
%e A116512 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 A116512 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 A116512 Table[Length@Select[GCD[n, Range@n], MatchQ[FactorInteger@#, {{_, _}}] && # != 1 &], {n, 93}] (* _Giovanni Resta_, Apr 04 2006; corrected by _Ilya Gutkovskiy_, Sep 26 2021 *)
%t A116512 a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, n * Times @@ (1-1/p) * Total[1/(p-1)]]; a[1] = 0; Array[a, 100] (* _Amiram Eldar_, Jun 21 2025 *)
%o A116512 (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 A116512 (PARI) a(n) = sumdiv(n, d, eulerphi(n/d) * (isprimepower(d) >= 1)); \\ _Daniel Suteu_, Jun 27 2018
%o A116512 (PARI) a(n) = {my(p = factor(n)[,1]); n * vecprod(apply(x -> 1-1/x, p)) * vecsum(apply(x -> 1/(x-1), p));} \\ _Amiram Eldar_, Jun 21 2025
%Y A116512 Cf. A000010, A013661, A069513, A119790, A119794, A120499, A131233, A154945.
%Y A116512 Cf. A095112 (Inverse Möbius transform), A354109 (positions of even terms).
%K A116512 nonn
%O A116512 1,4
%A A116512 _Leroy Quet_, Mar 23 2006
%E A116512 More terms from _R. J. Mathar_, _Emeric Deutsch_ and _Giovanni Resta_, Apr 01 2006
%E A116512 Edited by _N. J. A. Sloane_, Sep 16 2006