mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2018-02-27, 22:58   #441
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by swellman View Post
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.
Dubslow is offline   Reply With Quote
Old 2018-02-28, 18:36   #442
Brownfox
 
Brownfox's Avatar
 
Dec 2017

32×7 Posts
Default

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
Brownfox is offline   Reply With Quote
Old 2018-02-28, 20:43   #443
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

121116 Posts
Default

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?).
VBCurtis is offline   Reply With Quote
Old 2018-02-28, 22:05   #444
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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"
Dubslow is offline   Reply With Quote
Old 2018-03-01, 07:45   #445
Brownfox
 
Brownfox's Avatar
 
Dec 2017

32·7 Posts
Default

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.
Brownfox is offline   Reply With Quote
Old 2018-03-01, 17:41   #446
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

53×37 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2018-03-01, 20:21   #447
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100001101012 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.)

Last fiddled with by Dubslow on 2018-03-01 at 20:30
Dubslow is offline   Reply With Quote
Old 2018-03-04, 17:59   #448
Brownfox
 
Brownfox's Avatar
 
Dec 2017

32·7 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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
Brownfox is offline   Reply With Quote
Old 2018-03-05, 00:22   #449
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by Brownfox View Post
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,

Quote:
Originally Posted by Dubslow View Post
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.
Dubslow is offline   Reply With Quote
Old 2018-03-07, 17:44   #450
Brownfox
 
Brownfox's Avatar
 
Dec 2017

32·7 Posts
Default

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
Brownfox is offline   Reply With Quote
Old 2018-03-07, 18:25   #451
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by Brownfox View Post
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?
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reserved for MF - Sequence 4788 schickel Aliquot Sequences 2934 2021-01-07 18:52
Reserved for MF - Sequence 3366 RichD Aliquot Sequences 463 2021-01-02 16:01
Reserved for MF - Sequence 276 kar_bon Aliquot Sequences 127 2020-12-17 10:05
Team Sieve #37: 3408:i1287 RichD Aliquot Sequences 14 2013-08-02 17:02
80M to 64 bits ... but not really reserved petrw1 Lone Mersenne Hunters 82 2010-01-11 01:57

All times are UTC. The time now is 14:43.

Mon Jan 25 14:43:29 UTC 2021 up 53 days, 10:54, 0 users, load averages: 2.69, 2.57, 2.47

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