A088247 Orders of proper semifields.

16, 27, 32, 64, 81, 125, 128, 243, 256, 343, 512, 625, 729, 1024, 1331, 2048, 2187, 2197, 2401, 3125, 4096, 4913, 6561, 6859, 8192, 12167, 14641, 15625, 16384, 16807, 19683, 24389, 28561, 29791, 32768, 50653, 59049, 65536, 68921, 78125, 79507

Offset: 1

Author

Marc LeBrun, Sep 25 2003

Keywords

• nonn
• easy
• nice

Comments

Subset of prime powers A000961. Superset of orders of twisted fields A088248.

Prime powers p^e > 8 with e > 2, thus excluding the primes, the semiprimes, unity and 8. Robert G. Wilson v, Mar 11 2014

References

• D. E. Knuth, "Finite Semifields and Projective Planes", Selected Papers on Discrete Mathematics, Center for the Study of Language and Information, Leland Stanford Junior University, CA, 2003, p. 335.

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
• Hauke Klein, Semifields, provides definition, context, links, theorem.
• D. E. Knuth, Finite semifields and projective planes, Caltech PhD dissertation, library online PDF version.

Crossrefs

Cf. A000961, A088248.

Programs

Mathematica

max = 10^5; Clear[f]; f[2] = {}; p = Prime /@ Range[PrimePi[max^(1/3) // N]]; f[k_] := f[k] = Select[Union[f[k-1], p^k], # < max &]; f[k = 3]; While[f[k] != f[k-1], k++]; f[k] // Rest (* Jean-François Alcover, Sep 26 2013 *)
Select[ Range[ 9, 80000 ], PrimeOmega@# > 2 && Mod[ #, # - EulerPhi@# ] == 0 & ] (* or *) mx = 80000; Rest@ Sort@ Flatten@ Table[ Prime[n]^e, {n, PrimePi[ mx^(1/3)]}, {e, 3, Log[ Prime@ n, mx]}] (* Robert G. Wilson v, Mar 11 2014 *)

PARI

is(n)=isprimepower(n)>2 && n>8 \\ Charles R Greathouse IV, Mar 11 2014

Python

from math import isqrt
from sympy import primerange, integer_nthroot, primepi
def A088247(n):
    def g(x,a,b,c,m): yield from (((d,) for d in enumerate(primerange(b+1,isqrt(x//c)+1),a+1)) if m==2 else (((a2,b2),)+d for a2,b2 in enumerate(primerange(b+1,integer_nthroot(x//c,m)[0]+1),a+1) for d in g(x,a2,b2,c*b2,m-1)))
    def f(x): return int(n+1+x-sum(primepi(integer_nthroot(x, k)[0]) for k in range(3, x.bit_length())))
    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
    return bisection(f,n,n) # Chai Wah Wu, Sep 11 2024

Formula

All p^k >= 16, prime p, k >= 3.

a(n) = n^3 log^3 n + O(n^3 log^2 n log log n). - Charles R Greathouse IV, Mar 11 2014