mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2018-08-28, 11:34   #1
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

5·172 Posts
Default Distribution of prime factors in result of division

I have this question, maybe somebody can give me a hint.. :

So, if I take a large power of two: A=2^n, (let's say A has on the order of 10M bits).

Now, let D be a primorial (i.e. product of successive primes, starting with 2) of about 1M bits. (or more generally, let D be very smooth for its magnitude).

If I compute Q = A / D + 1 (integer division),
is the distribution of prime factors of Q "normal", i.e. similar to a random number of the same magnitude, or is Q "special" in some way (e.g. lacking small factors, or fewer factors, or something else) because of the way it was constructed?

Thanks!
preda is offline   Reply With Quote
Old 2018-08-28, 16:54   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Generating some small ones to play with, they seem pretty normal to me.
Code:
list(minn,maxn,mind,maxd)=my(v=List([1]),D=1,t); forprime(d=2,mind-1,D*=d); forprime(d=mind,maxd, D*=d; for(n=max(logint(D,2),minn), maxn, listput(v,2^n\D+1))); Set(v)
CRGreathouse is offline   Reply With Quote
Old 2018-08-28, 17:24   #3
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

3·1,619 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Generating some small ones to play with, they seem pretty normal to me.
Code:
list(minn,maxn,mind,maxd)=my(v=List([1]),D=1,t); forprime(d=2,mind-1,D*=d); forprime(d=mind,maxd, D*=d; for(n=max(logint(D,2),minn), maxn, listput(v,2^n\D+1))); Set(v)
ET_ is online now   Reply With Quote
Old 2018-08-29, 08:00   #4
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

5·172 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Generating some small ones to play with, they seem pretty normal to me.
Code:
list(minn,maxn,mind,maxd)=my(v=List([1]),D=1,t); forprime(d=2,mind-1,D*=d); forprime(d=mind,maxd, D*=d; for(n=max(logint(D,2),minn), maxn, listput(v,2^n\D+1))); Set(v)
Thanks! I'm making my first steps in pari-gp.
So, using your function above, invoking it with:
list(400, 400, 40, 50), I get:
[1, 4199532910136274708868750686823905097356516912131253471572067684786810449195617896899419953790293354798, 197378046776404911316831282280723539575756294870168913163887181184980091112194041154272737828143787675501, 8487256011385411186623745138071112201757520679417263266047148790954143917824343769633727726610182870046521]

Now, factorizing the first of those brings:
factor(4199532910136274708868750686823905097356516912131253471572067684786810449195617896899419953790293354798)
[ 2 1]
[ 3 1]
[ 13 1]
[53840165514567624472676290856716732017391242463221198353488047240856544220456639703838717356285812241 1]

In my oppinion this number is remarkably poor in factors (the opposite of "smooth"). Is this normal for a random number of that magnitude?

Last fiddled with by preda on 2018-08-29 at 08:22
preda is offline   Reply With Quote
Old 2018-08-29, 08:21   #5
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

26458 Posts
Default

And two more obtained from list(450, 450, 40, 50):
factor(4728253712304965360776172104918292366400929448610926249872850003757049475614965333673982952183992471021952642764799855)
[ 5 1]
[ 35027 1]
[ 173647 1]
[ 188603 1]
[824350573333231137295419661117987402085770733703228108689936536657633157092374391505295405255191232653 1]

factor(222227924478333371956480088931159741220843684084713533744023950176581325353903370682677198752647646138031774209945593180)
[ 2 2]
[ 3 1]
[ 5 1]
[ 293 1]
[ 341968043 1]
[36965300104120675637317638509334753380235348353587292411044062883784126463537469392209360002306406051253647 1]
preda is offline   Reply With Quote
Old 2018-08-29, 09:57   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by preda View Post
(the opposite of "smooth")
the opposite of k-smooth is k-rough.
science_man_88 is offline   Reply With Quote
Old 2018-08-29, 14:10   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

Quote:
Originally Posted by preda View Post
In my oppinion this number is remarkably poor in factors (the opposite of "smooth"). Is this normal for a random number of that magnitude?
Yes. By the Erdős-Kac theorem you'd expect 5.4 ± 2.3 prime factors, so 4 is pretty ordinary.

But really you should look at a bunch of examples, not just one isolated example.
CRGreathouse is offline   Reply With Quote
Old 2018-08-29, 22:40   #8
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

5A516 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yes. By the Erdős-Kac theorem you'd expect 5.4 ± 2.3 prime factors, so 4 is pretty ordinary.

But really you should look at a bunch of examples, not just one isolated example.
Again, thanks for enlightening me!

log(log(n)) indicates an awfully small number of expected prime factors. I updated my intuition on that point :)
preda is offline   Reply With Quote
Old 2018-09-04, 08:41   #9
GP2
 
GP2's Avatar
 
Sep 2003

3×863 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yes. By the Erdős-Kac theorem you'd expect 5.4 ± 2.3 prime factors, so 4 is pretty ordinary.
This is a bit off-topic, but how many prime factors would we expect a Mersenne number to have? Surely less than standard Erdős-Kac prediction, since its factors are restricted to the form 2kp+1 rather than arbitrary primes.
GP2 is offline   Reply With Quote
Old 2018-09-05, 16:50   #10
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

5·172 Posts
Default

Quote:
Originally Posted by GP2 View Post
This is a bit off-topic, but how many prime factors would we expect a Mersenne number to have? Surely less than standard Erdős-Kac prediction, since its factors are restricted to the form 2kp+1 rather than arbitrary primes.
An interesting question, I'd like to know the answer as well.
preda is offline   Reply With Quote
Old 2018-09-05, 17:05   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts
Default

Quote:
Originally Posted by preda View Post
An interesting question, I'd like to know the answer as well.
logint(2^p-1,2p+1) is the absolute maximum for prime exponent p.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne Factors tapion64 Miscellaneous Math 21 2014-04-18 21:02
Known factors distribution graphs James Heinrich Data 21 2013-09-26 19:54
strange factors distribution?? pegaso56 Information & Answers 19 2009-06-29 15:04
Distribution of Mersenne prime factors mod 6 alpertron Math 0 2006-06-23 20:07
Silverman & Wagstaff on Joint Distribution of Ultimate and Penultimate Prime Factors wblipp Math 12 2006-04-02 18:40

All times are UTC. The time now is 11:54.


Sun Feb 5 11:54:22 UTC 2023 up 171 days, 9:22, 1 user, load averages: 1.21, 1.19, 1.02

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

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