|
|
A069623
|
|
Number of perfect powers <= n.
|
|
9
|
|
|
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
|
|
|
FORMULA
|
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
a(n) = n - Sum_{k=2..n} M(floor(log_k(n))), where M is Mertens's function A002321. - Ridouane Oudra, Dec 30 2020
|
|
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)):
# second Maple program:
a:= proc(n) option remember; `if`(n=1, 1, a(n-1)+
`if`(igcd(seq(i[2], i=ifactors(n)[2]))>1, 1, 0))
end:
|
|
MATHEMATICA
|
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}]
(* 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)=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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|