20060208, 19:10  #1 
Jan 2005
Transdniestr
503 Posts 
Odds a largish number has N divisors?
Hello,
Say I wanted to find the odds that a large number (say 10^200) was squarefree and had x distinct prime factors and I have already done trial factoring through 10^9. I also know that the number is not a perfect power. Is there a way to get a rough approximation on the probability? Ideally, I'd like to generalize this to any number of divisors (i.e. what are the odds a number is of the form a^3bc where a,b,c and are primes). The background is the following: http://www.primepuzzles.net/puzzles/puzz_349.htm I don't see a reason why the conjecture would be false especially when d(n) is some power of two or it's at least 3smooth but I was curious about the rough odds for a given d(n) and approximate n. It turns out finding a solution to: 2^d(n)= n30 is pretty thorny. Most E's have solutions <=2^128 Any pointers would be appreciated. Thanks Last fiddled with by grandpascorpion on 20060208 at 19:12 
20060208, 19:56  #2 
"Robert Gerbicz"
Oct 2005
Hungary
2×733 Posts 
Solutions for E=92:
n=2^2492 n=2^4892 n=2^9692 n=2^19292 I think that the conjecture is false! Some interesting pseudo proof for this: A random integer n has got loglog(n) different prime divisors and almost all of them has got power=1, from equation 2^d(n)=n+E so n=2^kE where d(n)=k. But if k has got a "large" prime divisor=q then it means that n=2^kE has got a prime divisor which power is at least q1, but it's probability is very small: This is the reason why the solutions for E=92 has got very special structure: 24=2^3*3, 48=2^4*3, 96=2^5*3, 192=2^6*3. So there are very few possibilities for k, for example k=2^T, 3*2^T,9*2^T,.... for example for k=2^T, n=2^(2^T)E and it has to be 2^T different prime divisors, but for n the expected number of prime divisors is less: loglog(n) is about T*log(2) and there are theorems for Ramanujan ( a much easier proof by Hungarian number theorist Turán Pál ) that for almost all numbers the number of different prime divisors is "very close" to loglog(n). If we sum the probabilities I think that we can get a convergent serie, so it is possible that there is no solution for certain even E values. 
20060208, 20:32  #3 
Jan 2005
Transdniestr
503 Posts 
Sure, I found 92's answers as well.
30 is very difficult. 2^768 is a possibility, the only nonlongshot under 1000. I think you mean 2^T divisors rather than 2^T prime divisors. Thanks for the average formula. Would you know of a way to find the odds it would vary from the average? 
20060208, 20:52  #4  
"Robert Gerbicz"
Oct 2005
Hungary
2×733 Posts 
Quote:
Here you can read the famous theorem from Erdős PálKac to find the odds: http://mathworld.wolfram.com/ErdosKacTheorem.html Last fiddled with by R. Gerbicz on 20060208 at 20:53 

20060208, 21:32  #5 
Jan 2005
Transdniestr
111110111_{2} Posts 
Thanks for the pointer.
I agree with you about the finite number of cases. Intuitively, it makes good sense to me, anyways. 
20060209, 00:45  #6 
Jun 2003
1,579 Posts 
I personally think there are infinite number of cases for each E.
let 2^(d)=n+e then 2^(d)e=n Let e=1 or what ever you may want to it be, The problem amounts to this can 2^s1 have s divisors. If the number has log2(s) factors then the number has (s) divisors. On average each factor will be 2^s/log2(s) digits. For example s=128 then there are a huge alot of numbers with 128 bits and 7 factors. Each factor on average being 18 bits= under 2^18 or <~270,000 It is easy to generate such numbers. Hence infinite such numbers exist.(Not a mathematical proof, but an instinctive one) For all values of e say under 100, can the lowest d be found? Please post below values that you have found so far. Intresting problem though. Citrix 
20060209, 09:59  #7 
"Robert Gerbicz"
Oct 2005
Hungary
2×733 Posts 
The problem asked only for even values of E. However we can also examine odd and possible negative values of E. For E=1 the problem is a little different from other cases because 2^k1 is a cyclotomic number. For E=1 we can get 2^k+1 also cyclotomic numbers.
It is easy to prove that if E=0 then there is no solution! Otherwise there is n for: 2^d(n)=n so n is a power of 2, so n=2^k but in this case d(n)=k+1 so 2^d(n)=2^(k+1) isn't equal to n=2^k, it's a contradiction. Citrix if we can sum the probabilities that 2^kE is a solution and this sum is finite then the expected number of solutions of the equation is also finite! That's why I said I think that there is only finite number of solutions for each E. I haven't got a table for this problem. 
20060209, 12:30  #8  
Jan 2005
Transdniestr
503 Posts 
Just a reminder, the puzzle is a conjecturing involving even E
Even numbers E under 100 that I haven't found yet:
30,62,88,98 This means factoring numbers of the form 2^n30. Generally, you would want to check n where it's a power of 2 or 3smooth. The numbers you have to factor grow quickly. I understand what the average length of the factor would be. The probability is what I was looking for. And, it's very easy to multiply x factors to get a number f and find the E which would n  f. It's akin to multiplying two primes to get a big number. Finding a case for a specific E is like factoring that big number. Much, much harder. There's likely an infinite number of E's with solutions but there almost certainly aren't an infinity of answers for each even E. I'm beginning to doubt that each E has an even one answer. Here's the answers I have: Quote:


20060209, 13:47  #9 
"Robert Gerbicz"
Oct 2005
Hungary
2×733 Posts 
k=2^35998 is an easy case because d(k)=359 is impossible ( k is odd but isn't a perfect square, so d(k) should be odd)
I think this was the next hard step for you: 2^36098=2*584599*4345765943*8586291113*C and the remaining odd composite number isn't a perfect square so d(2^36098)=16*d(c) but c is odd and isn't a perfect square so d(c) is even. From this d(2^36098) is divisible by 32 but 360 isn't divisible by 32. k=2^51188 isn't a solution for E=88 because d(k)=511 is odd but k is odd and not a perfect square. This is the next hard number: 2^51288=2^3*3*7*2383*16889*1914893475039724462187*9142510112016355128979*C but c is odd composite and not a perfect square so d(c)>=4, from this d(2^51288)>=1024 so 2^51288 is also not a solution. In general it is easy to prove that if m is odd composite and not a perfect square then d(m)>=4 and d(m) is even. grandpascorpion you can extend your table using this fact and my results. 
20060209, 15:11  #10 
Jan 2005
Transdniestr
503 Posts 
Hi R,
We're on the same wavelength. I meant that I tested through 511 and 359 inclusive. (actually 446 now for E=98). I'm not actually testing 511 per reasons you cited. I'm using that fact that if E= m*2^x (where m is odd), it must be that (x+1)  d(n). So, I'm only considering those cases. So for 88, d(n) must be a multiple of 4 (because 88=2^3*11) so I think it's possible to have a solution with n=512. For 2^51288, I'm down to a 123 digit number that needs to be split into two prime factors. Could be a daunting task. I'm also prefactoring to a certain range, chipping away at the number and number of divisors I need and then determining if it's a solution is possible where you have a minimum # of factors and given that I have prefactored through a certain range. For instance, if I have prefactored through 10^9, my number to factor is 10^80 and to solve the relation I need a minimum of 12 more factors based on my given target n, there is no possible solution because (10^9)^12 > (10^80). In this way, I can check unsmooth numbers at but cheaply eliminate them (usually anyways). I'm also running the checks you cited with 360. I hadn't found the next factors you mentioned at the time of the last mail. Gramps 
20060209, 15:31  #11 
"Robert Gerbicz"
Oct 2005
Hungary
2·733 Posts 
2^51288 isn't a solution for E=88! I've posted that:
2^51288=2^3*3*7*2383*16889*1914893475039724462187*9142510112016355128979*C where C is an odd composite number and not a perfect square, hence d(C)>=4. But the function of d() is multiplicative so: d(2^51288)=d(2^3)*d(3)*d(7)*d(2383)*d(16889)*d(1914893475039724462187)*d(9142510112016355128979)*d(C) =256*d(C)>=1024 so it shouldn't be 512. It means that 2^51288 isn't a solution for E=88. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fermat number and Modulo for searching divisors  CyD  Factoring  4  20110531 11:24 
Odds that a Random Prime is a Number?  R.D. Silverman  Homework Help  60  20101013 10:31 
Odds that a random number is prime  Number theory  Homework Help  4  20090828 22:04 
Odds of a prime number being random  Orgasmic Troll  Lounge  6  20070811 04:09 
Number of divisors of n?  Citrix  Math  10  20060208 04:09 