Fun with LL residues

[NBtarheel_33]

Originally Posted by axn

Your original specification didn't call for 5 repeating 'A's, it called for 5 repeating hexits, including 00000, 11111, ..., FFFFF.

Indeed it didn't. No wonder Serge thought I had lost my marbles!

[Madpoo]

Originally Posted by NBtarheel_33

A residue of 0x2 is LL Hell (HeLL, perhaps?). Square 2, subtract 2, you get 2. Square 2, subtract 2, you get 2. And on and on and on...

True dat.

I wonder how to explain residues like the ones in:
M64847711
M47359579

And spoiler alert, because I'm sure that one for M47359579 is bogus, the masked byte is also FF. If one of y'all submits a bogus result now with all FF's, I'll know.

There's also this one:
M3370013

The masked byte is FE.

On the other hand, we have some actual winners like:
M15721967
M13708351

and a couple real beauties:
M10268009
M21642389

I found verified residues starting with 5 hexit runs for each hexit except for 4's, 6's, 9's, B's and F's.

There are probably cases of runs of those in the residue, but anyone familiar with SQL knows it takes longer to do a '%x%' match than a 'x%' match and I didn't want to bog down the server.
(EDIT: Never mind, I created an index on the residue column and checked... a few more runs of 6 in a row, but none with 7 or more)

[Batalov]

Originally Posted by Madpoo

I wonder how to explain residues like the ones in:
And spoiler alert, because I'm sure that one for M47359579 is bogus, the masked byte is also FF. If one of y'all submits a bogus result now with all FF's, I'll know.

FFFFFFFFFFFFFFFF residue is -1; it happens when the memory is zeroed in by a hardware glitch (or memory/buffer overrun?) with the lowest limb set not to 0 but to 1. Then 1^2-2 = -1, and then -1 is repeated until the end of the calculation. This is the second most probable outcome after 0000000000000002. -1 and 2 are the two solutions for x^2 - 2 = x, hence two cycles.

Originally Posted by Madpoo

There's also this one:
M3370013

The masked byte is FE.

FFFFFFFFFFFFFFFE residue is -2. Could happen if the penulitmate iteration gets zeroed in. 0^2-2 = -2.

[Madpoo]

Originally Posted by Batalov

FFFFFFFFFFFFFFFF residue is -1; it happens when the memory is zeroed in by a hardware glitch (or memory/buffer overrun?) with the lowest limb set not to 0 but to 1. Then 1^2-2 = -1, and then -1 is repeated until the end of the calculation. This is the second most probable outcome after 0000000000000002. -1 and 2 are the two solutions for x^2 - 2 = x, hence two cycles.

FFFFFFFFFFFFFFFE residue is -2. Could happen if the penulitmate iteration gets zeroed in. 0^2-2 = -2.

Would it be safe to say then that certain residues are mathematically impossible, and could only be achieved through some bad math somewhere along the way? Or is there a slim chance, however improbable, of something like that actually being a real residue?

Reason being, we might as well mark weird things like that as bad right away (or at least "suspect"), and if that was the first-time LL check, assign it back out for a new first time check rather than wait for the double-checking to catch up to it.

For my part, a few months back I tried to find weird residues like that which were waiting on a double or triple check and cleared them out but I missed some others like the 0xFFFFF... stuff.

And maybe there are other weird and implausible residues that we might mark as suspect right away and reassign as a first-time check to someone else? Preferably not the same person?

[retina]

Originally Posted by Madpoo

Would it be safe to say then that certain residues are mathematically impossible, and could only be achieved through some bad math somewhere along the way? Or is there a slim chance, however improbable, of something like that actually being a real residue?

Since we are only seeing the last 64 bits then any value is a plausible residue.

[Batalov]

Right. Essentially this convolution is a random number generator* with very good distribution properties. If one needed a stream of random bits, the whole state of the residue is an excellent source of it (for the prime modulo; maybe less perfect for a typical run modulo a composite Mersenne number, but still, "government-job"-grade random for sure). The full-length residue is a PRNG, and any bit (or a stretch of 64 bits) is independently PRNG as a vector along iterations as time.

To add to that, I have posted some examples some time ago, that produce a 0000000000000000 RES64 with the answer "not prime" (there are non-zero higher bits, but 64 lower bits are all zero, and all three programs are aware of that and will report "not prime"); that should be possible to find. Granted, those were not LL-, but PRP- residues.

I also remember a thread where people were pondering if a legitimately total zero residue is possible for an iteration less than p-th (or beyond, if we'd let the iterations continue). I don't remember if there was an answer. I thought it was a no. Clearly even if it ever happened, one could stop iterations because the final answer will be "2", but checking that the full residue is all zeroes is a computational expense. It is been done, but only relatively rarely, iirc.

We can check if there ever was a double- triple- checked residue =2. That used to be a no and is still a no, I gather from earlier posts.
__________________
* The M-Twister is not doing LL, though. Maybe it could ;-)

[axn]

Originally Posted by Batalov

The odds of having a string of five repeating hexits is ~ 1/16^4 * (number of sub-5-strings in a 14-string = 10), or 1 in ~ 6500.
______________
* This is an estimate of course and that's why I rounded the number, but it is accurate enough. The precise estimate should take into account that sub-5-strings are not independent (they overlap).

So I went ahead and computed the actual number.

Using dynamic programming, I get the count of patterns as 3184078216197616, giving a probability of 1:5793

EDIT:- This is for the 16 char case. For 14 char strings, the count is 10376414887936, giving a probability of 1:6944

[Anonuser]

Originally Posted by axn

So I went ahead and computed the actual number.

Using dynamic programming, I get the count of patterns as 3184078216197616, giving a probability of 1:5793

EDIT:- This is for the 16 char case. For 14 char strings, the count is 10376414887936, giving a probability of 1:6944

It might be worth to mention that one can also use rather simple recursive formulas to compute these values (see the attached pdf-file).

[axn]

Originally Posted by Anonuser

It might be worth to mention that one can also use rather simple recursive formulas to compute these values (see the attached pdf-file).

This is what I used for dynamic programming (but too lazy for writing it up) Thank you.