Computing the Padovan Sequence in Java

1. Overview

A Padovan sequence is a Fibonacci-like pattern in which the second and third preceding terms determine each term. Introduced by Richard Padovan in the 1990s (and earlier studied by others), it appears in architecture, natural growth patterns, and combinatorics, especially in counting certain tilings and geometric designs. It’s popular because, like Fibonacci, it links simple rules to surprising structures.

Thus, because it’s similar to Fibonacci, we can use the same approaches to find it, and, consequently, we would have the same pitfalls to avoid. In this tutorial, we will consider possible ways to generate the sequence and their tradeoffs. While there are options to use the Stream API or create generators to produce values lazily, we won’t consider them due to the implementation complexity and readability.

2. The Padovan Sequence

The Padovan numbers P(n) are defined by the recurrence:

P(n) = P(n-2) + P(n-3), with P(0) = P(1) = P(2) = 1.

Thus, we can use this formula to create the first terms: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, …

Padovan numbers occur in combinatorics (e.g., counting certain tilings and words), in geometry, architecture, and in growth models. As we can see, it’s pretty similar to Fibonacci, which uses F(n) = F(n-1) + F(n-2); Padovan uses P(n) = P(n-2) + P(n-3), which makes it a slower-growing sequence.

3. Recursive Approaches

The simplest option to go for is a recursive approach; it’s not very practical, but since it’s a common way people familiarize themselves with recursion, it might be a good way to start:

public static int nthPadovanTermRecursiveMethod(int n) {
    if (n == 0 || n == 1 || n == 2) {
        return 1;
    }
    return nthPadovanTermRecursiveMethod(n - 2) + nthPadovanTermRecursiveMethod(n - 3);
}

However, it’s important to understand that we should use this solution only for educational purposes. This solution is very inefficient and would result in O(2^n) time complexity and linear space complexity (to maintain the call stack). We can reduce the time complexity by introducing memoization, which would reduce it to O(n):

public static int nthPadovanTermRecursiveMethodWithMemoization(int n) {
    if (n == 0 || n == 1 || n == 2) {
        return 1;
    }
    int[] memo = new int[n + 1];
    memo[0] = 1;
    memo[1] = 1;
    memo[2] = 1;
    return nthPadovanTermRecursiveMethodWithMemoization(n, memo);
}

private static int nthPadovanTermRecursiveMethodWithMemoization(int n, int[] memo) {
    if (memo[n] != 0) {
        return memo[n];
    }
    memo[n] = nthPadovanTermRecursiveMethodWithMemoization(n - 2, memo)
      + nthPadovanTermRecursiveMethodWithMemoization(n - 3, memo);
    return memo[n];
}

While we made some progress, the solution is still pretty slow and uses unnecessary space.

4. Iterative Approaches

However, using recursion for such problems is a gimmick and shouldn’t be used in production or any code that requires performance. Thus, we can try to use an iterative solution to address this problem:

public static int nthPadovanTermIterativeMethodWithArray(int n) {
    int[] memo = new int[n + 1];
    if (n == 0 || n == 1 || n == 2) {
        return 1;
    }
    memo[0] = 1;
    memo[1] = 1;
    memo[2] = 1;
    for (int i = 3; i <= n; i++) {
        memo[i] = memo[i - 2] + memo[i - 3];
    }
    return memo[n];
}

In this case, we use the same idea, but instead of recursive calls, we use an array to hold previous values. While there are no complexity improvements over the previous approach (the time and space complexities remain linear), we can use this as a stepping stone for further improvements. It’s easy to see that we need only three numbers:

public static int nthPadovanTermIterativeMethodWithVariables(int n) {
    if (n == 0 || n == 1 || n == 2) {
        return 1;
    }
    int p0 = 1, p1 = 1, p2 = 1;
    int tempNthTerm;
    for (int i = 3; i <= n; i++) {
        tempNthTerm = p0 + p1;
        p0 = p1;
        p1 = p2;
        p2 = tempNthTerm;
    }
    return p2;
}

It’s a pretty nice improvement: we still have linear time complexity, but the space complexity was reduced to a constant.

5. Binet-like Formula

However, we can reduce the complexity even more and use a simple formula. The ratio of the numbers is constant, so we don’t need to do any complex operations at all:

public static int nthPadovanTermUsingFormula(int n) {
    if (n == 0 || n == 1 || n == 2) {
        return 1;
    }

    // Padovan spiral constant (plastic number) - the real root of x^3 - x - 1 = 0
    final double PADOVAN_CONSTANT = 1.32471795724474602596;
    
    // Normalization factor to approximate Padovan sequence values
    final double NORMALIZATION_FACTOR = 1.045356793252532962;
    
    double p = Math.pow(PADOVAN_CONSTANT, n - 1); 
    return (int) Math.round(p / NORMALIZATION_FACTOR);
}

This approach would calculate any n-th number in constant time; however, it uses approximation. Thus, it’s important to account for any issues and use more decimal places, for example, using BigDecimal.

6. Conclusion

As for the Fibonacci sequence, we can calculate the Padovan sequence in many different ways. Each of them has its own benefits and shortcomings (even if we talk about simplicity and educational properties). Thus, we can pick the best suitable one, based on the requirements we have in front of us.

As usual, all the code from this tutorial is available over on GitHub.