CODEWITHSUNDEEP
pythonrecursionsequencepascals-triangleoeis
landee
landee

Reputation: 45

How to obtain n-th even triangle number using recursive algorithm

I know there is a formula for n-th even triangle, but it's just a matter of interest for me to try to write a recursive algorithm.

def even_triangle(n):
    value = n * (n + 1) // 2
    if value % 2 == 0:
        return value
    return even_triangle(n + 1)

for i in range(1, 12):
    print(f"{i})", even_triangle(i))

I tried to write a function which could compute the n-th even triangle number (OEIS A014494), but it turned out that it returns the previous result if the n-th triangle number is odd, but not the next even triangle number as expected.

Output:

1) 6  
2) 6  
3) 6  
4) 10 
5) 28 
6) 28 
7) 28 
8) 36 
9) 66 
10) 66
11) 66

What I expect:

1) 6
2) 10
3) 28
4) 36
5) 66
6) 78
7) 120
8) 136
9) 190
10) 210
11) 276

Upvotes: 3

Views: 88

Answers (3)

lastchance
lastchance

Reputation: 6745

You can also do it by a "double-step" recursion. Not sure if that counts, but it gets to the base case a little faster and reflects the fact that the even triangle numbers come from successive pairs of the actual triangle numbers (3rd/4th; 7th/8th; etc.)

def even_triangle( n ):
    if n <= 1: return 6 * n
    return even_triangle( n - 2 ) + 8 * n - 6 + 4*( n % 2 )

for i in range( 1, 11 ):
    print( even_triangle( i ) )

Output:

6
10
28
36
66
78
120
136
190
210

Upvotes: 1

trincot
trincot

Reputation: 351029

The reason you get duplicates follows from your recursive call:

return even_triangle(n + 1)

When this gets executed, then consequently even_triangle(n) === even_triangle(n + 1), which is not what you ever want to have (since it enforces the duplicate value).

When using recursion, you would typically make a recursive call on a simpler version of the problem (so with a lesser value of n) and then "upgrade" that result with some manipulation to make it suitable for the current value of n.

In this particular case we can see that results come in pairs of standard triangular numbers, then skipping two triangular numbers, and then again a pair, ...etc. That makes me look at a solution where you determine whether the n-th even triangular number is the first one of such a pair, or the second one. If it is the second one, the difference with the preceding n-th even triangular number (got from recursion) is the distance between normal triangular numbers, otherwise the distance is greater.

In short, we can find this recursive relation:

def even_triangle(n):
    if n == 0:
        return 0
    elif n % 2 == 0:
        return even_triangle(n - 1) + 2 * n
    else:
        return even_triangle(n - 1) + 6 * n

As the difference between the two recursive calls is just the factor 2 versus 6, you could produce that factor from n % 2 (i.e. 2 + (n % 2) * 4) and merge those two recursive return statements. The base case can also be merged into it with an and operator:

def even_triangle(n):
    return n and even_triangle(n - 1) + (2 + (n % 2) * 4) * n

As you have already noted yourself, there is a closed formula for this, so using recursion is not the most efficient here.

Upvotes: 3

Frank Yellin
Frank Yellin

Reputation: 11307

You could start of by using the fact that n * (n + 1) // 2 is even iff either n or (n + 1) is divisible by 4. So the numbers you want to plug into that triangle number generator are 0, 3, 4, 7, 8, 11, 12, etc.

So you could write:

def even_triangular(n):
    m = 2 * n if n % 2 == 0 else 2 * n + 1
    return m * (m + 1) // 2

[even_triangular(i) for i in range(10)]
[0, 6, 10, 28, 36, 66, 78, 120, 136, 190]

Upvotes: -3

Related Questions