A081676 Largest perfect power <= n.

1, 1, 1, 4, 4, 4, 4, 8, 9, 9, 9, 9, 9, 9, 9, 16, 16, 16, 16, 16, 16, 16, 16, 16, 25, 25, 27, 27, 27, 27, 27, 32, 32, 32, 32, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64

Offset: 1

Author

Reinhard Zumkeller, Mar 26 2003

Keywords

• nonn
• changed

Comments

a(n) = n if n is in A001597, otherwise a(n) = a(n-1). - Robert Israel, Dec 17 2015

Links

• Neven Sajko, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A001597, A069584, A069623.

Programs

Maple

N:= 1000: # to get a(1) to a(N).
Powers:= {1,seq(seq(b^p, p=2..floor(log[b](N))),b=2..isqrt(N))}:
Powers:= sort(convert(Powers,list)):
j:= 1:
for i from 1 to N do
  if i >= Powers[j+1] then j:= j+1 fi;
  A[i]:= Powers[j];
od:
seq(A[i],i=1..N); # Robert Israel, Dec 17 2015

Mathematica

Array[SelectFirst[Range[#, 1, -1], Or[And[! PrimeQ@ #, GCD @@ FactorInteger[#][[All, -1]] > 1], # == 1] &] &, 72] (* Michael De Vlieger, Jun 14 2017 *)

PARI

a(n) = {while(!ispower(n), n--; if (n==0, return (1))); n;} \\ Michel Marcus, Nov 04 2015

Python

from sympy import mobius, integer_nthroot
def A081676(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(x-1+sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
    m = n-f(n)
    return bisection(lambda x:f(x)+m,m-1,n+1) # Chai Wah Wu, Nov 05 2024

Sage

p = [i for i in (1..81) if i.is_perfect_power()]
r = [[p[i]]*(p[i+1]-p[i]) for i in (0..10)]
print([y for x in r for y in x]) # Peter Luschny, Jun 13 2017

Formula

a(n) = n - A069584(n).

a(n) = A001597(A069623(n)). - Ridouane Oudra, Aug 26 2025