A139555 a(n) = number of prime-powers (including 1) that each are <= n and are coprime to n.

1, 1, 2, 2, 4, 2, 5, 4, 6, 4, 8, 4, 9, 6, 7, 7, 11, 6, 12, 8, 10, 8, 13, 8, 13, 10, 13, 11, 16, 8, 17, 14, 15, 13, 16, 11, 19, 14, 16, 13, 20, 12, 21, 16, 17, 16, 22, 15, 22, 17, 20, 18, 24, 17, 22, 18, 21, 19, 25, 16, 26, 21, 22, 22, 25, 18, 28, 22, 25, 19, 29, 21, 30, 24, 26, 24

Offset

1,3

Comments

Indices of first occurrence of each natural number: 1, 3, 5, 7, 9, 15, 11, 13, 21, 17, 19, 23, 32, 33, ..., . - Robert G. Wilson v

From Reinhard Zumkeller, Oct 27 2010: (Start)

a(n) <= A000010(n); a(A051250(n)) = A000010(A051250(n)), 1 <= n <= 17;

conjecture: a(n) < A000010(n) for n > 60, cf. A051250. (End)

Links

R. Zumkeller, Table of n, a(n) for n = 1..1000

Formula

a(n) = Sum_{k=1..A000010(n)} A010055(A038566(n,k)). - Reinhard Zumkeller, Feb 23 2012

Example

All the positive integers <= 21 that are coprime to 21 are 1,2,4,5,8,10,11,13,16,17,19,20. Of these integers, only 1,2,4,5,8,11,13,16,17,19 are prime-powers. There are 10 of these prime-powers; so a(21) = 10.

Maple

isA000961 := proc(n) if n = 1 or isprime(n) then true; else RETURN(nops(ifactors(n)[2]) =1) ; fi ; end: A139555 := proc(n) local a, i; a := 0 ; for i from 1 to n do if isA000961(i) and gcd(i, n) = 1 then a := a+1 ; fi ; od: a ; end: seq(A139555(n), n=1..100) ; # R. J. Mathar, May 12 2008

Mathematica

f[n_] := Length@ Select[Range@ n, Length@ FactorInteger@ # == 1 == GCD[n, # ] &]; Array[f, 76] (* Robert G. Wilson v *)

Prog

(Haskell)
a139555 = sum . map a010055 . a038566_row
-- Reinhard Zumkeller, Feb 23 2012, Oct 27 2010

Crossrefs

Cf. A139556.

Cf. A065515. - Reinhard Zumkeller, Oct 27 2010

Sequence in context: A243271 A232245 A121895 * A241814 A088371 A133181

Adjacent sequences: A139552 A139553 A139554 * A139556 A139557 A139558

Keyword

nonn

Author

Leroy Quet, Apr 27 2008

Extensions

More terms from R. J. Mathar and Robert G. Wilson v, May 12 2008

Status

approved