This may actually be feasible now

With CTPUG 14 in the near future, and two failed attempts to tackle the Ulam seuqence problem from the previous meetings, I decided to give the problem some thought today.

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.