Reserved for MF - Sequence 4788

[VBCurtis]

Originally Posted by RichD

So is it safe to say, "You can't over-sieve your way to less memory requirements."

More sieving -> less memory, yes generally; but we're already assuming enough sieving for a density-140+ matrix. There is a diminishing-returns aspect to extra sieving, and a fuzzily-known bound where more sieving ceases to reduce matrix effort at all (or perhaps it was that a matrix won't even build if one over-over-sieves- that happens on smallish problems somewhat often if a script gets carried away).

[henryzz]

It is always possible to reduce the large prime bound. This should reduce the size of the matrix although it may significantly increase the sieving time.

[Batalov]

[schickel]

Originally Posted by Batalov

The fantastic news is that with it holding steady at 2^3, there has been some downward pressure. What are the odds that the power of 2 will change it the current line [10664] factors into two primes?

[henryzz]

Originally Posted by schickel

The fantastic news is that with it holding steady at 2^3, there has been some downward pressure. What are the odds that the power of 2 will change it the current line [10664] factors into two primes?

Assuming two factors 50% I think. The composite is 1 mod 4. This can be made up of two 1 mod 4 factors or two 3 mod 4 factors. If it is the 1 mod 4 factors we will drop to 2^2 otherwise we will stick with 2^3.

[flagrantflowers]

Originally Posted by henryzz

Assuming two factors 50% I think. The composite is 1 mod 4. This can be made up of two 1 mod 4 factors or two 3 mod 4 factors. If it is the 1 mod 4 factors we will drop to 2^2 otherwise we will stick with 2^3.

And then you need to hit the same again to reduce 2^2 down to 2? And this only works if the split is two factors?

[schickel]

Originally Posted by flagrantflowers

And then you need to hit the same again to reduce 2^2 down to 2? And this only works if the split is two factors?

Actually my question was worded a little wrong: I actually meant what are the odds the power of 2 would go down if it splits into two.

If it splits into three factors, or it factors into two and the math is wrong, there is a chance that the power of 2 can change to something higher than 3.

To get the downdriver you need a line to factor as 2^n * p, with p being of the proper modular form to drop the power of 2 to 1. (Or 2 * 3^n * p, [n even] if you have the 2 * 3 driver; very hard to do!)

In this case, there is no way to get the downdriver on the next line, but maybe we can get a reduction to 2^2 which will help a lot with the size of the composites on each line.

[flagrantflowers]

Originally Posted by schickel

In this case, there is no way to get the downdriver on the next line, but maybe we can get a reduction to 2^2 which will help a lot with the size of the composites on each line.

Thank you, that is a very useful play-by-play. I can't be asked to learn the maths on, but am entertained by following the progress/thread. I mean, I'm try to not get too into numerology lately.

But if I'm understanding. Assuming it splits into two it can be either two 1 mod 4 factors or two 3 mod 4 factors; I would assume the 'odds' would be 1:1?

I'm try to learn.

[Dubslow]

Originally Posted by henryzz

Assuming two factors 50% I think. The composite is 1 mod 4. This can be made up of two 1 mod 4 factors or two 3 mod 4 factors. If it is the 1 mod 4 factors we will drop to 2^2 otherwise we will stick with 2^3.

In general, flagrantflowers, if you write the line as:

2^b * (q1^k1 * q2^k2 * q3^k3)^2 * (p1 * p2 * p3)

...you can use the following rules to determine any possible mutations:

1) Ignore any primes whose power is even (like the q's above)

2) For the remaining primes, we'll assume they have no power, since getting a prime cubed (or higher) is extraordinarily unlikely (except for small primes like 3 or 5 or 7).

3) Look at the power of 2 that divides p+1 for each prime p.

4) If the sum of those powers is greater than b, no mutation will occur.

5) If the sum of those powers is exactly b, then the power b will increase (an upwards mutation).

6) If the sum of those powers is less than b, then the power will be reduced to this lower sum (a downwards mutation).

Since all primes are odd (except 2 of course), p+1 automatically is even, so each prime contributes at least 1 power of two. To a zeroth order approximation, half of primes+1 are divisible by two and not four, a quarter of all primes+1 are divisible by four but not eight, and an eighth of all primes are divisible by eight but not sixteen, etc.

So right now, we have 2^3 * C, where C has no small factors and is thus likely to split into two (large) factors p1 and p2 (or rather less likely, three factors p1 p2 and p3).

We know that C is 1 mod 4. Therefore, since 1*3 = 3 mod 4, we know that both of its factors are either both 1 or both 3 mod 4 -- but it can't be that one is 1 mod 4 and the other is 3 mod 4.

If they are both 1 mod 4, then we know that p1+1 and p2+1 are 2 mod 4, hence their power of two is precisely 1 (since they are not 0 mod 4, their power of two can't be 2 or more), for a total power of two of 2. Thus, 2 < b=3, so by rule 6) we would mutate from 2^3 * p1 * p2 to 2^2 * ...., and 2^2 is "better" in the sense that it's less abundant than 2^3, i.e. each line goes down more.

If they are both 3 mod 4, then p1+1 and p2+1 would be 0 mod 4, so they each have a power of two of at least 2, so the total power of two would be at least 4, which is more than b=3, so no mutation would occur.

To zeroth order approximation, it's about equally likely that they are both 1 or both 3 mod 4, so around a 50% chance this line mutates to 2^2 or stays at 2^3.

As schickel mentioned, with these rules you can see that the only way to get 2^1, as necessary for the downdriver, is to get a line 2^b * (primes to even power) * p, where p is 1 mod 4, so that the power of two in p+1 is only 1, whence by rule 6) we get 2^1.

For details on the why of these rules, see my page here (and let me know if something confuses you )

[henryzz]

Something that we have both ignored is that a prime can be 7 mod 8. This doesn't particularly affect this case since we are dealing with 2^3 with C = 1 mod 4. However, in other situations such as with C = 3 mod 4, it is necessary to consider mod 8 or above as is done at the top of Dubslow's last post.
It is also worth noting that 5) needs adjusting for primes other than 2. I think that the correct statement is:
5) If the sum of those powers is exactly b, then the power b will increase (an upwards mutation) with probability 1/(p-1).
This is due to N and sigma(N) having to match mod p^n(assuming we are mutating from p^(n-1) to p^n). We already know that neither are 0 mod p^n but are 0 mod p^(n-1) so the probability is 1/(p-1) rather than 1/p. This is just 1 for p=2 which makes the original statement correct for p=2.

[Dubslow]

I was only talking about the power of 2, yes.