Abundant numbers of form n^2+n+1

[Jack Brennen]

> njas> mf> Martin said:
> njas> mf> Another solution is n=19581212842 which has
> njas> mf> n^2+n+1 = 3*7^2*13*19*31*37*43*61*79*97*103*4447
> njas> mf> sigma(n^2+n+1)/(n^2+n+1) = 2.0031147...
> njas> 
> njas> Me:  That almost brings the problem within range
> njas> of a brute force search.  If 100 seqfans searched
> njas> for 100 days using ...  What IS the fastest program
> njas> for this sort of thing?  Mathematica, Pari, Sage?
> njas> Simon, what do you think?
> njas> (The question is, what is the smallest amicable 
> njas> number of the form n^2+n+1 ?)
> njas> 
> njas> Neil



It's not too hard to show that if n^2+n+1 is abundant and less
than 10^24, it must be divisible by 3, 7, 13, 19, and at least
one of 31 or 37.  (Just assume the opposite is true, and then
try to use allowable factors to get to a sigma ratio of 2.0
without going over 10^24 -- you can't do it.  Note that you
need to use the fact that n^2+n+1 is never divisible by 9.)

For n^2+n+1 divisible by 3*7*13*19*31, you have 16 possibilities
for n modulo 160797, so you only need to test roughly one of
every 10000 possibilities for n.

Likewise for 3*7*13*19*37, you have 16 possibilities
for n modulo 191919, so you only need to test roughly one of
every 12000 possibilities for n.

So searching up to n=19581212842 should involve almost
2 million tests using factor 31, and a little less than
2 million tests using factor 37.

I've run these roughly 3.5 million tests using PARI and verified
that the smallest abundant n^2+n+1 does occur when
n=19581212842.  (Nowhere near 10,000 seqfan-days needed.)

The nearest any number (from this search space) below that
comes to being abundant is for n=13582594132, where
sigma(n^2+n+1)/(n^2+n+1) is equal to 1.9943125...

Obviously, it would be nice if someone else could verify my
results independently -- both the assertion in my first
paragraph above, and the assertion that the first abundant
n^2+n+1 divisible by 3*7*13*19*(31 or 37) is for n=19581212842.