mersenneforum.org Escaping drivers (moved from 4788 thread)
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2012-05-14, 10:02   #1
schickel

"Frank <^>"
Dec 2004
CDP Janesville

212210 Posts
Escaping drivers (moved from 4788 thread)

Quote:
 Originally Posted by R. Gerbicz 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 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....

 2012-05-15, 18:15 #2 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 575410 Posts 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.
2012-05-15, 19:44   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by henryzz 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.

2012-05-15, 20:53   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by science_man_88 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,

 2012-05-18, 13:08 #5 LaurV Romulan Interpreter     Jun 2011 Thailand 100011000000112 Posts 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
 2012-05-19, 18:36 #6 Greebley     May 2009 Dedham Massachusetts USA 3×281 Posts 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.
 2012-05-19, 18:46 #7 Greebley     May 2009 Dedham Massachusetts USA 3×281 Posts 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.
2012-05-19, 19:44   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Greebley 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

2012-05-20, 19:01   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by science_man_88 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.

2012-05-21, 21:58   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 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.

 2012-05-22, 10:50 #11 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 2·3·7·137 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Christenson Soap Box 112 2016-07-01 15:15 c10ck3r Lounge 10 2012-05-18 06:02 James Heinrich PrimeNet 7 2011-11-25 17:47 maqableh Programming 9 2006-05-12 16:22 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