Reserved for MF - Sequence 3408

[Dubslow]

Originally Posted by swellman

I remember Serge writing this. I’m ignorant of aliquot theory - any idea on how many iterations would be required before 3408 turns? 150 or more like 800? Just curious.

Obligatory plug for my way-too-in-depth theory page. Ideally should be easily accessible to anyone with a little basic college math -- hopefully, substantially more accessible than even the number theory discussion group.

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.

[Brownfox]

I had already done some calculations based on sequence 1667820 where the composites were 90-110 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 co-factor 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 90-110 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

[VBCurtis]

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 200-digit seq vs a 100-digit. That gives us an expected ~1000 terms to lose the driver, though a 50% chance of losing it would be much much sooner (right?).

[Dubslow]

Originally Posted by VBCurtis

I'm inclined to think the chances of prime cofactor is inverse to length, so your second probability would be about half for a 200-digit seq vs a 100-digit.

Sounds right. We're asking, for n digits, how many of those n digit numbers are prime? Which is to say, we're asking what (pi(b) - pi(a))/(b-a) is, for b=10a -- or, more precisely, what pi'(b) is. Of course pi(x) is famously ~ x/logx, so pi'(x) ~ (logx-1)/log^2 x) ~ 1/log x. Theoretically, measuring how many prime cofactors exist for a given size should be measuring pi'(x) ~ 1/log x. Actually, re-reading, pi(x) is closer approximated by Li(x), where Li is of course the integral of 1/logx. So really pi(x) ~ x/logx is actually an approximation to the better statement that pi'(x) ~ 1/logx.

tl;dr is "yes you just quoted the PNT"

[Brownfox]

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.

[VBCurtis]

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.

[Dubslow]

Originally Posted by VBCurtis

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.

The computation can be performed in an analogous way to the power of 2. Let "threes count of x" refer the the largest power of 3 that divides sigma(x) (such that, e.g., the threes count of 11 is 1 [sigma(11) = 12 = 3*4]).

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 non-3 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.)

[Brownfox]

Originally Posted by VBCurtis

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.

Having done a bit of counting and calculation I've come to the conclusion that increasing the size of the number of digits doesn't actually make a significant difference to these probabilities. Yes, it reduces the chance of getting another 3 initially, but it also reduces the chance of losing it once it's there, and as far as I can work out, these cancel out in the long term.

So an acceptable working assumption is probably that an n-digit number takes of the order of 5n iterations to escape from the 2.3 driver.

Hope that helps
Steve

[Dubslow]

Originally Posted by Brownfox

Having done a bit of counting and calculation I've come to the conclusion that increasing the size of the number of digits doesn't actually make a significant difference to these probabilities. Yes, it reduces the chance of getting another 3 initially, but it also reduces the chance of losing it once it's there, and as far as I can work out, these cancel out in the long term.

So an acceptable working assumption is probably that an n-digit number takes of the order of 5n iterations to escape from the 2.3 driver.

Hope that helps
Steve

Hi Steve,

Originally Posted by Dubslow

So if the cofactor n/(2*3) has "m" total squarefree prime factors....

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

With your dataset and scripts, would you be willing to do a measurement of the rough distribution of this "m"? That is, how often a 100 digit cofactor has 1 non-powered factor, or 2 non-powered factors, etc? I could use that measurement together with the rough theory from before to put together a rough estimate of how often the D1 should get another 3. Hopefully, it will match your measured data.

Thanks.

[Brownfox]

My approximation for cofactors with 90-110 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

[Dubslow]

Originally Posted by Brownfox

My approximation for cofactors with 90-110 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

Excellent, thanks! Just to clarify, does this count only unpowered primes or any primes to a nonunit power as well?