The previous post stated a formula for f(n), the nth square triangular number (i.e. the nth triangular number that is also a square number):
((17 + 12√2)n + (17 – 12√2)n – 2)/32
Now 17 – 12√2 is 0.029… and so the term (17 – 12√2)n approaches zero very quickly as n increases. So the f(n) is very nearly
((17 + 12√2)n – 2)/32
The error in the approximation is less than 0.001 for all n, so the approximation is exact when rounded to the nearest integer. So the nth square triangular number is
⌊((17 + 12√2)n +14)/32⌋
where ⌊x⌋ is the greatest integer less than x.
Here’s how you might implement this in Python:
from math import sqrt, floor def f(n): x = 17 + 12*sqrt(2) return floor((x**n + 14)/32.0)
Unfortunately this formula isn’t that useful in ordinary floating point computation. When n = 11 or larger, the result is needs more bits than are available in the significand of a floating point number. The result is accurate to around 15 digits, but the result is longer than 15 digits.
The result can also be computed with a recurrence relation:
f(n) = 34 f(n-1) – f(n-2) + 2
for n > 2. (Or n > 1 if you define f(0) to be 0, a reasonable thing to do).
This only requires integer arithmetic, so it’s only limitation is the size of the integers you can compute with. Since Python has arbitrarily large integers, the following works for very large integers.
def f(n): if n < 2: return n return f(n-1)*34 - f(n-2) + 2
This is a direct implementation, though it’s inefficient because of the redundant function evaluations. It could be made more efficient by, for example, using memoization.