Odds a largish number has N divisors?

[grandpascorpion]

Hello,

Say I wanted to find the odds that a large number (say 10^200) was square-free 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 3-smooth 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)= n-30 is pretty thorny. Most E's have solutions <=2^128

Any pointers would be appreciated. Thanks

[R. Gerbicz]

Solutions for E=92:
n=2^24-92
n=2^48-92
n=2^96-92
n=2^192-92

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^k-E where d(n)=k. But if k has got a "large" prime divisor=q then it means that n=2^k-E has got a prime divisor which power is at least q-1, 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.

[grandpascorpion]

Sure, I found 92's answers as well.

30 is very difficult. 2^768 is a possibility, the only non-longshot 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?

[R. Gerbicz]

Originally Posted by grandpascorpion

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?

Yes, you've right: T ( different ) prime divisors and 2^T divisors. I think that for every even E values the number of the solutions is finite.

Here you can read the famous theorem from Erdős Pál-Kac to find the odds: http://mathworld.wolfram.com/Erdos-KacTheorem.html

[grandpascorpion]

Thanks for the pointer.

I agree with you about the finite number of cases. Intuitively, it makes good sense to me, anyways.

[Citrix]

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^s-1 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

[R. Gerbicz]

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^k-1 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^k-E 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.

[grandpascorpion]

Even numbers E under 100 that I haven't found yet:
30,62,88,98

This means factoring numbers of the form 2^n-30. Generally, you would want to check n where it's a power of 2 or 3-smooth. 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:

Answer at E=2, Exp=2, v=2. factors are Mat([2, 1])
Answer at E=4, Exp=3, v=4. factors are Mat([2, 2])
Answer at E=6, Exp=4, v=10. factors are [2, 1; 5, 1]
Answer at E=8, Exp=4, v=8. factors are Mat([2, 3])
Answer at E=10, Exp=4, v=6. factors are [2, 1; 3, 1]
Answer at E=12, Exp=6, v=52. factors are [2, 2; 13, 1]
Answer at E=14, Exp=6, v=50. factors are [2, 1; 5, 2]
Answer at E=16, Exp=5, v=16. factors are Mat([2, 4])
Answer at E=18, Exp=8, v=238. factors are [2, 1; 7, 1; 17, 1]
Answer at E=20, Exp=6, v=44. factors are [2, 2; 11, 1]
Answer at E=22, Exp=16, v=65514. factors are [2, 1; 3, 1; 61, 1; 179, 1]
Answer at E=24, Exp=8, v=232. factors are [2, 3; 29, 1]
Answer at E=26, Exp=8, v=230. factors are [2, 1; 5, 1; 23, 1]
Answer at E=28, Exp=9, v=484. factors are [2, 2; 11, 2]
No answer at E=30 between 2 and maxSearch 766
Answer at E=32, Exp=6, v=32. factors are Mat([2, 5])
Answer at E=34, Exp=8, v=222. factors are [2, 1; 3, 1; 37, 1]
Answer at E=36, Exp=6, v=28. factors are [2, 2; 7, 1]
Answer at E=38, Exp=128, v=340282366920938463463374607431768211418. Stage 1
Answer at E=40, Exp=16, v=65496. factors are [2, 3; 3, 1; 2729, 1]
Answer at E=42, Exp=16, v=65494. factors are [2, 1; 11, 1; 13, 1; 229, 1]
Answer at E=44, Exp=6, v=20. factors are [2, 2; 5, 1]
Answer at E=46, Exp=6, v=18. factors are [2, 1; 3, 2]
Answer at E=48, Exp=10, v=976. factors are [2, 4; 61, 1]
Answer at E=50, Exp=12, v=4046. factors are [2, 1; 7, 1; 17, 2]
Answer at E=52, Exp=6, v=12. factors are [2, 2; 3, 1]
Answer at E=54, Exp=256, v=115792089237316195423570985008687907853269984665640564039457584007913129639882. Stage 1
Answer at E=56, Exp=16, v=65480. factors are [2, 3; 5, 1; 1637, 1]
Answer at E=58, Exp=16, v=65478. factors are [2, 1; 3, 1; 7, 1; 1559, 1]
Answer at E=60, Exp=24, v=16777156. factors are [2, 2; 11, 1; 593, 1; 643, 1]
No answer at E=62 between 2 and maxSearch 766
Answer at E=64, Exp=7, v=64. factors are Mat([2, 6])
Answer at E=66, Exp=8, v=190. factors are [2, 1; 5, 1; 19, 1]
Answer at E=68, Exp=12, v=4028. factors are [2, 2; 19, 1; 53, 1]
Answer at E=70, Exp=8, v=186. factors are [2, 1; 3, 1; 31, 1]
Answer at E=72, Exp=8, v=184. factors are [2, 3; 23, 1]
Answer at E=74, Exp=8, v=182. factors are [2, 1; 7, 1; 13, 1]
Answer at E=76, Exp=24, v=16777140. factors are [2, 2; 3, 1; 5, 1; 279619, 1]
Answer at E=78, Exp=12, v=4018. factors are [2, 1; 7, 2; 41, 1]
Answer at E=80, Exp=10, v=944. factors are [2, 4; 59, 1]
Answer at E=82, Exp=8, v=174. factors are [2, 1; 3, 1; 29, 1]
Answer at E=84, Exp=12, v=4012. factors are [2, 2; 17, 1; 59, 1]
Answer at E=86, Exp=8, v=170. factors are [2, 1; 5, 1; 17, 1]
No answer at E=88 between 2 and maxSearch 510
Answer at E=90, Exp=256, v=115792089237316195423570985008687907853269984665640564039457584007913129639846. Stage 1
Answer at E=92, Exp=24, v=16777124. factors are [2, 2; 7, 1; 13, 1; 46091, 1]
Answer at E=94, Exp=16, v=65442. factors are [2, 1; 3, 1; 13, 1; 839, 1]
Answer at E=96, Exp=48, v=281474976710560. factors are [2, 5; 5, 1; 211, 1; 8337528931, 1]
No answer at E=98 between 2 and maxSearch 358

[R. Gerbicz]

k=2^359-98 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^360-98=2*584599*4345765943*8586291113*C

and the remaining odd composite number isn't a perfect square so
d(2^360-98)=16*d(c) but c is odd and isn't a perfect square so d(c) is even.
From this d(2^360-98) is divisible by 32 but 360 isn't divisible by 32.

k=2^511-88 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^512-88=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^512-88)>=1024 so 2^512-88 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.

[grandpascorpion]

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^512-88, 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

[R. Gerbicz]

2^512-88 isn't a solution for E=88! I've posted that:
2^512-88=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^512-88)=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^512-88 isn't a solution for E=88.