Padovan n-step number sequences: Difference between revisions
Content added Content deleted
(More OEIS Links) |
(Add Factor) |
||
Line 46: | Line 46: | ||
# Write a function to generate the first <math>t</math> terms, of the first <code>2..max_n</code> Padovan <math>n</math>-step number sequences as defined above. |
# Write a function to generate the first <math>t</math> terms, of the first <code>2..max_n</code> Padovan <math>n</math>-step number sequences as defined above. |
||
# Use this to print and show here at least the first <code>t=15</code> values of the first <code>2..8</code> <math>n</math>-step sequences.<br> (The [https://oeis.org OEIS] column in the table above should be omitted). |
# Use this to print and show here at least the first <code>t=15</code> values of the first <code>2..8</code> <math>n</math>-step sequences.<br> (The [https://oeis.org OEIS] column in the table above should be omitted). |
||
=={{header|Factor}}== |
|||
{{works with|Factor|0.99 2021-02-05}} |
|||
<lang factor>USING: compiler.tree.propagation.call-effect io kernel math |
|||
math.ranges prettyprint sequences ; |
|||
: padn ( m n -- seq ) |
|||
V{ "|" 1 1 1 } over prefix clone over 2 - |
|||
[ dup last2 + suffix! ] times rot pick 1 + - |
|||
[ dup length 1 - pick [ - ] keepd pick <slice> sum suffix! ] |
|||
times nip ; |
|||
"Padovan n-step sequences" print |
|||
2 8 [a..b] [ 15 swap padn ] map simple-table.</lang> |
|||
{{out}} |
|||
<pre> |
|||
Padovan n-step sequences |
|||
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 |
|||
</pre> |
|||
=={{Header|Python}}== |
=={{Header|Python}}== |
Revision as of 22:53, 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
- Write a function to generate the first terms, of the first
2..max_n
Padovan -step number sequences as defined above. - Use this to print and show here at least the first
t=15
values of the first2..8
-step sequences.
(The OEIS column in the table above should be omitted).
Factor
<lang factor>USING: compiler.tree.propagation.call-effect io kernel math math.ranges prettyprint sequences ;
- padn ( m n -- seq )
V{ "|" 1 1 1 } over prefix clone over 2 - [ dup last2 + suffix! ] times rot pick 1 + - [ dup length 1 - pick [ - ] keepd pick <slice> sum suffix! ] times nip ;
"Padovan n-step sequences" print 2 8 [a..b] [ 15 swap padn ] map simple-table.</lang>
- Output:
Padovan n-step sequences 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
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, ...
- .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>