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

Author

Leroy Quet, Apr 27 2008

Keywords

• nonn

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)

Examples

			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.
		

Links

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

Crossrefs

Cf. A139556.

Cf. A065515. - Reinhard Zumkeller, Oct 27 2010

Programs

Haskell

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

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 *)

Formula

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

Extensions

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