20180227, 22:58  #441  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
Quote:
Anyways, breaking 2*3 requires getting the 3 to an even power, then the remaining cofactor must simultaneously be a prime which is 1 mod 4 (well, you can also have other primes with even powers  even powers are great for guide mutations). Essentially, getting an even power on the 3 makes it otherwise the same as the downdriver (while the even power of 3 persists). Odds of getting 2*3^2*P, P==1 mod 4, are pretty slim. Perhaps 1/3*1/2*(odds of getting a downdriver on a random guide). Not good. Sidenote: defining "driver" to be "class <= 1", while perhaps convenient for human discussions, doesn't really make sense IMO. Much more logical to divide the guides into "those which require an even power of v" and "those which don't" would make more sense. 

20180228, 18:36  #442 
Dec 2017
3^{2}×7 Posts 
I had already done some calculations based on sequence 1667820 where the composites were 90110 digits.
I'm not a mathematician so I don't claim they're in any way rigorous but it came out as: Chance of getting to an even power of 3 is 0.024 But there is then a risk every subsequent iteration of losing the even power of 3 with probability 0.057. If we do have an even power of 3, then the chance of getting an iteration where the cofactor is a prime of the form 4n+1 is 0.0069. So the average number of iterations would be of the order of 1/0.0069 * (0.057+0.024)/0.024 = 490. That's for 90110 digits remember. By the time you get to the sizes of composites you're talking about, the average number of iterations required will be considerably larger still. Hope that's of interest. Happy to provide further details if anyone is interested (but I did say I am not a mathematician!) Steve 
20180228, 20:43  #443 
"Curtis"
Feb 2005
Riverside, CA
1001000010001_{2} Posts 
Steve
This is just the sort of estimate we're curious about. If you're able, could you provide those numbers for two different sizes, say 90 and 110 digits? Ideally, we'd want to estimate each probability as a function of the number of digits in the sequence N, but that's a big ask. I'm inclined to think the chances of prime cofactor is inverse to length, so your second probability would be about half for a 200digit seq vs a 100digit. That gives us an expected ~1000 terms to lose the driver, though a 50% chance of losing it would be much much sooner (right?). 
20180228, 22:05  #444  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Quote:
tl;dr is "yes you just quoted the PNT" 

20180301, 07:45  #445 
Dec 2017
77_{8} Posts 
Curtis
I can have a go at the weekend  too much RL before then. The key in all the probabilities is the distribution of the number of factors  how likely it is to have 1, 2, 3 etc factors (other than 2 and 3) in each iteration. I don't know a way of calculating this, so I ended up counting 200+ examples and assuming that distribution was typical. I'll do the same for a few different sizes to get an indication of how it changes. 
20180301, 17:41  #446 
"Curtis"
Feb 2005
Riverside, CA
4625_{10} Posts 
I think that 'counting factors' is summarized by the probability the 2*3^2 cofactor is prime, which we're comfortable estimating via prime number theorem (per the post before yours).
I'm not at all comfortable estimating the probability a 2*3 gains another 3, nor do I know how that changes with number of digits. 
20180301, 20:21  #447  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
7221_{10} Posts 
Quote:
Consider the sum (or difference) of two numbers x and y (or, for instance, the difference between sigma(n) and n). If x and y have different powers of 3 (not the "threes count", no sigma here), then the power of 3 in their sum/difference is equal to the lesser of the two powers of 3 in x and y. Therefore, the sum cannot have a higher power of 3 than x or y. So we can eliminate that case for considering increases in the power of 3. On the other hand, if x and y share the same power of 3, then the sum has the same power of 3 times the sum of the two non3 portions of the sum. If those two portions add up to a multiple of 3, then the power of 3 will increase. Those two portions can each individually be 1 or 2 mod 3, so their sum is 0 mod 3 with probability 1/2. The power of 3 that divides this sum is ~random, I believe, so after the 1/2, then 2/3 odds you get on factor of 3, 2/9 odds you get a factor of 9, 2/27 odds you get a factor of 27, etc. So the odds that we get a 3^2 in this case is about 1/2*2/3 = 1/3, with a 1/9 chance of getting 3^3, 1/27 chance of getting 3^4, etc. So, given a 2*3 driver, with a base power of 3 in n being 1, we then require that sigma(n) be 1 as well per the above paragraph, i.e. the threes count of n is 1. Only after this do the 1/9 odds of getting 3^2 apply. The threes count of both 2 and 3 is zero (though not so their higher powers), so they can be ignored; powers of primes larger than 3 also have a threes count of zero (since 2*2 = 1*1 = 1 mod 3). I assume that the primes are roughly evenly distributed between 1 and 2 mod 3 (as they are roughly evenly distributed between 1 and 3 mod 4). So if the cofactor n/(2*3) has "m" total squarefree prime factors, then each contributes a roughly 1/2 chance of having a threes count of (at least) 1. We want a threes count of exactly 1, to trigger the circumstances of the previous paragraph, so we want exactly 1 head in m coin flips, which occurs with probability m/2^m. So the overall odds of getting a 3^2 is m/(3*2^m), while the overall odds of getting any even power of 3 is m/(2^m*(3 + 27 + 243 + ...)) = 3m/2^(m+3) (since 1/(3+27+243+...) = 3/8). The distribution of the number of squarefree primes in a random integer not divisible by 6 is left as an exercise for the reader. (That means it's substantially harder than what I just wrote, and I haven't a clue about how to go about calculating it.) Last fiddled with by Dubslow on 20180301 at 20:30 

20180304, 17:59  #448  
Dec 2017
3^{2}·7 Posts 
Quote:
So an acceptable working assumption is probably that an ndigit number takes of the order of 5n iterations to escape from the 2.3 driver. Hope that helps Steve 

20180305, 00:22  #449  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
1C35_{16} Posts 
Quote:
Quote:
Thanks. 

20180307, 17:44  #450 
Dec 2017
3^{2}×7 Posts 
My approximation for cofactors with 90110 digits  to be taken with a large pinch of salt as it is only based on some 200 examples so the deviation from the actual expectation is likely to be large  is as follows:
Number of factors other than 2 or 3 Expectation (%) 1 1.4% 2 2.8% 3 13.8% 4 24.4% 5 23.5% 6 15.7% 7 8.8% 8 6.0% 9 2.3% 10 0.9% 11 0.5% Hope that helps Steve 
20180307, 18:25  #451  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Reserved for MF  Sequence 4788  schickel  Aliquot Sequences  2934  20210107 18:52 
Reserved for MF  Sequence 3366  RichD  Aliquot Sequences  463  20210102 16:01 
Reserved for MF  Sequence 276  kar_bon  Aliquot Sequences  127  20201217 10:05 
Team Sieve #37: 3408:i1287  RichD  Aliquot Sequences  14  20130802 17:02 
80M to 64 bits ... but not really reserved  petrw1  Lone Mersenne Hunters  82  20100111 01:57 