login
Prime powers with exponents that are themselves prime powers.
3

%I #29 Sep 12 2024 12:46:27

%S 2,3,4,5,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41,43,47,49,53,59,

%T 61,67,71,73,79,81,83,89,97,101,103,107,109,113,121,125,127,128,131,

%U 137,139,149,151,157,163,167,169,173,179,181,191,193,197,199,211,223,227

%N Prime powers with exponents that are themselves prime powers.

%C A000040, A053810, A050376 and A082522 are subsequences;

%C a(n) = A000961(n+1) for 1<=n<=26.

%C Complement of A164345 with respect to A000961.

%H Reinhard Zumkeller, <a href="/A096165/b096165.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) ~ n log n. - _Charles R Greathouse IV_, Oct 19 2015

%e 512=2^9=2^(3^2), A000961(118)=A000040(1)^A000961(118), therefore 512 is a term;

%e 64=2^6, but 6 is not a prime power, therefore 64 is not a term.

%p F:= proc(t) local P;

%p P:= ifactors(t)[2];

%p nops(P) = 1 and (P[1][2]=1 or nops(numtheory:-factorset(P[1][2]))=1)

%p end proc:

%p select(F, [$2..1000]); # _Robert Israel_, Jul 20 2015

%t Select[Range@ 240, Or[PrimeQ@ #, PrimePowerQ@ # && PrimePowerQ@ FactorInteger[#][[1, 2]]] &] (* _Michael De Vlieger_, Jul 20 2015 *)

%o (Haskell)

%o a096165 n = a096165_list !! (n-1)

%o a096165_list = filter ((== 1) . a010055 . a001222) $ tail a000961_list

%o -- _Reinhard Zumkeller_, Nov 17 2011

%o (PARI) is(n)=while(1,if(!(n=isprimepower(n)),return(0),if(n==1,return(1)))) \\ _Anders Hellström_, Jul 19 2015

%o (PARI) ispp(n)=n==1 || isprimepower(n)

%o is(n)=ispp(isprimepower(n)) \\ _Charles R Greathouse IV_, Oct 19 2015

%o (Python)

%o from sympy import primepi, integer_nthroot, factorint

%o def A096165(n):

%o def f(x): return int(n+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length()) if len(factorint(k))<=1))

%o def bisection(f,kmin=0,kmax=1):

%o while f(kmax) > kmax: kmax <<= 1

%o while kmax-kmin > 1:

%o kmid = kmax+kmin>>1

%o if f(kmid) <= kmid:

%o kmax = kmid

%o else:

%o kmin = kmid

%o return kmax

%o return bisection(f,n,n) # _Chai Wah Wu_, Sep 12 2024

%Y Cf. A000040, A000961, A010055, A001222, A050376, A053810, A082522, A164336, A164345.

%K nonn

%O 1,1

%A _Reinhard Zumkeller_, Jul 25 2004