Fastest way to find nearest triangle number?
Question: In python I need a function that takes an integer and returns the absolute
value of n minus the nearest [triangle
number](http://en.wikipedia.org/wiki/Triangular_number) to n. The way I'm
doing it now is by generating a list of all the triangle numbers up to n. Then
using:

    
    
    def closest(myList, myNumber):
        c = min(myList, key=lambda x:abs(x-myNumber))
    

To find the closest triangle number.

The end result list should look like:

    
    
    [0, 0, 1 , 0 , 1 ,1 , 0 , 1, 2 , 1, 0 , 1, 2, 2, 1, 0, etc.]
    

If you have another method of generating the same result that's faster go for
it.


Answer: A little bit of math will bring a more analytical solution:

    
    
    from math import sqrt
    def close_triangle2(n):
        m=int(0.5*(-1+sqrt(1+8*n))) #solve it for the explicit formula
        tan0=(m*m+m)/2              #the closest one is either this
        tan1=(m*m+3*m+2)/2          #or this
        if (n-tan0)>(tan1-n):
            return tan1-n
        else:
            return n-tan0
    

It will become slightly faster than the loop version from @perreal when the
number is large:

    
    
    In [87]:
    
    %timeit close_triangle(111111111)
    100000 loops, best of 3: 5 µs per loop
    In [86]:
    
    %timeit close_triangle2(111111111)
    100000 loops, best of 3: 4.13 µs per loop
    

If you wonders:

    
    
    In [94]:
    
    close_triangle2((30**10 * (30**10+1)) / 2 + 100)
    Out[94]:
    100L
    In [95]:
    
    close_triangle((30**10 * (30**10+1)) / 2 + 100)
    Out[95]:
    100L
    
    In [102]:
    
    %timeit close_triangle((30**10 * (30**10+1)) / 2 + 100)
    10000 loops, best of 3: 17.9 µs per loop
    In [103]:
    
    %timeit close_triangle2((30**10 * (30**10+1)) / 2 + 100)
    100000 loops, best of 3: 12 µs per loop
    

