10
\$\begingroup\$

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
\$\endgroup\$
16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It still says this takes too long, which I think is ridiculous. \$\endgroup\$ – JonnyDoeInWisco Apr 12 '16 at 13:47
  • \$\begingroup\$ "the is_ prefix suggests that it probably returns a boolean" I miss appending ? to boolean functions whenever I go back to Python from Lisp or something \$\endgroup\$ – cat Apr 12 '16 at 21:28
15
\$\begingroup\$

Performance

You can find the solution without any loops:

The xth 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 2nd (since x=2) and 3rd 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
\$\endgroup\$
7
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Could you please elaborate how did you get that candidate? \$\endgroup\$ – Ivan Apr 12 '16 at 13:49
  • \$\begingroup\$ @Ivan, if n = ((i+1)^2 ((i+1)^2 + 1)) / 2 then 2n = (i+1)^2 ((i+1)^2 + 1) = (i+1)^4 + (i+1)^2 which is slightly larger than (i+1)^4. \$\endgroup\$ – Peter Taylor Apr 12 '16 at 14:07
  • 1
    \$\begingroup\$ The solution is absolutely fine. If there is no solution for some n, then it doesn't matter what the value of i is (because the check will fail). If there is a solution i, then i+1 is quite obviously an integer that is just a bit smaller than (2n)^(1/4). \$\endgroup\$ – gnasher729 Apr 12 '16 at 14:21
  • \$\begingroup\$ How to get the candidate: x^2 (x^2 + 1) = 2n. The square root of 2n is between x^2 and x^2 + 1, and x^2 + 1 < (x + 1)^2. Taking the square root again gives a number between x and x+1. Since x is an integer, rounding the square root down gives x. \$\endgroup\$ – gnasher729 Apr 12 '16 at 14:28
  • \$\begingroup\$ Ok, I've caught up with what you are doing (its not clear from the text) - I thought you were calculating the exact value of the xth trangular number from the sum by reversing the calculation but you aren't you only take the process half-way there and then use the fourth-root as an approximation (which you then have to floor) and it then needs to have the square of that triangular number and the next triangular number calculated to test if it is actually correct... It'll work but you could improve the final paragraph to explain the last step and also why you stop using x and use i. \$\endgroup\$ – MT0 Apr 12 '16 at 14:30
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ For some reason this passes all the test cases, but upon submission it says there is a syntax error on line 2. I fixed the parenthesis and it still says it. \$\endgroup\$ – JonnyDoeInWisco Apr 12 '16 at 13:46
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.