Escaping drivers (moved from 4788 thread)

[schickel]

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.

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:

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:

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....

[henryzz]

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:

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:

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.

[science_man_88]

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 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]

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 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,

[LaurV]

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

.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

[Greebley]

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]

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.

[science_man_88]

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.

[science_man_88]

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.

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]

Originally Posted by science_man_88

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.

[henryzz]

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

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

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.