Padovan sequence

Try me

The Padovan sequence is the following infinite sequence of natural numbers: 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 ...

The sequence begins with the subsquence \([1, 1, 1]\) and then each term is the sum of two terms before the last one, that is:

\(P(0) = 1\)

\(P(1) = 1\)

\(P(2) = 1\)

\(P(n) = P(n-2) + P(n-3)\)

The Padovan sequence is a cousin of the Fibonacci sequence and has many applications in applied mathematics. As a curiosity, the Padovan sequence can be represented as a set of joined equilateral triangles forming an spiral:

Recall that in Python, the last elements of the array can be accessed directly using negative indices, for example, array[-1] would be the last element of the array, array [-2] the second to last, and so on. Also, remember that the append() function, adds an element to the end of the array.

With everything explained so far, develop the following program:

A program that asks the user for a length and generates a Padovan sequence of that length, stores it in an array and prints the array.

Solution

Flow chart

The following flow chart represents a possible solution to the problem:

We can generate a Padovan sequence with 4 elements as:

pad = [1, 1, 1]
next_val = pad[-2] + pad[-3]
pad.append(next_val)

Note that the value that we have added does not depend on the length of the array, but on the last two elements of the array. Therefore, we can use a loop to generate the sequence of any length.

Also, in Python, we can use the while loop to iterate while a certain condition is not met. We can use this type of loop to generate a Padovan sequence with a given length, using the len function in the condition to compare the actual length of the array with the value provided by the user.

Code

This is the code of the solution:

# Get length of sequence to generate from input
padovan_len = int(input("enter length of sequence: "))
# Init Padovan sequence array
pad = [1, 1, 1]

# While the length of the sequence is smaller than the input
while len(pad) < padovan_len:
    # Calculate the next value as the sum of the two values before the last one
    next_val = pad[-2] + pad[-3]
    # Append the new value to the array
    pad.append(next_val)

print(pad)