20140801, 07:18  #1 
Aug 2006
5,987 Posts 
Strange factorization
I asked a question on stats.stackexchange about the factorization of 2015^{4} + 4^{1345} (a number I just 'happened upon') because I was struck by the somewhat unusual factorization. At the time I was hoping for an algebraic factorization that I had missed, though this seems unlikely since 2015^{4} + x^{1345} is irreducible. But is there any reason for this behavior? If it was just a typical number of its size the chance that it would have so many factors so (relatively) close together is something like .3% (which, I was reminded, corresponds to an alpha of about .006 since a priori I could have been surprised in either direction).
I did not cherry pick this number  it was the only number I examined, and I suspected something funny  algebraic factorization or other  before I attempted the factorization. It could be simple chance but I think not  I think it shows a lack of understanding of factorizations on my part. Educate me! 
20140801, 07:57  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,313 Posts 
2015^{4} + 4*x^{4} is reducible, though...

20140801, 08:31  #3 
Jun 2003
5404_{10} Posts 
Yes. Looks like Aurifeuillean Factorization is at play. The 405digit unfactored part and it's cofactor are very close together in size.
That still leaves the question of why one of the cofactors split further into so many. 
20140801, 14:03  #4 
Aug 2006
1763_{16} Posts 
Perfect! That's why I love this forum.
Indeed. 
20140801, 17:22  #5 
"Bob Silverman"
Nov 2003
North of Boston
1D34_{16} Posts 

20140801, 17:24  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,313 Posts 
When I first looked at the factordb entry it still had a c650 cofactor. But I recently was ruminating about x^y+y^x and convinced myself that x=4 would be a "Sierpinskilike number" for it because the expression was never prime (y>1), algebraically. Well, it is not a "Sierpinskilike number" in spirit, really; there is no covering set.
So, I submitted the 2015^2+2*4^672+2*2015*2^672 2015^2+2*4^6722*2015*2^672 factors; the DB usually does gcd, but it didn't. Then I ran gcd in Pari and submitted the c245 and c405, and the entry started to look like it does now. For fun, I've done the same to 2015^4+4^1015 2015^4+4^2015 Of course, one can also generate a test file of these algebraic factorizations with awk or perl and submit it to the DB... 
20140801, 18:04  #7  
Aug 2006
1011101100011_{2} Posts 
Quote:
I don't have a full factorization, so all I can say is that it has 8 or more prime factors. 8 wouldn't be unusual for a number of that size. The other algebraic factor is completely unfactored. 

20140802, 23:35  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3×3,313 Posts 
9 factors, after all.

20140803, 00:22  #9 
Aug 2006
5,987 Posts 
So that's definitely unusual clustering on the one algebraic factor. Does anyone know why? I see that 44971818273701332261784061961 * 9664021418404865297256058765601 * 386265978137298005895635792872544753829637 is close to a quarter of the logarithmic total, but not close enough that I could reasonably expect something nice like the original factorization. Last fiddled with by CRGreathouse on 20140803 at 00:37 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Something strange ...  bayanne  Software  6  20160406 04:33 
Something *really* strange  schickel  FactorDB  7  20120202 00:10 
A strange RSA key  siew  Factoring  70  20100531 22:31 
Strange bug with GMPECM  MatWurS530113  GMPECM  2  20071119 00:01 
Strange bug  HiddenWarrior  Software  5  20050822 08:34 