Found period 32, difference 126

time to generate 200000 numbers (U (2, 5)) is 0.37129

time to generate 2000000 numbers (U (2, 5)) is 3.66487

time to generate 20000000 numbers (U (2, 5)) is 38.38641

Found period 26, difference 126

time to generate 200000 numbers (U (2, 7)) is 0.36446

time to generate 2000000 numbers (U (2, 7)) is 4.06793

time to generate 20000000 numbers (U (2, 7)) is 44.24620

Found period 444, difference 1778

time to generate 200000 numbers (U (2, 9)) is 0.40023

time to generate 2000000 numbers (U (2, 9)) is 5.73586

time to generate 20000000 numbers (U (2, 9)) is 38.33744

Found period 1628, difference 6510

time to generate 200000 numbers (U (2, 11)) is 0.41977

time to generate 2000000 numbers (U (2, 11)) is 3.65161

time to generate 20000000 numbers (U (2, 11)) is 37.85133

Found period 5906, difference 23622

time to generate 200000 numbers (U (2, 13)) is 0.65191

time to generate 2000000 numbers (U (2, 13)) is 3.69802

time to generate 20000000 numbers (U (2, 13)) is 36.82868

Found period 80, difference 510

time to generate 200000 numbers (U (2, 15)) is 0.36584

time to generate 2000000 numbers (U (2, 15)) is 3.61351

time to generate 20000000 numbers (U (2, 15)) is 37.08529

time to generate 200000 numbers (U (2, 17)) is 4.52874

Found period 126960, difference 507842

time to generate 2000000 numbers (U (2, 17)) is 7.54118

time to generate 20000000 numbers (U (2, 17)) is 39.30235

time to generate 200000 numbers (U (2, 19)) is 4.54097

Found period 380882, difference 1523526

time to generate 2000000 numbers (U (2, 19)) is 35.07058

time to generate 20000000 numbers (U (2, 19)) is 36.92766

time to generate 200000 numbers (U (2, 21)) is 4.10050

time to generate 2000000 numbers (U (2, 21)) is 43.80197

Found period 2097152, difference 8388606

time to generate 20000000 numbers (U (2, 21)) is 456.09959

There's a bunch of improvements that can be made to the code - especially the periodicity check is not that efficient, and tends to repeat work which could be avoided. This bites for the U(2, 21) sequence, for which the direct approach presented earlier can calculate 20000000 elements in around 290 seconds, but the overall problem is now something that can be solved in "reasonable" time periods

Presented without further comment.

# time python ./solve_167.py

Answer = <answer redacted, but confirmed correct>

real 7m15.052s

user 6m41.213s

sys 0m15.365s

## 2 comments:

Nice! If I'd seen your previous post earlier, I'd've lent you my period checker. Is your code available anywhere? I'd like to see how you sped up the sequence generation.

I'd didn't do my usual trick of creating a repository for this stuff immediately, since I had originally only intended to confirm that the answer was indeed correct. Since I ended up solving 30 problems over the weekend [1], that really went according to plan.

Still, it's never to late to correct that (Git repo).

[1] There 31 solutions currently, but since I only finished 207 this morning after an idea in the shower, that doesn't count for the weekend.

Post a Comment