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

23·137 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

16E616 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×5×317 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 offline   Reply With Quote
Old 2018-08-29, 08:00   #4
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

23·137 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

21108 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
Dumbassville

26×131 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

2×3×977 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

23·137 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

50228 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

23·137 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
Dumbassville

838410 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 07:05.

Sun Jul 5 07:05:53 UTC 2020 up 102 days, 4:38, 1 user, load averages: 1.20, 1.30, 1.47

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.