This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A069623 Number of perfect powers <= n. 8
 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, 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, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 LINKS Robert Israel, Table of n, a(n) for n = 1..10000 M. A. Nyblom, A Counting Function for the Sequence of Perfect Powers, Austral. Math. Soc. Gaz. 33 (2006), 338-343. Stackexchange, Proof of formula of number of Power <=n, Jun 24 2013 Eric Weisstein's World of Mathematics, Perfect Powers. FORMULA 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 a(n) = O(sqrt(n)) (conjectured). a(n) = A076411(n+1) = Sum_{k=1..n} A075802(k). - Chayim Lowen, Jul 24 2015 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 EXAMPLE a(27) = 7 as the perfect powers <= 27 are 1, 4, 8, 9, 16, 25 and 27. MAPLE N:= 1000:  # to get a(n) for n <= N R:= Vector(N): for p from 2 to ilog2(N) do   for i from 1 to floor(N^(1/p)) do       R[i^p]:= 1 od od: A069623:= map(round, Statistics:-CumulativeSum(R)): convert(A069623, list); # Robert Israel, May 19 2014 # second Maple program: a:= proc(n) option remember; `if`(n=1, 1, a(n-1)+      `if`(igcd(seq(i, i=ifactors(n)))>1, 1, 0))     end: seq(a(n), n=1..100);  # Alois P. Heinz, Feb 26 2019 MATHEMATICA a = 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}] (* Or *) b[n_] := n - Sum[ MoebiusMu[k] * Floor[n^(1/k) - 1], {k, 1, Floor[ Log[2, n]]}]; Table[b[n], {n, 1, 85}] PROG (PARI) a(n) = 1 + sum(k=1, n, ispower(k) != 0); \\ Michel Marcus, Jul 25 2015 (PARI) a(n)=n-sum(k=1, logint(n, 2), moebius(k)*(sqrtnint(n, k)-1)) \\ Charles R Greathouse IV, Jul 21 2017 (PARI) a(n)=my(s=n); forsquarefree(k=1, logint(n, 2), s-=(sqrtnint(n, k)-1)*moebius(k)); s \\ Charles R Greathouse IV, Jan 08 2018 CROSSREFS Perfect powers are A001597. Cf. A053289. A076411(n) = a(n-1) is another version. Cf. A075802 (first differences). - Chayim Lowen, Jul 29 2015 Sequence in context: A025425 A234451 A085501 * A076411 A217038 A309196 Adjacent sequences:  A069620 A069621 A069622 * A069624 A069625 A069626 KEYWORD nonn,easy AUTHOR Amarnath Murthy, Mar 27 2002 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.

Last modified September 18 09:52 EDT 2019. Contains 327168 sequences. (Running on oeis4.)