|
%I #52 Mar 07 2021 01:50:09
%S 1,1,1,2,2,2,2,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,6,6,7,7,7,7,7,8,8,8,
%T 8,9,9,9,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,10,10,
%U 10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12
%N Number of perfect powers <= n.
%H Robert Israel, <a href="/A069623/b069623.txt">Table of n, a(n) for n = 1..10000</a>
%H M. A. Nyblom, <a href="http://www.austms.org.au/Publ/Gazette/2006/Nov06/nyblom.pdf">A Counting Function for the Sequence of Perfect Powers</a>, Austral. Math. Soc. Gaz. 33 (2006), 338-343.
%H Stackexchange, <a href="http://math.stackexchange.com/questions/428351/proof-of-formula-of-number-of-power-leq-n">Proof of formula of number of Power <=n</a>, Jun 24 2013
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectPower.html">Perfect Powers</a>.
%F a(n) = n - Sum_{k=1..floor(log_2(n))} mu(k)*[n^(1/k)-1]), where mu = A008683. - _David W. Wilson_, Oct 09 2002
%F a(n) = O(sqrt(n)) (conjectured). a(n) = A076411(n+1) = Sum_{k=1..n} A075802(k). - _Chayim Lowen_, Jul 24 2015
%F The conjecture is true: The number of squares < n is n^(1/2) + O(1). The number of higher powers < n is nonnegative and less than n^(1/3) log_2(n). Thus a(n) = n^(1/2) + O(n^(1/3) log n). - _Robert Israel_, Jul 31 2015
%F a(n) = n - Sum_{k=2..n} M(floor(log_k(n))), where M is Mertens's function A002321. - _Ridouane Oudra_, Dec 30 2020
%e a(27) = 7 as the perfect powers <= 27 are 1, 4, 8, 9, 16, 25 and 27.
%p N:= 1000: # to get a(n) for n <= N
%p R:= Vector(N):
%p for p from 2 to ilog2(N) do
%p for i from 1 to floor(N^(1/p)) do
%p R[i^p]:= 1
%p od od:
%p A069623:= map(round,Statistics:-CumulativeSum(R)):
%p convert(A069623,list); # _Robert Israel_, May 19 2014
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n=1, 1, a(n-1)+
%p `if`(igcd(seq(i[2], i=ifactors(n)[2]))>1, 1, 0))
%p end:
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Feb 26 2019
%t a[1] = 1; a[n_] := If[ !PrimeQ[n] && GCD @@ Last[Transpose[FactorInteger[n]]] > 1, a[n - 1] + 1, a[n - 1]]; Table[a[n], {n, 1, 85}]
%t (* Or *) b[n_] := n - Sum[ MoebiusMu[k] * Floor[n^(1/k) - 1], {k, 1, Floor[ Log[2, n]]}]; Table[b[n], {n, 1, 85}]
%o (PARI) a(n) = 1 + sum(k=1, n, ispower(k) != 0); \\ _Michel Marcus_, Jul 25 2015
%o (PARI) a(n)=n-sum(k=1,logint(n,2), moebius(k)*(sqrtnint(n,k)-1)) \\ _Charles R Greathouse IV_, Jul 21 2017
%o (PARI) a(n)=my(s=n); forsquarefree(k=1,logint(n,2), s-=(sqrtnint(n,k[1])-1)*moebius(k)); s \\ _Charles R Greathouse IV_, Jan 08 2018
%Y Perfect powers are A001597. Cf. A053289. A076411(n) = a(n-1) is another version.
%Y Cf. A075802 (first differences). - _Chayim Lowen_, Jul 29 2015
%Y Cf. A002321.
%K nonn,easy
%O 1,4
%A _Amarnath Murthy_, Mar 27 2002
|
