20180828, 11:34  #1 
"Mihai Preda"
Apr 2015
5·17^{2} 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! 
20180828, 16:54  #2 
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,mind1,D*=d); forprime(d=mind,maxd, D*=d; for(n=max(logint(D,2),minn), maxn, listput(v,2^n\D+1))); Set(v) 
20180828, 17:24  #3 
Banned
"Luigi"
Aug 2002
Team Italia
3·1,619 Posts 

20180829, 08:00  #4  
"Mihai Preda"
Apr 2015
5·17^{2} Posts 
Quote:
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 20180829 at 08:22 

20180829, 08:21  #5 
"Mihai Preda"
Apr 2015
2645_{8} 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] 
20180829, 09:57  #6 
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 

20180829, 14:10  #7  
Aug 2006
5,987 Posts 
Quote:
But really you should look at a bunch of examples, not just one isolated example. 

20180829, 22:40  #8  
"Mihai Preda"
Apr 2015
5A5_{16} Posts 
Quote:
log(log(n)) indicates an awfully small number of expected prime factors. I updated my intuition on that point :) 

20180904, 08:41  #9  
Sep 2003
3×863 Posts 
Quote:


20180905, 16:50  #10 
"Mihai Preda"
Apr 2015
5·17^{2} Posts 
An interesting question, I'd like to know the answer as well.

20180905, 17:05  #11 
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Distribution of Mersenne Factors  tapion64  Miscellaneous Math  21  20140418 21:02 
Known factors distribution graphs  James Heinrich  Data  21  20130926 19:54 
strange factors distribution??  pegaso56  Information & Answers  19  20090629 15:04 
Distribution of Mersenne prime factors mod 6  alpertron  Math  0  20060623 20:07 
Silverman & Wagstaff on Joint Distribution of Ultimate and Penultimate Prime Factors  wblipp  Math  12  20060402 18:40 