Comments on A048247
From: "David Harden" <sylow2subgroup(AT)hotmail.com>
Date: Sat, 13 Apr 2002 22:09:27 -0400

I believe that all the terms listed there are correct.

What I mean by testing to the base p (p prime) is this:

If p occurs to the kth power in some factorial (say n!), then let 
n=sum{0<=i<=log_p(n)} (c_i*p^i) be the base p expansion of n.
Then k=ord_p(n!)=(n-sum{0<=i<=log_p(n)}(c_i))/(p-1), so

k=(sum{0<=i<=log_p(n)}(c_i*p^i-c_i))/(p-1)

k=sum{0<=i<=log_p(n)}(c_i*(p^i-1)/(p-1)), for some integers c_i with 
0<=c_i<=p-1.

All of this reasoning is reversible, so if k can be written as a linear 
combination of (p^i-1)/(p-1) with coefficients that are integers in [0,p-1], 
then there is an n such that p occurs to the kth power in n!. (While this is 
an instance of the NP-complete problem known as the knapsack problem, this 
is an easy knapsack because it is a superincreasing knapsack, since 
sum{0<=i<=m}(p^i-1) < (p^(m+1)-1)/(p-1).)

Determining whether or not this happens is what I mean by testing with 
respect to the base p.

To decide whether or not a given k is in this set, it 
suffices just to check this for the primes p<=k.
The integers that pass the test with respect to p, as I said before, are 
linear combinations of (p^i-1)/(p-1) with integral coefficients in [0,p-1]. 
The analytic number theoretic way to state this is that they arise as 
degrees of terms in the power series expansion of

(1+x+...+x^(p-1))*(1+x^(p+1)+...+x^(p^2-1))*
(1+x^(p^2+p+1)+...+x^(p^3-1)...

The nth term of this product (no relation to 'n' in earlier discussion) is a 
finite geometric series with p terms, first term 1 and common ratio 
x^((p^n-1)/(p-1)). Therefore the nth term of this product may be written as 
(x^(p*(p^n-1)/(p-1))-1)/(x^((p^n-1)/(p-1))-1).

I believe sequence to be infinite, although I cannot prove (or disprove) this is the 
case.

---- David

From: "David Harden" <sylow2subgroup@hotmail.com>, Nov 04 2004
Subject: Additional comments

Here is an algorithm 
which tests the integer n for membership in n^(1/3+o(1)) time.

Fast algorithm for testing membership in A048247 (Here n is the number 
being tested):

The basic test is the direct test for n's failure of the base p test for all 
p<=n.
This is still used, except for large primes, where certain improvements can 
be made:

If p is large enough so that n <= p^2+p-1:

Then n < p(p+1) so we may write n = a(p+1) + b where a<p and 0<=b<p. n 
passes the base p test unless a=p or b=p; since we have the inequality, this 
means n passes unless b=p.
How do we detect the b=p case quickly?

n = a(p+1) + p means n+1 = (a+1)(p+1) so that p+1 divides n.
First of all (assuming n>5), p is odd so p+1 is even and this automatically 
won't happen when n is even.
If n is odd, then we can factor n+1 (in n^o(1) time if one uses a fast 
algorithm) and list all tau(n+1) divisors d of n+1 which are large enough, 
and see if d-1 is prime (using a Lucas test, since the factorization of 
(d-1)+1=d is already known). tau(n+1) is also n^o(1) and the primality 
testing for d-1 can be done very quickly.
If one directly tests n with respect to all p < n^(1/2) after doing this, 
then one obtains a test which runs in n^(1/2+o(1)) time. But these ideas can 
be extended further:

Suppose p is large enough that n<=p^3+p^2+p-2.

Then n < p(p^2+p+1) so we may write n = c(p^2+p+1) + r1, where 0 <= c < p 
and 0 <= r1 < p^2+p+1.
If r1 = p^2+p, then r1 > (p-1)(p+1)+ (p-1)*1 so n fails the base p test at 
this first step. This kind of failure is easy to detect quickly because n = 
c(p^2+p+1) + p^2+p means p^2+p+1 divides n+1 so that we can just do a 
divisor search (and use the fact that all prime factors of p^2+p+1, aside 
from 3, must be congruent to 1 mod 3, and 3 itself may appear only once in 
the factorization of p^2+p+1) and a primality test (the idea of the Lucas 
test can be adapted here, if one is not willing to settle for a fast 
general-purpose primality test: we are testing m=(-1+sqrt(4d-3))/2 for 
primality and we know the factorization of m^2+m+1, so we can use a 
primality test which uses third-order linear recurrence sequences instead of 
the second-order ones used in the Lucas test).
This is failure at the first step in the base p test, and it can be 
eliminated for all c with one big factorization+divisor list+primality test.

If r1<=p^2+p-1, then we may write r1 = a(p+1) + b as before so that n = 
c*(p^2+p+1) + a(p+1) + b and, as before, ), 0<=a<p and 0<=b<=p.
In this case, n passes the base p test unless b=p. To detect that quickly, 
note that that means
n = c(p^2+p+1) + a(p+1) + p so that p+1 divides n+1-c.
The idea behind doing this quickly is that there are many primes p between 
n^(1/3) and n^(1/2) and only about n^(1/3) values of c that appear in base p 
testing on this interval. So we can just take each possible value of c, 
factor n+1-c, generate a divisor list for n+1-c, and see if any divisor d on 
the interval of concern has d-1 prime (again, using a Lucas test).
The interval of concern is the interval consisting of p which give rise to 
that value of c. This is easy to compute, but I won't do it here.
Also: for n>12, p=2 isn't a problem and p+1 is even so this test is 
immediately passed if n+1-c is odd. This means only those values of c 
incongruent to n mod 2 need to be tested. This takes n^o(1) time for each of 
the approximately n^(1/3)/2 values of c tested. So this overall takes 
n^(1/3+o(1)) steps.

For all primes p with p^3+p^2+p-2 < n, the direct test is  still used on 
each one. This takes n^(1/3+o(1)) steps also.