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]
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))))
...
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, ...
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.
Thanks for sharing Baltasar, I had no idea about this succession. It's like a stubborn Fibonacci sequence :P