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!

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)[/code]

[QUOTE=CRGreathouse;494801]Generating some small ones to play with, they seem pretty [COLOR="Red"]normal[/COLOR] 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)[/code][/QUOTE]

:smile::smile::smile:

[QUOTE=CRGreathouse;494801]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)[/code][/QUOTE]

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?

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]

[QUOTE=preda;494839](the opposite of "smooth")[/QUOTE]

the opposite of k-smooth is k-rough.

[QUOTE=preda;494839]In my oppinion this number is remarkably poor in factors (the opposite of "smooth"). Is this normal for a random number of that magnitude?[/QUOTE]

Yes. By the [url=https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem]Erdős-Kac theorem[/url] 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.

[QUOTE=CRGreathouse;494864]Yes. By the [url=https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem]Erdős-Kac theorem[/url] 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.[/QUOTE]

Again, thanks for enlightening me!

log(log(n)) indicates an awfully small number of expected prime factors. I updated my intuition on that point :)

[QUOTE=CRGreathouse;494864]Yes. By the [url=https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Kac_theorem]Erdős-Kac theorem[/url] you'd expect 5.4 ± 2.3 prime factors, so 4 is pretty ordinary.[/QUOTE]

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.

[QUOTE=GP2;495319]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.[/QUOTE]

An interesting question, I'd like to know the answer as well.

[QUOTE=preda;495430]An interesting question, I'd like to know the answer as well.[/QUOTE]

logint(2^p-1,2p+1) is the absolute maximum for prime exponent p.