cp's OEIS Frontend

A025476 Prime root of n-th nontrivial prime power (A025475, A246547).

%I A025476 #35 Aug 16 2024 08:37:11
%S A025476 2,2,3,2,5,3,2,7,2,3,11,5,2,13,3,2,17,7,19,2,23,5,3,29,31,2,11,37,41,
%T A025476 43,2,3,13,47,7,53,5,59,61,2,67,17,71,73,79,3,19,83,89,2,97,101,103,
%U A025476 107,109,23,113,11,5,127,2,7,131,137,139,3,149,151,29,157,163,167,13,31,173,179
%N A025476 Prime root of n-th nontrivial prime power (A025475, A246547).
%H A025476 Michael De Vlieger, <a href="/A025476/b025476.txt">Table of n, a(n) for n = 1..10000</a>
%p A025476 cvm := proc(n, level) local f,opf; if n < 2 then RETURN() fi;
%p A025476 f := ifactors(n); opf := op(1,op(2,f)); if nops(op(2,f)) > 1 or
%p A025476 op(2,opf) <= level then RETURN() fi; op(1,opf) end:
%p A025476 A025476_list := n -> seq(cvm(i,1),i=1..n); # n is search limit
%p A025476 A025476_list(30000);  # _Peter Luschny_, Sep 21 2011
%p A025476 # Alternative:
%p A025476 isA246547 := n -> n > 1 and not isprime(n) and type(n, 'primepower'):
%p A025476 seq(ifactors(p)[2][1][1], p in select(isA246547, [$1..30000])); # _Peter Luschny_, Jul 15 2023
%t A025476 Transpose[ Flatten[ FactorInteger[ Select[ Range[2, 30000], !PrimeQ[ # ] && Mod[ #, # - EulerPhi[ # ]] == 0 &]], 1]][[1]] (* _Robert G. Wilson v_ *)
%o A025476 (PARI) forcomposite(n=4,10^5,if( ispower(n, , &p) && isprime(p), print1(p,", "))) \\ _Joerg Arndt_, Sep 11 2021
%o A025476 (Python)
%o A025476 from sympy import primepi, integer_nthroot, primefactors
%o A025476 def A025476(n):
%o A025476     def f(x): return int(n-1+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(2,x.bit_length())))
%o A025476     kmin, kmax = 1,2
%o A025476     while f(kmax) >= kmax:
%o A025476         kmax <<= 1
%o A025476     while True:
%o A025476         kmid = kmax+kmin>>1
%o A025476         if f(kmid) < kmid:
%o A025476             kmax = kmid
%o A025476         else:
%o A025476             kmin = kmid
%o A025476         if kmax-kmin <= 1:
%o A025476             break
%o A025476     return primefactors(kmax)[0] # _Chai Wah Wu_, Aug 15 2024
%Y A025476 Cf. A025473, A025475, A048148, A246547.
%K A025476 easy,nonn
%O A025476 1,1
%A A025476 _David W. Wilson_