mersenneforum.org > Math Distribution of prime factors in result of division
 Register FAQ Search Today's Posts Mark Forums Read

 2018-08-28, 11:34 #1 preda     "Mihai Preda" Apr 2015 5·172 Posts 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!
 2018-08-28, 16:54 #2 CRGreathouse     Aug 2006 5,987 Posts 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)
2018-08-28, 17:24   #3
ET_
Banned

"Luigi"
Aug 2002
Team Italia

3·1,619 Posts

Quote:
 Originally Posted by CRGreathouse 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)

2018-08-29, 08:00   #4
preda

"Mihai Preda"
Apr 2015

5·172 Posts

Quote:
 Originally Posted by CRGreathouse 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

 2018-08-29, 08:21 #5 preda     "Mihai Preda" Apr 2015 26458 Posts 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]
2018-08-29, 09:57   #6
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by preda (the opposite of "smooth")
the opposite of k-smooth is k-rough.

2018-08-29, 14:10   #7
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by preda 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.

2018-08-29, 22:40   #8
preda

"Mihai Preda"
Apr 2015

5A516 Posts

Quote:
 Originally Posted by CRGreathouse 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 :)

2018-09-04, 08:41   #9
GP2

Sep 2003

3×863 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2018-09-05, 16:50   #10
preda

"Mihai Preda"
Apr 2015

5·172 Posts

Quote:
 Originally Posted by GP2 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.

2018-09-05, 17:05   #11
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 Originally Posted by preda 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post tapion64 Miscellaneous Math 21 2014-04-18 21:02 James Heinrich Data 21 2013-09-26 19:54 pegaso56 Information & Answers 19 2009-06-29 15:04 alpertron Math 0 2006-06-23 20:07 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