mersenneforum.org Strange factorization
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2014-08-01, 07:18 #1 CRGreathouse     Aug 2006 3·1,993 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 7·23·61 Posts 20154 + 4*x4 is reducible, though...
 2014-08-01, 08:31 #3 axn     Jun 2003 23×233 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

135338 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 100110010111012 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,993 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 100110010111012 Posts 9 factors, after all.
2014-08-03, 00:22   #9
CRGreathouse

Aug 2006

3×1,993 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

 Thread Tools

 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 19:19.

Thu May 19 19:19:53 UTC 2022 up 35 days, 17:21, 1 user, load averages: 1.85, 1.50, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔