A113028

[pmb]

A while back, I poked at a diverting math problem for a bit, and then ended up submitting it to The online encyclopedia of integer sequences where it got accepted. At the same time, it lit a fire in jes5199's brain. Now it has mutated into some kind of crazy bizarro super speed demon of something: ( Read more... )

Comments

[jes5199]

and that's in Ruby. It goes about twice as fast if i use YARV's miniruby

but then i get stuck. i keep saying there are no more breakthroughs to find... and i think it's probably true now.

[conform]

i wrote an implementation yesterday which can now do up to 22 on a slow machine with no compiler optimizations in less than four tenths of a second.

[conform]

i should note that my implementation is just combining the two approaches that josh and paul implemented, and adding two optimizations that jesse came up with. and the code is a mess. but... can't argue with results.

[conform]

also, the crazy thing is how few lexical permutations i actually look at:

base 3: 1 iterations
base 4: 2 iterations
base 5: 2 iterations
base 6: 6 iterations
base 7: 3 iterations
base 8: 17 iterations
base 9: 97 iterations
base 10: 9 iterations
base 11: 3 iterations
base 12: 46 iterations
base 13: 74 iterations
base 14: 40 iterations
base 15: 58 iterations
base 16: 36942 iterations
base 17: 1022 iterations
base 18: 279 iterations
base 19: 1091 iterations
base 20: 3172 iterations
base 21: 1170 iterations
base 22: 1717 iterations

real 0m0.367s
user 0m0.352s
sys 0m0.009s

!!??!

[pmb]

You PDX coders are insane.

[chocolatesmudge]

All I have to say about this is: Damn you, Peter Boothe.

[mycrust]

How do these algorithms work?

[pmb]

Voodoo, near as I can tell. I feel like I should let jes5199, conformpdx, j3h, and stereotype441 do the explaining, as they figured it out and understand it best.

[conform]

there are several approaches. how much detail do you want?

[mycrust]

Not so much that it makes either my head or your fingers hurt.

[conform]

32 and 33 are in my post now.