Week 12 update

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!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s