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.