Python program to print Aitken’s array

In this short tutorial, we will see what an Aitken’s array is and then write a program in Python to print Aitken’s array. Let’s get started.

Aitken’s Array in Python

Aitken’s array is like a triangle of numbers. The first row of the array contains only one element which is 1. The next row starts with the last value of the previous row. The second value of a row is given by the sum of the first element of the row and the element of the previous row at the same position. The third element of the row is given by the sum of the second element of the row and the element of the previous row at the same position. The same rule is for the fourth element and so on.

The number of rows is specified by the user. Each successive row has one extra element than the previous row, hence it makes a triangular structure. For example, for 4 rows, the array will look like this-

[1]
[1 2]
[2 3 5]
[5 7 10 15]

 Code to Print Aitken’s Array

From the pattern of the array, it is obvious that we will have to use either recursion or dynamic programming. Recursion for a larger number of repetitions is very resource-intensive and you might as well run out of memory. To avoid this and get faster results, we will go with the dynamic programming technique with memoization. For this purpose, we will use @lru_cache decorator to cache the previously computed values. These values can be used by future subproblems without having to recompute them.

Let’s see the code to print Aitken’s array for 6 rows

from functools import lru_cache

@lru_cache()
def atiken(n):
    # Base case:
    if n == 1:
        print([1])
        return [1]
    
    atiken_array = [atiken(n-1)[-1]]
    
    for k in range(n-1):
        atiken_array.append(atiken_array[k] + atiken(n-1)[k])
        
    print(atiken_array)
    return atiken_array

# Function call
atiken(6)

[1]
[1, 2]
[2, 3, 5]
[5, 7, 10, 15]
[15, 20, 27, 37, 52]
[52, 67, 87, 114, 151, 203]