mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Probability & Probabilistic Number Theory

Reply
 
Thread Tools
Old 2014-08-01, 07:18   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default 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!
CRGreathouse is offline   Reply With Quote
Old 2014-08-01, 07:57   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

20154 + 4*x4 is reducible, though...
Batalov is offline   Reply With Quote
Old 2014-08-01, 08:31   #3
axn
 
axn's Avatar
 
Jun 2003

2·34·29 Posts
Default

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.
axn is offline   Reply With Quote
Old 2014-08-01, 14:03   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

592510 Posts
Default

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

Quote:
Originally Posted by axn View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2014-08-01, 17:22   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2014-08-01, 17:24   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

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...
Batalov is offline   Reply With Quote
Old 2014-08-01, 18:04   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2014-08-02, 23:35   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

9 factors, after all.
Batalov is offline   Reply With Quote
Old 2014-08-03, 00:22   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

172516 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:16.

Mon Sep 28 23:16:23 UTC 2020 up 18 days, 20:27, 0 users, load averages: 2.10, 1.76, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.