cp's OEIS Frontend

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

%I A139555 #22 Jun 20 2018 01:35:41
%S A139555 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,
%T A139555 17,14,15,13,16,11,19,14,16,13,20,12,21,16,17,16,22,15,22,17,20,18,24,
%U A139555 17,22,18,21,19,25,16,26,21,22,22,25,18,28,22,25,19,29,21,30,24,26,24
%N A139555 a(n) = number of prime-powers (including 1) that each are <= n and are coprime to n.
%C A139555 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_
%C A139555 From _Reinhard Zumkeller_, Oct 27 2010: (Start)
%C A139555 a(n) <= A000010(n); a(A051250(n)) = A000010(A051250(n)), 1 <= n <= 17;
%C A139555 conjecture: a(n) < A000010(n) for n > 60, cf. A051250. (End)
%H A139555 R. Zumkeller, <a href="/A139555/b139555.txt">Table of n, a(n) for n = 1..1000</a>
%F A139555 a(n) = Sum_{k=1..A000010(n)} A010055(A038566(n,k)). - _Reinhard Zumkeller_, Feb 23 2012
%e A139555 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.
%p A139555 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
%t A139555 f[n_] := Length@ Select[Range@ n, Length@ FactorInteger@ # == 1 == GCD[n, # ] &]; Array[f, 76] (* _Robert G. Wilson v_ *)
%o A139555 (Haskell)
%o A139555 a139555 = sum . map a010055 . a038566_row
%o A139555 -- _Reinhard Zumkeller_, Feb 23 2012, Oct 27 2010
%Y A139555 Cf. A139556.
%Y A139555 Cf. A065515. - _Reinhard Zumkeller_, Oct 27 2010
%K A139555 nonn
%O A139555 1,3
%A A139555 _Leroy Quet_, Apr 27 2008
%E A139555 More terms from _R. J. Mathar_ and _Robert G. Wilson v_, May 12 2008