Return to Answer

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)

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)

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 take $$i = \lfloor\sqrt[4]{2n} - 1\rfloor$$ then you just need to test one candidate value, 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)

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)

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 take $$i = \lfloor\sqrt[4]{2n} - 1\rfloor$$ then you just need to test one candidate value, and the code is essentially constant-time (until you start dealing with numbers big enough that multiplying them can't be considered constant-time).

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 take $$i = \lfloor\sqrt[4]{2n} - 1\rfloor$$ then you just need to test one candidate value, 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)