Expressing an integer as the sum of triangular numbers
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