After rereading my last post, I was still frustrated by not having a constant-time solution.
Well… after spending a couple more hours on it, I have one!
from math import sqrt def ideal_i(n: int): return round(sqrt((2 * n) + 1)) - 1
I knew that in my previous solution, the number of times we loop must be derivable from n itself without actually performing the loop. There was still some “naivety”. Even though we’d avoided brute force calculation of i, we were still waiting to satisfy a condition.
I realized that this problem is very similar to that story where Gauss figures out that to find the sum of the numbers from 1 to x, you do a fancy thingy with lining them up. We’ll omit the part where my math sucks and I spend a couple of hours fiddling with that. I eventually found this: sum = x(y + x)/2, where x is the number of terms to add and y is the first element. That lets us start at 2: n = x(2 + x)/2. Luckily, a “solve for x” website gave me the x = sqrt(2n+1) equivalent.* Which we want to round.
Now we know how many times we would have incremented i, which means we have i.
Just to be sure, I tested the two versions using this helpful old strategy:
all(ideal_i(x) == ideal_i_2(x) for x in range(1,10000))
Satisfaction! Someone should update Wikipedia with how to calculate i given four stools. I’m sure that’s where all of us looked first, only to realize that it doesn’t know the answer either.
That said, we should remember that removing the naivety of the original formula gives us a huge advantage in speed, but means we have to have faith that the pattern repeats infinitely.
(P.S. My real last post! Adieu.)
*zingarod later showed me the algebraic steps to get from one to the other. Thanks!