Padovan n-step number sequences: Difference between revisions

From Rosetta Code
Content added Content deleted
(New draft task with Python solution)
 
(More OEIS Links)
Line 26: Line 26:
! <math>n</math> !! Values !! [https://oeis.org OEIS] Entry
! <math>n</math> !! Values !! [https://oeis.org OEIS] Entry
|-
|-
| 2 || 1,1,1,2,2,3,4,5,7,9,12,16,21,28,37, ... || A134816: 'Padovan's spiral numbers'
| 2 || 1,1,1,2,2,3,4,5,7,9,12,16,21,28,37, ... || [https://oeis.org/A134816 A134816]: 'Padovan's spiral numbers'
|-
|-
| 3 || 1,1,1,2,3,4,6,9,13,19,28,41,60,88,129, ... || A000930: 'Narayana's cows sequence'
| 3 || 1,1,1,2,3,4,6,9,13,19,28,41,60,88,129, ... || [https://oeis.org/A000930 A000930]: 'Narayana's cows sequence'
|-
|-
| 4 || 1,1,1,2,3,5,7,11,17,26,40,61,94,144,221, ... || A072465: 'A Fibonacci-like model in which each pair of rabbits dies after the birth of their 4th litter'
| 4 || 1,1,1,2,3,5,7,11,17,26,40,61,94,144,221, ... || [https://oeis.org/A072465 A072465]: 'A Fibonacci-like model in which each pair of rabbits dies after the birth of their 4th litter'
|-
|-
| 5 || 1,1,1,2,3,5,8,12,19,30,47,74,116,182,286, ... || A060961: 'Number of compositions (ordered partitions) of n into 1's, 3's and 5's'
| 5 || 1,1,1,2,3,5,8,12,19,30,47,74,116,182,286, ... || [https://oeis.org/A060961 A060961]: 'Number of compositions (ordered partitions) of n into 1's, 3's and 5's'
|-
|-
| 6 || 1,1,1,2,3,5,8,13,20,32,51,81,129,205,326, ... || <not found>
| 6 || 1,1,1,2,3,5,8,13,20,32,51,81,129,205,326, ... || <not found>
|-
|-
| 7 || 1,1,1,2,3,5,8,13,21,33,53,85,136,218,349, ... || A117760: 'Expansion of 1/(1 - x - x^3 - x^5 - x^7)'
| 7 || 1,1,1,2,3,5,8,13,21,33,53,85,136,218,349, ... || [https://oeis.org/A117760 A117760]: 'Expansion of 1/(1 - x - x^3 - x^5 - x^7)'
|-
|-
| 8 || 1,1,1,2,3,5,8,13,21,34,54,87,140,225,362, ... || <not found>
| 8 || 1,1,1,2,3,5,8,13,21,34,54,87,140,225,362, ... || <not found>
|-
|-
|}
|}



<br>
<br>

Revision as of 19:14, 13 March 2021

As the Fibonacci sequence expands to the Fibonacci n-step number sequences; We similarly expand the Padovan sequence to form these Padovan n-step number sequences.

The Fibonacci-like sequences can be defined like this:

   For n == 2:
       start:      1, 1
       Recurrence: R(n, x) = R(n, x-1) + R(n, x-2); for n == 2
   For n == N:
       start:      First N terms of R(N-1, x)
       Recurrence: R(N, x) = sum(R(N, x-1) + R(N, x-2) + ... R(N, x-N))

For this task we similarly define terms of the first 2..n-step Padowan sequences as:

   For n == 2:
       start:      1, 1, 1
       Recurrence: R(n, x) = R(n, x-2) + R(n, x-3); for n == 2
   For n == N:
       start:      First N + 1 terms of R(N-1, x)
       Recurrence: R(N, x) = sum(R(N, x-2) + R(N, x-3) + ... R(N, x-N-1))

The initial values of the sequences are:

Padovan -step sequences
Values OEIS Entry
2 1,1,1,2,2,3,4,5,7,9,12,16,21,28,37, ... A134816: 'Padovan's spiral numbers'
3 1,1,1,2,3,4,6,9,13,19,28,41,60,88,129, ... A000930: 'Narayana's cows sequence'
4 1,1,1,2,3,5,7,11,17,26,40,61,94,144,221, ... A072465: 'A Fibonacci-like model in which each pair of rabbits dies after the birth of their 4th litter'
5 1,1,1,2,3,5,8,12,19,30,47,74,116,182,286, ... A060961: 'Number of compositions (ordered partitions) of n into 1's, 3's and 5's'
6 1,1,1,2,3,5,8,13,20,32,51,81,129,205,326, ... <not found>
7 1,1,1,2,3,5,8,13,21,33,53,85,136,218,349, ... A117760: 'Expansion of 1/(1 - x - x^3 - x^5 - x^7)'
8 1,1,1,2,3,5,8,13,21,34,54,87,140,225,362, ... <not found>


Task
  1. Write a function to generate the first terms, of the first 2..max_n Padovan -step number sequences as defined above.
  2. Use this to print and show here at least the first t=15 values of the first 2..8 -step sequences.
    (The OEIS column in the table above should be omitted).

Python

Generates a wikitable formatted output <lang python>def pad_like(max_n=8, t=15):

   """
   First t terms of the first 2..max_n-step Padowan sequences.
   """
   start = [[], [1, 1, 1]]     # for n=0 and n=1 (hidden).
   for n in range(2, max_n+1):
       this = start[n-1][:n+1]     # Initialise from last
       while len(this) < t:
           this.append(sum(this[i] for i in range(-2, -n - 2, -1)))
       start.append(this)
   return start[2:]

def pr(p):

   print(
.strip()) for n, seq in enumerate(p, 2): print(f"| {n:2} || {str(seq)[1:-1].replace(' ', )+', ...'}\n|-") print('|}') if __name__ == '__main__': p = pad_like() pr(p)</lang>
Output:
Padovan -step sequences
Values
Padovan -step sequences
Values
2 1,1,1,2,2,3,4,5,7,9,12,16,21,28,37, ...
3 1,1,1,2,3,4,6,9,13,19,28,41,60,88,129, ...
4 1,1,1,2,3,5,7,11,17,26,40,61,94,144,221, ...
5 1,1,1,2,3,5,8,12,19,30,47,74,116,182,286, ...
6 1,1,1,2,3,5,8,13,20,32,51,81,129,205,326, ...
7 1,1,1,2,3,5,8,13,21,33,53,85,136,218,349, ...
8 1,1,1,2,3,5,8,13,21,34,54,87,140,225,362, ...