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