DEV Community

Baltasar García Perez-Schofield
Baltasar García Perez-Schofield

Posted on • Edited on

Padawan's sequence

#mathematics #sequence #padovan #programming

Today I learned about the Padovan sequence, which is defined as follows:

p[0] = 1
p[1] = 1
p[2] = 1
p[n] = p[n - 2] + p[n - 3]
Enter fullscreen mode Exit fullscreen mode

This is like the Fibonacci's succession, only misplaced. The last element is ignored, only to be taken by the next computation.

Let's implement the Padovan sequence in Python:

def padovan_seq(n: int) -> list[int]:
    toret = []

    if n > 0:
        match n:
            case 0:
                toret = [1]
            case 1:
                toret = [1, 1]
            case 2:
                toret = [1, 1, 1]
            case _:
                toret = padovan_seq(n - 1)
                toret += [toret[-2] + toret[-3]]
    ...

    return toret
...


if __name__ == "__main__":
    print("Padovan sequence")
    print(str.join(", ", (str(x) for x in padovan_seq(100))))
...
Enter fullscreen mode Exit fullscreen mode

The output is:

Padovan sequence
1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, 351, 465, 616, 816, 1081, 1432, 1897, 2513, 3329, 4410, 5842, 7739, 10252, 13581, 17991, 23833, 31572, 41824, 55405, 73396, 97229, 128801, 170625, 226030, 299426, 396655, 525456, 696081, 922111, 1221537, 1618192, 2143648, ...
Enter fullscreen mode Exit fullscreen mode

Oh, and what's in the title? What a Padawan of Star Was has to do with all of this? Plainly nothing. Clickbait, I'm afraid.

Yeah, I'm that silly.

Top comments (3)

Collapse
 
canro91 profile image
Cesar Aguirre •

Thanks for sharing Baltasar, I had no idea about this succession. It's like a stubborn Fibonacci sequence :P

Collapse
 
baltasarq profile image
Baltasar García Perez-Schofield •

Sure!! It seems to be something like Fibonacci. It is curious that you can obtain the Perrin succession if you apply the same mechanism but start with different values:

P(0) = 3
P(1) = 0
P(2) = 2
P(n) = P(n − 2) + P(n − 3)
Enter fullscreen mode Exit fullscreen mode

BTW, did you know about the OEIS database?

Collapse
 
canro91 profile image
Cesar Aguirre • • Edited

BTW, did you know about the OEIS database?

:O Not at all...Now I know where to find ideas for passwords :)