[seqfan] Re: min(d(p^n-1)) for sufficiently large p

[hv at crypt.org]

franktaw at netscape.net wrote:
:I think I would recommend something like "a(n) is the largest value m 
:such that p^n-1 has at least m divisors for sufficiently large primes 
:p", with a comment like "All terms in this sequence are conjectured; 
:even that such a value exists is a conjecture." You ought to be able to 
:find a suitable conjecture to support the values on-line somewhere - 
:perhaps at <http://www.primepuzzles.net/conjectures/>.

Given the comments from Max and yourself, I think then it is better to
fall back to the alternative approach - name the sequence by the formula
and move the interpretation to a comment. Neil is quite rightly resistant
to sequences whose values change over time.

:I don't normally support making a sequence with all conjectured values, 
:but in this case, this really is what the sequence is. If someone 
:found, for example, that there are only finitely many Sophie Germain 
:primes, the values in the sequence would be changed.

The intended sequence does not involve any conjectured values, but
I obviously haven't managed to make that clear.

:Do you have a program that generates these values? If you do, it should 
:definitely be included - send it as a separate file with a link if it 
:is too long for direct inclusion. Otherwise some more complete 
:description of how the values were determined ought to be included.

I had generated values up to a(9) by hand, then found A079612(n) and
understood that this bore a direct relation to the sequence I was trying
to generate. I think the formula for A079612() is sufficient to make
these values fairly easy to calculate, but the values listed below were
generated directly from the values listed for A079612() (and so if there
are any errors in A079612() they will be propagated here).


Below is the new version of the sequence that I am now proposing. Note
that only the %N, %C and %e lines have changed. I suspect they could
be further improved, but I hope it is at least clear that this sequence
is not conjectural or subject to change with new information.

%I A000001
%S A000001 4,32,8,160,8,384,8,384,16,256,8,7680,8,128,32,1792,8,4096,8,3840,32,
%T A000001 256,8,36864,16,128,32,2560,8,24576,8,4096,32,128,32,327680,8,128,32,
%U A000001 36864,8,18432,8,2560,128,256,8,344064,16,1024,32,2560,8,20480,32,
%N A000001 d(A079612(n)) . 2^d(n)
%C A000001 p^n-1 has at least a(n) divisors for all sufficiently large primes p, i.e. lim inf d(p^n-1) >= a(n). It may or may not be a tight bound: for n=1, for example, lim inf d(p^n-1) = a(n) is equivalent to the assertion that there are infinitely many Sophie Germain primes.
%F A000001 a(n) = d(A079612(n)) . 2^d(n) (where d(n)=A000005(n))
%e A000001 A079612(2)=24, so a(2) = d(24).2^d(2) = 32. From A079612() we know that 24 must divide p^2-1 for all primes p except 2 and 3. With a finite number of small exceptions, the factors p-1 and p+1 must contribute either an additional distinct prime factor or enough small repeated factors to ensure that d(p^2-1) >= d(24qr) with q, r distinct primes > 3, so lim inf d(p^2-1) >= d(24qr) = 32.
%Y A000001 Cf. A000005, A079612.
%K A000001 new,nonn
%O A000001 1,1
%A A000001 hv at crypt.org (Hugo van der Sanden)

Hugo