cp's OEIS Frontend

A081676 Largest perfect power <= n.

%I A081676 #42 Aug 26 2025 09:51:51
%S A081676 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,
%T A081676 27,27,27,32,32,32,32,36,36,36,36,36,36,36,36,36,36,36,36,36,49,49,49,
%U A081676 49,49,49,49,49,49,49,49,49,49,49,49,64,64,64,64,64,64,64,64,64,64,64
%N A081676 Largest perfect power <= n.
%C A081676 a(n) = n if n is in A001597, otherwise a(n) = a(n-1). - _Robert Israel_, Dec 17 2015
%H A081676 Neven Sajko, <a href="/A081676/b081676.txt">Table of n, a(n) for n = 1..10000</a>
%F A081676 a(n) = n - A069584(n).
%F A081676 a(n) = A001597(A069623(n)). - _Ridouane Oudra_, Aug 26 2025
%p A081676 N:= 1000: # to get a(1) to a(N).
%p A081676 Powers:= {1,seq(seq(b^p, p=2..floor(log[b](N))),b=2..isqrt(N))}:
%p A081676 Powers:= sort(convert(Powers,list)):
%p A081676 j:= 1:
%p A081676 for i from 1 to N do
%p A081676   if i >= Powers[j+1] then j:= j+1 fi;
%p A081676   A[i]:= Powers[j];
%p A081676 od:
%p A081676 seq(A[i],i=1..N); # _Robert Israel_, Dec 17 2015
%t A081676 Array[SelectFirst[Range[#, 1, -1], Or[And[! PrimeQ@ #, GCD @@ FactorInteger[#][[All, -1]] > 1], # == 1] &] &, 72] (* _Michael De Vlieger_, Jun 14 2017 *)
%o A081676 (PARI) a(n) = {while(!ispower(n), n--; if (n==0, return (1))); n;} \\ _Michel Marcus_, Nov 04 2015
%o A081676 (Sage)
%o A081676 p = [i for i in (1..81) if i.is_perfect_power()]
%o A081676 r = [[p[i]]*(p[i+1]-p[i]) for i in (0..10)]
%o A081676 print([y for x in r for y in x]) # _Peter Luschny_, Jun 13 2017
%o A081676 (Python)
%o A081676 from sympy import mobius, integer_nthroot
%o A081676 def A081676(n):
%o A081676     def bisection(f,kmin=0,kmax=1):
%o A081676         while f(kmax) > kmax: kmax <<= 1
%o A081676         while kmax-kmin > 1:
%o A081676             kmid = kmax+kmin>>1
%o A081676             if f(kmid) <= kmid:
%o A081676                 kmax = kmid
%o A081676             else:
%o A081676                 kmin = kmid
%o A081676         return kmax
%o A081676     def f(x): return int(x-1+sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
%o A081676     m = n-f(n)
%o A081676     return bisection(lambda x:f(x)+m,m-1,n+1) # _Chai Wah Wu_, Nov 05 2024
%Y A081676 Cf. A001597, A069584, A069623.
%K A081676 nonn,changed
%O A081676 1,4
%A A081676 _Reinhard Zumkeller_, Mar 26 2003