cp's OEIS Frontend

A025478 Least roots of perfect powers (A001597).

%I A025478 #31 Sep 07 2024 08:53:34
%S A025478 1,2,2,3,2,5,3,2,6,7,2,3,10,11,5,2,12,13,14,6,15,3,2,17,18,7,19,20,21,
%T A025478 22,2,23,24,5,26,3,28,29,30,31,10,2,33,34,35,6,11,37,38,39,40,41,12,
%U A025478 42,43,44,45,2,46,3,13,47,48,7,50,51,52,14,53,54,55,5,56,57,58,15,59,60,61,62
%N A025478 Least roots of perfect powers (A001597).
%H A025478 Daniel Forgues, <a href="/A025478/b025478.txt">Table of n, a(n) for n=1..10000</a>
%F A025478 a(n) = A052410(A001597(n)).
%F A025478 (i) a(n) < n for n > 2. (ii) a(n)/n is bounded and lim sup a(n)/n must be around 0.7. (iii) Sum_{k=1..n} a(k) seems to be asymptotic to c*n^2 with c around 0.29. (iv) a(n) = 2 if n is in A070228 (proof seems self-evident), hence there is no asymptotic expression for a(n) (just the average in (iii)). - _Benoit Cloitre_, Oct 14 2002
%e A025478 a(5) = 2 because pp(5) = 16 = 2^4 (not 4^2 as we take the smallest base).
%t A025478 pp = Select[ Range[5000], Apply[GCD, Last[ Transpose[ FactorInteger[ # ]]]] > 1 &]; f[n_] := Block[{b = 2}, While[ !IntegerQ[ Log[b, pp[[n]]]], b++ ]; b]; Join[{1}, Table[ f[n], {n, 2, 80}]]
%t A025478 (* Second program: *)
%t A025478 Prepend[DeleteCases[#, 0], 1] &@ Table[If[Set[e, GCD @@ #[[All, -1]]] > 1, Power[n, 1/e], 0] &@ FactorInteger@ n, {n, 4000}]  (* _Michael De Vlieger_, Apr 25 2017 *)
%o A025478 (Haskell)
%o A025478 a025478 n = a025478_list !! (n-1)  -- a025478_list defined in A001597.
%o A025478 -- _Reinhard Zumkeller_, Mar 11 2014
%o A025478 (Python)
%o A025478 from math import gcd
%o A025478 from sympy import mobius, integer_nthroot, factorint
%o A025478 def A025478(n):
%o A025478     if n == 1: return 1
%o A025478     def f(x): return int(n-2+x+sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))
%o A025478     kmin, kmax = 1,2
%o A025478     while f(kmax) >= kmax:
%o A025478         kmax <<= 1
%o A025478     while True:
%o A025478         kmid = kmax+kmin>>1
%o A025478         if f(kmid) < kmid:
%o A025478             kmax = kmid
%o A025478         else:
%o A025478             kmin = kmid
%o A025478         if kmax-kmin <= 1:
%o A025478             break
%o A025478     return integer_nthroot(kmax, gcd(*factorint(kmax).values()))[0] # _Chai Wah Wu_, Aug 13 2024
%o A025478 (PARI) lista(kmax) = {my(r, e); print1(1, ", "); for(k = 1, kmax, e = ispower(k, , &r); if(e > 0, print1(r, ", ")));} \\ _Amiram Eldar_, Sep 07 2024
%Y A025478 Cf. A052410 (least root), A001597 (perfect powers).
%Y A025478 Cf. A025479 (largest exponents of perfect powers), A070228.
%K A025478 easy,nonn
%O A025478 1,2
%A A025478 _David W. Wilson_
%E A025478 Definition edited and cross-reference added by _Daniel Forgues_, Mar 10 2009