Finding two consecutive triangular numbers with a given target sum

Question

I need to speed up this code so it can handle inputs in the thousands. It adds triangular numbers to a list based on input n, then it loops through to find if any two consecutive numbers squared in that list add up to n. The test cases I've been using are n = 45, which would be true and n = 6, which would be false.

Here is the code:

def Triangular(n):
    lst = []
    for i in range(1, n + 1):
        lst.append((i** 2 + i)//2)

    for i in lst:
        for j in lst:
            if i*i + j*j == n and ((lst.index(i) == lst.index(j)+1) 
                               or (lst.index(i) == lst.index(j)-1)):
                return True
            else:
                continue

Answer 1

A few suggestions:

• Explicitly return False if the condition fails, i.e., if there aren’t two triangular numbers that sum to n.

  As it stands, your function with either return True or None.

• Don’t store the first n triangular numbers in a list; check them as you go through.

  For large n, you’ll be creating a very large list, which will slow down Python. And the vast majority of the numbers in that list will be greater than n, so cannot possibly sum with a consecutive triangular number squared to give n.

  This is much more efficient:

  for i in range(1, n + 1):
      # If T_1 = i (i+1) / 2 and T_2 = (i+1) (i+2) / 2 then
      # we have
      # T_1^2 + T_2^2 = (i+1)^2 [i^2 + (i+2)^2] / 4
      result = (i+1)**2 * (i**2 + (i+2)**2) / 4
      if result == n:
          return True
      elif result > n:
          return False
  

  We’re not storing lots of numbers in a list, and we’re only going until it’s impossible to find a working combination.

  On my fairly weedy old laptop, this can take O(10^7) input and finish in under a second.

• Use a better function name, and write a docstring.

  Per PEP 8, function names in Python should be lowercase_with_underscores; your CamelCase function gives the impression of being a class.

  And Triangular isn’t a very helpful name – if I saw that being called, I’d probably assume it was returning the nth triangular number. Something like

  def is_consecutive_triangular_square_sum(n):
  

  doesn’t roll off the tongue as nicely, but it’s never going to be confused for getting triangular numbers, and the is_ prefix suggests that it probably returns a boolean.

  You should also write a docstring, which explains what the function is supposed to do. Useful for interactive help and/or people reading your code.

Answer 2

Performance

You can find the solution without any loops:

The x^th triangle number is given by:

$$\frac{x(x+1)}{2}$$

So the sum n of the square of two consecutive triangular numbers is given by:

$$\begin{align} n & = \left(\frac{x(x+1)}{2}\right)^2 + \left(\frac{(x+1)(x+2)}{2}\right)^2 \\ & = \frac{x^2(x+1)^2 + (x+1)^2(x+2)^2}{4}\\ & = \frac{(x+1)^2(2x^2+4x+4)}{4} \\ & = \frac{(x+1)^2(x^2+2x+1 + 1)}{2} \\ & = \frac{(x+1)^2((x+1)^2 + 1)}{2} \\ \text{let } i = (x+1)^2 \implies n & = \frac{i(i+1)}{2} \\ \Leftrightarrow 0 & = i^2 + i - 2n \end{align}$$

Then using the quadratic formula:

$$\begin{align}i=\frac{-1 + \sqrt{1+8n}}{2}\\ \implies x = \sqrt{\frac{-1 + \sqrt{1+8n}}{2}} - 1 \end{align}$$

If n = 45 then

$$ x = \sqrt{\frac{-1 + \sqrt{1+8 \cdot{} 45 }}{2}}-1 = 2$$

Which is an integer so n=45 is a valid sum of the square of the 2^nd (since x=2) and 3^rd triangular numbers.

If n = 6 then

$$ x = \sqrt{\frac{-1 + \sqrt{1+8 \cdot{} 6 }}{2}}-1 = \sqrt{3} -1$$

Which is not an integer so n=6 is not a valid sum of the squares of two consecutive triangular numbers.

Python Code

import math

def IsSumOfConsecutiveTriangularNumbersSquared(n):
  x = math.sqrt((math.sqrt(1+8*n)-1)/2)-1
  return x == math.floor(x)

print 45, IsSumOfConsecutiveTriangularNumbersSquared(45)
print 6, IsSumOfConsecutiveTriangularNumbersSquared(6)
print 3092409168985, IsSumOfConsecutiveTriangularNumbersSquared(3092409168985)

Output

45 True
6 False
3092409168985 True

Answer 3

When performance is the issue, it's always worth looking at the algorithm.

    for i in lst:
        for j in lst:

is a doubly-nested loop, so it's going to be quadratic in some parameter. (In this case, the parameter is n).

alexwlchan's answer uses a single loop, so it's going to be linear in some parameter. (In this case the parameter is the fourth root of n, because of the early break from the loop).

But taking the algebraic transformation one step further, $$\left(\frac{x(x+1)}{2}\right)^2 + \left(\frac{(x+1)(x+2)}{2}\right)^2 = \frac{(x+1)^2 ((x+1)^2 + 1)}{2}$$

so if you're looking for an \$i\$ such that \$n\$ is the sum of the squares of the \$i\$th triangle number and the \$(i+1)\$th triangle number, the only candidate you need to consider is $$i = \lfloor\sqrt[4]{2n} - 1\rfloor$$ and the code is essentially constant-time (until you start dealing with numbers big enough that multiplying them can't be considered constant-time).

For a practical implementation, the root taking and test could be split into two. Note that this is pseudocode because I don't speak Python:

def is_consecutive_triangular_square_sum(n):
    # t = (i+1)^2
    t = int(sqrt(2*n))
    if (t * (t + 1) != 2 * n): return False
    # s = i+1; I assume the risk of numerical error causing sqrt(t) to be just below an integer
    s = int(sqrt(t) + 0.5)
    return (s * s == t)

Answer 4

Besides the efficient solution by alexwlchan, I'd like to also make some suggestions.

Creating the list

You use

lst = []
for i in range(1, n + 1):
    lst.append((i** 2 + i)//2)

Shorter and more efficient would be

lst = [(i ** 2 + i) // 2 for i in range(1, n+1)]

(But you actually don't need to store the list.)

Checking positions

Notice how you check lst.index. That makes that the statement in the inner loop is only true for at most 2 entries in the entire list. But lst.index needs to search through the list, which is not that fast.

for i in lst:
    for j in lst:
        if i*i + j*j == n and ((lst.index(i) == lst.index(j)+1) 
                           or (lst.index(i) == lst.index(j)-1)):
            return True
        else:
            continue

Either i < j or i > j. If i > j, swapping the roles of i and j would give i < j, and (thus) would have shown up earlier in the iteration. So you only need to check the first condition, as that's always the one to be triggered.

for i in lst:
    for j in lst:
        if i*i + j*j == n and lst.index(i) == lst.index(j)+1:
            return True
        else:
            continue

Now this only helps a little bit. What we actually want is to get rid of the inner loop.

for idx, i in enumerate(lst):
    try:
        j = lst[idx + 1]
    except IndexError:
        continue

    if i*i + j*j == n:
        return True

Now, I'm not a fan of the try/except here. But that's because we used a list.

Getting rid of the list

def t(n):
    return (n ** 2 + n) // 2

def is_consecutive_triangular_square_sum(n):
    # Blatantly stealing name from alexwlchan
    for i in range(1, n + 1):
        if t(i)**2 + t(i+1)**2 == n:
            return True
    return False

This has the downside of calling t multiple times for each i. But we could get rid of that if performance is paramount (which it probably isn't, but let's presume it is!)

Optimised

def is_consecutive_triangular_square_sum(n):
    ts = ((i**2 + i)//2 for i in range(1, n+1))
    t_prev = next(ts)
    for t_next in ts:
        if t_prev * t_prev + t_next * t_next == n:
            return True
        t_prev = t_next
    return False

And short-circuiting to stop early.

def is_consecutive_triangular_square_sum(n):
    ts = ((i**2 + i)//2 for i in range(1, n+1))
    t_prev = next(ts)
    for t_next in ts:
        squared_sum = t_prev * t_prev + t_next * t_next
        if squared_sum == n:
            return True
        elif squared_sum > n:
            # At this point, all squares will be larger anyway
            # since the squared-sum is ever-increasing.
            break
        t_prev = t_next
    return False

Answer 5

A more general solution: Let f (x) be an increasing function of x (in this case, f (x) is the square of the x-th triangular number), and we want to find an integer i such that f (i) + f (i + 1) = n.

We solve f (x) = n/2 for real numbers x, and let i = floor (x). Then we check whether i is a solution: If f (i) + f (i + 1) = n, then i is the only solution, otherwise there is no solution.

Why? Since f (x) is increasing, f (i) ≤ n/2 (it is equal if x was an integer), and f (i + 1) > n/2. The sum of f (j) + f (j + 1) for any j > i is greater than 2 * (n/2) = n. The sum for any j < i is less than 2 * (n/2) = n, therefore i is the only possible solution.

This method handles rounding errors quite well: If f (x) is reasonably smooth then f (x) = n/2 for some x quite close to i + 1/2. So even if we calculate x with some error, i = floor (x) will likely be the correct value.

If it is hard to find the exact solution of f (x) = n/2, then we can find i = floor (x) for some approximate solution x; as long as f (i) + f (i + 1) > n we know i is too large and decrease by 1; then as long as f (i) + f (i + 1) < n we know i is too small and increase i by 1, and then we either found the correct i or there is none.