Expressing an integer as the sum of triangular numbers

Problem 621

Gauss famously proved that every positive integer can be expressed as the sum of three triangular numbers (including 0 as the lowest triangular number前几个三角数是0,1,3,6,10,15,即三角型的面积n(n+1)/2). In fact most numbers can be expressed as a sum of three triangular numbers in several ways.

Let G(n) be the number of ways of expressing n as the sum of three triangular numbers, regarding different arrangements of the terms of the sum as distinct.

For example, G(9)=7 , as 9 can be expressed as: 3+3+3, 0+3+6, 0+6+3, 3+0+6, 3+6+0, 6+0+3, 6+3+0. You are given G(1000)=78 and G(106)=2106 .

Find G(17526×109 ) .

def g(n):
t=[i*(i+1)//2 for i in range(1+int(math.sqrt(n*8+1)/2-1/2))]
le=len(t)
c=0
for i in range(le):
if t[i]+t[i]+t[i]>n:break
hi=le
for j in range(i,le):
if t[i]+t[j]+t[j]>n:break
lft=bisect.bisect_left(t,n-t[i]-t[j],j,hi )
if lft<hi and t[lft]==n-t[i]-t[j]:
hi=lft
if i ==j:
if j==lft:
c+=1
else:
c+=3
else:
if j==lft:
c+=3
else:
c+=6
return c