For the record, Stormbringer's solution is slightly less than sqrt(n) in the worst case. floor((k * k + k)/2) = n; solve for k to get approximately sqrt(2 * n)

For the record, Stormbringer's solution is slightly less than sqrt(n) in the worst case. floor((k * k + k)/2) = n; solve for k to get approximately sqrt(2 * n) The (Sqrt(n) * 2)-1 solution is less efficient, but only by a roughly constant factor of approximately sqrt(2). (14 vs 19, when n=100) Patio11's binary+linear algorithm is almost certainly the inefficient solution that the blogger hinted at. Patio11 claims to have coded an even more efficient solution, but has not explained it. I for one suspect his supposedly more efficient solution has a bug, but I have not inspected or tested his code.