mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-02-08, 19:10   #1
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default Odds a largish number has N divisors?

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

Last fiddled with by grandpascorpion on 2006-02-08 at 19:12
grandpascorpion is offline   Reply With Quote
Old 2006-02-08, 19:56   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2006-02-08, 20:32   #3
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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?
grandpascorpion is offline   Reply With Quote
Old 2006-02-08, 20:52   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

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

Last fiddled with by R. Gerbicz on 2006-02-08 at 20:53
R. Gerbicz is offline   Reply With Quote
Old 2006-02-08, 21:32   #5
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default

Thanks for the pointer.

I agree with you about the finite number of cases. Intuitively, it makes good sense to me, anyways.
grandpascorpion is offline   Reply With Quote
Old 2006-02-09, 00:45   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

1,579 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2006-02-09, 09:59   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2006-02-09, 12:30   #8
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default 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^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:

Quote:
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
grandpascorpion is offline   Reply With Quote
Old 2006-02-09, 13:47   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×733 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Old 2006-02-09, 15:11   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2006-02-09, 15:31   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·733 Posts
Default

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.
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fermat number and Modulo for searching divisors CyD Factoring 4 2011-05-31 11:24
Odds that a Random Prime is a Number? R.D. Silverman Homework Help 60 2010-10-13 10:31
Odds that a random number is prime Number theory Homework Help 4 2009-08-28 22:04
Odds of a prime number being random Orgasmic Troll Lounge 6 2007-08-11 04:09
Number of divisors of n? Citrix Math 10 2006-02-08 04:09

All times are UTC. The time now is 09:55.

Tue May 11 09:55:39 UTC 2021 up 33 days, 4:36, 1 user, load averages: 2.14, 1.77, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.