So, from today's bright idea,:

$ python ./Ulam.py

time to generate 100 numbers (U (2, 5)) is 0.00426

time to generate 1000 numbers (U (2, 5)) is 0.03167

time to generate 10000 numbers (U (2, 5)) is 0.22796

time to generate 100000 numbers (U (2, 5)) is 1.44548

time to generate 1000000 numbers (U (2, 5)) is 14.71493

time to generate 100 numbers (U (2, 7)) is 0.00214

time to generate 1000 numbers (U (2, 7)) is 0.01558

time to generate 10000 numbers (U (2, 7)) is 0.15068

time to generate 100000 numbers (U (2, 7)) is 1.43910

time to generate 1000000 numbers (U (2, 7)) is 14.62419

time to generate 100 numbers (U (2, 9)) is 0.00245

time to generate 1000 numbers (U (2, 9)) is 0.01770

time to generate 10000 numbers (U (2, 9)) is 0.15190

time to generate 100000 numbers (U (2, 9)) is 1.45868

time to generate 1000000 numbers (U (2, 9)) is 14.93112

time to generate 100 numbers (U (2, 11)) is 0.00211

time to generate 1000 numbers (U (2, 11)) is 0.01602

time to generate 10000 numbers (U (2, 11)) is 0.15409

time to generate 100000 numbers (U (2, 11)) is 1.49055

time to generate 1000000 numbers (U (2, 11)) is 15.08445

...

time to generate 100 numbers (U (2, 21)) is 0.00486

time to generate 1000 numbers (U (2, 21)) is 0.03741

time to generate 10000 numbers (U (2, 21)) is 0.25073

time to generate 100000 numbers (U (2, 21)) is 1.78683

time to generate 1000000 numbers (U (2, 21)) is 17.9669

(Sequences U(2,5) and U(2,7) verified against the On-Line Encyclopedia of Integer Sequences (to 1000 elements))

The period detection and related footwork is still missing, but with a linear time growth, the problem looks much more doable.

So, the bright idea:

Looking at various articles, it's mentioned several times that Scherml and Speigel proved that "The sequence (2, v) for odd v >= 5 had precisely 2 even terms".

It can also be shown that the second even number occurs fairly early in the sequence.

Since we're dealing with sequences of that form, after the initial terms to reach the second even term, the candidate numbers we're dealing with must be odd. Generating the new candidates is thus trivial, and, with a little housekeeping, the list of candidates to consider can be kept short on every loop.

I'm not sure whether to feel chuffed about spotting this, or annoyed that I didn't spot this earlier.

## No comments:

Post a Comment