Igor Schein on Thu, 23 Sep 2004 19:33:20 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: sigma explosion


On Thu, Sep 23, 2004 at 12:34:36AM -0700, Phil Carmody wrote:
> Given that sigma(3221^12) is prime, I noticed the following inexplicable
> explosion in run-time, apparantly to infinity -- i=11 is still running:
> 
> (10:26) gp > for(i=2,11,x=gettime();sigma(sigma(3221^12)^i);print(i,"
> ",gettime()))
> 2 10
> 3 30
> 4 50
> 5 70
> 6 80
> 7 110
> 8 120
> 9 150
> 10 190

The factoring mechanism doesn't detect 11th power (only checks up to
7th power):

? \g5
   debug = 5
? factor(1247451159302262598804596798564656994853573^11)
IFAC: cracking composite
        11383060931611972087309109789996968343219695883990256301855546143975326574480561146376352393480764093270004531343229460069640975362334863052665903147660436143963077669821714492900421706099931668095348370353939306558380975834271106415521419227974023535332867876933135397993776447501454350992330027448703725775032000902770797098006060636836292416703271897610369604149549615728266915657894812283903554997991520666350426291352422632334591235036729922462579117522094877
IFAC: checking for pure square
OddPwrs: is 11383060931611972087309109789996968343219695883990256301855546143975326574480561146376352393480764093270004531343229460069640975362334863052665903147660436143963077669821714492900421706099931668095348370353939306558380975834271106415521419227974023535332867876933135397993776447501454350992330027448703725775032000902770797098006060636836292416703271897610369604149549615728266915657894812283903554997991520666350426291352422632334591235036729922462579117522094877
        ...a 3rd, 5th, or 7th power?
        modulo: resid. (remaining possibilities)
           211:    6   (3rd 0, 5th 0, 7th 0)
IFAC: trying Pollard-Brent rho method
Rho: searching small factor of 1539-bit integer
Rho: using X^2+5 for up to 49152 rounds of 32 iterations
  *** factor: user interrupt after 1,560 ms.

It's trivial to add, but where do you draw a line?  

Igor