Distribution of prime factors in result of division

[preda]

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!

[CRGreathouse]

Generating some small ones to play with, they seem pretty normal to me.

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_]

Originally Posted by CRGreathouse

Generating some small ones to play with, they seem pretty normal to me.

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)

[preda]

Originally Posted by CRGreathouse

Generating some small ones to play with, they seem pretty normal to me.

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?

[preda]

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]

[science_man_88]

Originally Posted by preda

(the opposite of "smooth")

the opposite of k-smooth is k-rough.

[CRGreathouse]

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.

[preda]

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 :)

[GP2]

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.

[preda]

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.

[science_man_88]

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.