login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
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 (list; graph; refs; listen; history; text; internal format)
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

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@#, {{_, _}}]&], {n, 93}] (* Giovanni Resta, Apr 04 2006 *)

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. A119790, A119794, A120499.

Sequence in context: A302032 A291326 A291325 * A276836 A291324 A075388

Adjacent sequences:  A116509 A116510 A116511 * A116513 A116514 A116515

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 11 21:35 EDT 2021. Contains 343808 sequences. (Running on oeis4.)