Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
46-liner: using integer factorization solution in 3rd party category for Saw the Stick by przemyslaw.daniel
'''
We can try to express every number as a
difference of two sums of triangular numbers
1(1+1)/2 + 1(2+1)/2 + ... + x(x+1)/2 = x(x+1)(x+2)/6
n = a(a+1)(a+2)/6 - b(b+1)(b+2)/6
6n = a(a+1)(a+2) - b(b+1)(b+2)
6n = (a-b)(a^2+ab+3a+b^2+3b+2)
which means a-b must divide 6n
All we have to do is to find positive root of
a^2+ab+3a+b^2+3b+2 = 6n/d (d - divisor)
and calculate a and b based on a-b = d.
Complexity depends on prime factoization algorithm
complexity mutiplied by amount of divisors of a given
number. Sympy module uses pollard rho/p-1, for example rho method
has O(n^1/4) complexity
There is a space for improvement. We can combine factoring method
with triangular verfifcation as we can find correct divisor before
finding all of them
Due to float number precision it is better to implement own sqrt
function for big integers
'''
def int_sqrt(n):
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x if x*x == n else None
def checkio(n):
from sympy import divisors
for d in divisors(6*n)[::-1]:
k = int_sqrt(3*(-d*(d**3-4*d-24*n)))
if not k:
continue
a = (k+3*d**2-6*d)/(6*d)
b = a-d
if b >= 0 and a == int(a):
return [x*(x+1)//2 for x in range(int(b)+1, int(a)+1)]
return []
Oct. 26, 2018
Comments: