mersenneforum.org Strange factorization
 Register FAQ Search Today's Posts Mark Forums Read

 2014-08-01, 07:18 #1 CRGreathouse     Aug 2006 3×1,987 Posts Strange factorization I asked a question on stats.stackexchange about the factorization of 20154 + 41345 (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 20154 + x1345 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!
 2014-08-01, 07:57 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 33×73 Posts 20154 + 4*x4 is reducible, though...
 2014-08-01, 08:31 #3 axn     Jun 2003 10010111010102 Posts Yes. Looks like Aurifeuillean Factorization is at play. The 405-digit 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.
2014-08-01, 14:03   #4
CRGreathouse

Aug 2006

3×1,987 Posts

Quote:
 Originally Posted by Batalov 20154 + 4*x4 is reducible, though...
Perfect! That's why I love this forum.

Quote:
 Originally Posted by axn Yes. Looks like Aurifeuillean Factorization is at play. The 405-digit 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.
Indeed.

2014-08-01, 17:22   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by CRGreathouse Perfect! That's why I love this forum. Indeed.
Nomenclature correction:

It is not an Aurefeuillian factorization. i.e. that of X^4 + 4Y^4

Apply Erdos-Kac. How many factors does each of the algebraic
factors have? Is it more than 3 Sigma from the mean?

 2014-08-01, 17:24 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 926110 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 "Sierpinski-like number" for it because the expression was never prime (y>1), algebraically. Well, it is not a "Sierpinski-like 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^672-2*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...
2014-08-01, 18:04   #7
CRGreathouse

Aug 2006

3·1,987 Posts

Quote:
 Originally Posted by R.D. Silverman Apply Erdos-Kac. How many factors does each of the algebraic factors have? Is it more than 3 Sigma from the mean?
2^672*4030+4^672*2+2015^2

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.

 2014-08-02, 23:35 #8 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 33·73 Posts 9 factors, after all.
2014-08-03, 00:22   #9
CRGreathouse

Aug 2006

10111010010012 Posts

Quote:
 Originally Posted by Batalov 9 factors, after all.

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 2014-08-03 at 00:37

 Similar Threads Thread Thread Starter Forum Replies Last Post bayanne Software 6 2016-04-06 04:33 schickel FactorDB 7 2012-02-02 00:10 siew Factoring 70 2010-05-31 22:31 MatWur-S530113 GMP-ECM 2 2007-11-19 00:01 HiddenWarrior Software 5 2005-08-22 08:34

All times are UTC. The time now is 15:31.

Thu Jan 21 15:31:16 UTC 2021 up 49 days, 11:42, 0 users, load averages: 1.48, 1.98, 2.05