Padovan numbers (2 points)

The Padovan integer sequence (or Padovan numbers) is defined as:

\(x_0 = 1, x_1 = 0, x_2 = 0, x_{i} = x_{i-2} + x_{i-3}, i \geq 3\)

The first Padovan numbers are the following:

1, 0, 0, 1, 0, 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, ...

Write function padovan() that takes an integer (int) and returns a tuple with the first three consecutive Padovan numbers such that its summation is greater than the given integer.

Save this function in file padovan.py.

Examples:

>>> padovan(8)
(2, 3, 4)
>>> padovan(11)
(3, 4, 5)
>>> padovan(110)
(28, 37, 49)

Note

More tests are provided in file test-padovan.txt.