mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2012-05-14, 10:02   #1
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

212210 Posts
Default Escaping drivers (moved from 4788 thread)

Quote:
Originally Posted by R. Gerbicz View Post
Escaping from 2^4*31 isn't very hard, see the elf file for 5778. Between line 390-973 we have 2^4*31^e, for e>0. And for 21 times e=2, for one time e=3 and for the rest e=1. So escaping it is easy but on the next line we see again 2^4*31. I would say it is hard to kill the 31 as a factor in 2^4*31.
Quote:
Originally Posted by Dubslow View Post
Looks like 972 and 804 were potential escapes, but the rest of them were definitely pretty darn smooth. (If my understanding of schickel is accurate.)
The trick is that the escape does not happen until the power of 2 changes. After the 2 changes, the other piece(s) of the driver will appear on the next line, then, depending on the relative sizes of the primes, drop off after one or more lines.

I have two immediate examples that I recently dealt with vis a vis 2^9 * 3 * 11 * 31. First, 363270 broke this way: Driver acquired on line 1418, size 64, driver lost on line 1619, size 133; the lines after escape factored this way:
Code:
2^9 * 3 * 11 * 31^2
2^8 * 3 * 11 * 31
2^8 * 3 
2^8 * 3 
2^8 * 3 
2^8 * 3 
2^8 * 3 
2^8 * 3^4 * 31
2^8 * 3^3 * 31
2^8 * 3^3 
2^9 * 3^2 
2^7 * 3^2 
2^7 * 3^4 
2^7 * 3^2 
2^7 * 3^2 
2^7 * 3^2 
2^7 * 3^2 
2^8 * 3^2 
2^8 * 3^5 
2^11 * 3^5 
2^11 * 3^6 
2^10 * 3^5 
2^10 * 3^5
2^7
As you can see, that darn 3 likes to hang in there....

For 572000, driver acquired on line 2886, size 86; driver lost on line 3070, size 151; after loss:
Code:
2^9 * 3 * 11 * 31^2
2^8 * 3 * 11 * 31^2
2^8 * 3 * 11 * 31 
2^8 * 3 * 11^3 * 31
2^8 * 3 * 11 
2^8 * 3 
2^8 * 3 
2^8 * 3 
2^8 * 3 
2^6 * 3 
2^6 * 3 
2^6 * 3 
2^6 * 3 
2^4 * 3 
2^4 * 3 
2^4 * 3 
2^4 * 3 
2^4 * 3 
2^4 * 3 
2^4 * 3^2 
2^4 * 7
And again you can see that darn 3 just hanging on....
schickel is offline   Reply With Quote
Old 2012-05-15, 18:15   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

575410 Posts
Default

The lower the factor the more likely it is to stay on.
For 3 there is 50% chance of each factor keeping the 3 for the next iteration.
The probability of keeping 3 with n factors is:
Code:
n       probability
1         50%
2         75%
3         87.5%
4         93.75%
5         96.88%
For 7 there is a 1/6 = 16.67% chance of each factor keeping the 7 so the probability of keeping the 7 with n factors becomes:
Code:
n       probability
1         16.67%
2         30.56%
3         42.13%
4         51.77%
5         59.81%
This is noticeably lower.
I wonder if there is a formula estimating the number of factors a number of a certain size will have.
henryzz is online now   Reply With Quote
Old 2012-05-15, 19:44   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by henryzz View Post
I wonder if there is a formula estimating the number of factors a number of a certain size will have.
x^n for prime x either has 1 factor or n factors if n then x=2 gives you the most a given length can have, 2^3=8<10 so the maximum for 1 digits is 3 2^6=64<100 gives you up to 6 but it will change by from just 3 added each time because log_2(10) is about 3.321928094887362347870319430 this will round up another one every so often. your minimum the lowest prime below 10 is 7 I would believe that should give you a low end.
science_man_88 is offline   Reply With Quote
Old 2012-05-15, 20:53   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
x^n for prime x either has 1 factor or n factors if n then x=2 gives you the most a given length can have, 2^3=8<10 so the maximum for 1 digits is 3 2^6=64<100 gives you up to 6 but it will change by from just 3 added each time because log_2(10) is about 3.321928094887362347870319430 this will round up another one every so often. your minimum the lowest prime below 10 is 7 I would believe that should give you a low end.
okay technically the low limit is 2 and isn't based on 7,
science_man_88 is offline   Reply With Quote
Old 2012-05-18, 13:08   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100011000000112 Posts
Default

Battlefield, episode 95280, challenging the record for breaking D4 ...
(related to the discussion in the 4788 thread)

Code:
.1597 C137 = 2^4 * 3 * 5 * 31 * ...
.1598 C137 = 2^4 * 3 * 5 * 31 * ...
.1599 C138 = 2^4 * 3^3 * 5 * 31 * ...
.1600 C138 = 2^4 * 3^3 * 5 * 31 * ...
.1601 C139 = 2^4 * 3^2 * 5 * 7^2 * 31^3 * ...
.1602 C139 = 2^4 * 3^2 * 5 * 7^2 * 31 * ... * C133
LaurV is offline   Reply With Quote
Old 2012-05-19, 18:36   #6
Greebley
 
Greebley's Avatar
 
May 2009
Dedham Massachusetts USA

3×281 Posts
Default

Interestingly enough I was trying to figure this out. I went through the sequence from 276 to 5 million that reached 20 digits up to the merge or open end. I calculated the driver, number of digits and whether it stayed with the driver or escaped.

I think made a ratio of stayed/escaped up to 110 digits and did a linear fit of the line, a + bx where x is the number of digits. Note that this only gives a a very rough probability, because it weighs the less dependable high values the same as the lower points with many more data-points. So stopping at different values could give the b for the down=driver from 1.4 to 1.3.

This gives the following:

2^6*127: 127 + 4.6x
2*3: 3 + 4.93x
2^4*31: 31 + 3.06x
2^2*7: 7+ 3.38x
2^3*3*5: 17 + 1.21x
2^5*3*7: 8 + 1.05x
down-driver: -2 + 1.36x
2^3*3: 2 + 0.39x
2^3*3^3*5 : 2 + 0.25
3^5*3^2*7: 1 + 0.27

For ones based on perfect numbers I chose the intecept values. Without this the values were close but not exact - basically the need for 2^6*127 to escape it requires 127^2 which only happens 1/127 even for 0 digits.

These are in order of hardest to easiest to escape. Note that the 2^6 may not have had enough data to be very accurate. For the last driver 2^9*11*31, there were too many 0 exits to calculate this way.

I separated the 2^3*3*5 and 2^5*3*7 by whether the power of 3 was 1 or greater than 1. The reason is that the power of 3 cannot be reduced easily because there are 2 powers of 3 from 2^3*5 (15,6) and from 2^5 (63) terms. 2*3*3^2*5 can only go to 2^3*3*5 if the power of 5 is higher than 1 (same as escaping) and 2^5*3^2*7 cannot go to 2^5*3*7 without changing the power of 2.

My opinion (supported by the numbers above) is that 2^3*3^2*5 and 2^5*3^2*7 are not drivers.

Interestingly, 2^3*3 had a much larger chance of escape than I expected compared to the down-driver. I guess the power of 3 can be higher than 1 adds more chance to escape.
Greebley is offline   Reply With Quote
Old 2012-05-19, 18:46   #7
Greebley
 
Greebley's Avatar
 
May 2009
Dedham Massachusetts USA

3×281 Posts
Default

At 130 digits, 2^4*31 would have 1/430 chance of escape.

It occurs to me another definition of a driver could be based on whether the b from a+bx is greater than or equal 1, rather than the 2 deficit or surplus.

In that case the drivers would be:
2^6*127
2*3
2^4*31
2^2*7
2^3*3^1*5
2^5*3^1*7
down-driver
Higher perfect numbers
(2^9*3*11*31 likely being a driver as well)

but not 2*3*3, 2^3*3^2*5 or 2^5*3*7 which have 3x or greater times the chance to escape.
Greebley is offline   Reply With Quote
Old 2012-05-19, 19:44   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Greebley View Post
It occurs to me another definition of a driver could be based on whether the b from a+bx is greater than or equal 1, rather than the 2 deficit or surplus.
well for the 6p example they gave at one time the formula could be (sigma(x)-x)*p+sigma(x) for any x that you think is a driver ( admittedly this could give you multiple numbers that work for the same part of a sequence or none at all)

take x=25 as an example:

6p+31 if we want this next line to be divisible by 25 what properties of p are needed ?

well 31-25 = 6 so the number left over is 6*(p+1) so p+1 must be a multiple of 6 that is also divisible by 25 gcd(25,6) =1 so p+1 has a minimum of 25 leaving p = 24 mod 25 since half of these are even the p must be 49 mod 50 so for this to persist the prime must be of that form, failure of that form to contain primes shows if the driver can persist across lines.

Last fiddled with by science_man_88 on 2012-05-19 at 19:46
science_man_88 is offline   Reply With Quote
Old 2012-05-20, 19:01   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
well for the 6p example they gave at one time the formula could be (sigma(x)-x)*p+sigma(x) for any x that you think is a driver ( admittedly this could give you multiple numbers that work for the same part of a sequence or none at all)

take x=25 as an example:

6p+31 if we want this next line to be divisible by 25 what properties of p are needed ?

well 31-25 = 6 so the number left over is 6*(p+1) so p+1 must be a multiple of 6 that is also divisible by 25 gcd(25,6) =1 so p+1 has a minimum of 25 leaving p = 24 mod 25 since half of these are even the p must be 49 mod 50 so for this to persist the prime must be of that form, failure of that form to contain primes shows if the driver can persist across lines.
Code:
for(x=7,100,forprime(p=1,1000,print1(((sigma(x)-x)*p+sigma(x))==(sigma(x*p)-(x*p))==0));print(","x))
I like the output but some are repeated in fact I kinda see a pattern in that the ones that end up as one ( because they where 0 start at the first one on multiples of 7 and increase 1 every so often the first connection looks to be the prime gaps. so starts at 7 then 2 out for 11 3 out for 13 next line starts at 14 and continues in a similar fashion but I believe it's a multiple as in the gaps are multiples of the first one.
science_man_88 is offline   Reply With Quote
Old 2012-05-21, 21:58   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Code:
for(x=7,100,forprime(p=1,1000,print1(((sigma(x)-x)*p+sigma(x))==(sigma(x*p)-(x*p))==0));print(","x))
I like the output but some are repeated in fact I kinda see a pattern in that the ones that end up as one ( because they where 0 start at the first one on multiples of 7 and increase 1 every so often the first connection looks to be the prime gaps. so starts at 7 then 2 out for 11 3 out for 13 next line starts at 14 and continues in a similar fashion but I believe it's a multiple as in the gaps are multiples of the first one.
I'm scanning my computer I ran the code and got a different result.
science_man_88 is offline   Reply With Quote
Old 2012-05-22, 10:50   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·3·7·137 Posts
Default

As far as I can work out the chance of losing the p in the next iteration after 2^x*p*comp is(assuming not a driver):
p=3
Code:
Digits  1 in x of losing     1 in x of keeping
60       18.46                1.057
70       19.93                1.053
80       21.30                1.049 
90       22.59                1.046
100      23.81                1.044
110      24.97                1.042
120      26.07                1.040
130      27.14                1.038
140      28.16                1.036
160      30.10                1.034
180      31.92                1.032
p=7
Code:
Digits  1 in x of losing     1 in x of keeping
60       2.628                1.614
70       2.696                1.590
80       2.756                1.569 
90       2.811                1.552
100      2.860                1.538
110      2.906                1.525
120      2.948                1.513
130      2.988                1.503
140      3.025                1.494
160      3.093                1.478
180      3.154                1.464
This explains why losing a 3 is so difficult sometimes. Larger factors disappear much easier. The number of digits you are at also makes quite a difference.
henryzz is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Abortion debate (moved from 2012 election thread) Christenson Soap Box 112 2016-07-01 15:15
DNS Hijack (moved from Server problems thread) c10ck3r Lounge 10 2012-05-18 06:02
PrimeNet API moved? James Heinrich PrimeNet 7 2011-11-25 17:47
Where I should write C code (thread moved) maqableh Programming 9 2006-05-12 16:22
ECMNET page inaccessible (moved) Joe O GMP-ECM 4 2005-03-21 17:39

All times are UTC. The time now is 18:30.

Fri Dec 4 18:30:49 UTC 2020 up 1 day, 14:42, 0 users, load averages: 1.99, 1.63, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.