9-liner: easily up to 10**10000 speedy solution for Ulam–Warburton Automaton by StefanPochmann - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

9-liner: easily up to 10**10000 solution in Speedy category for Ulam–Warburton Automaton by StefanPochmann

def automaton(step: int) -> int:
    total = 0
    mul = 1
    while step:
        m = step.bit_length() - 1
        total += mul << (2*m)
        step -= 1 << m
        mul *= 3
    return total * 4 // 3

March 15, 2023

Comments:

StefanPochmann on March 15, 2023, 3:08 a.m.
Times for 10**10000 and the slowest case up to that: ``` step = 10**10000 0.06 seconds 0.05 seconds 0.05 seconds step = 2**33219-1 0.16 seconds 0.17 seconds 0.17 seconds ``` Benchmark code: <pre class='brush: python'>from time import time def automaton(step: int) -> int: total = 0 mul = 1 while step: m = step.bit_length() - 1 total += mul << (2*m) step -= 1 << m mul *= 3 return total * 4 // 3 for step in '10**10000', '2**33219-1': print('step =', step) step = eval(step) for _ in range(3): t = time() automaton(step) print(f'{time() - t :.2f} seconds') print() </pre>

List, list and list again

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!