Padovan n-step number sequences: Difference between revisions
m (→{{header|REXX}}: simplified the code.) |
(→{{header|C}}: Simpler.) |
||
Line 147: | Line 147: | ||
{{trans|Wren}} |
{{trans|Wren}} |
||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
#include <stdlib.h> |
|||
void padovanN(int n, size_t t, int *p) { |
void padovanN(int n, size_t t, int *p) { |
||
Line 164: | Line 163: | ||
int main() { |
int main() { |
||
int n, i; |
int n, i; |
||
size_t t = 15; |
const size_t t = 15; |
||
int |
int p[t]; |
||
printf("First %ld terms of the Padovan n-step number sequences:\n", t); |
printf("First %ld terms of the Padovan n-step number sequences:\n", t); |
||
for (n = 2; n <= 8; ++n) { |
for (n = 2; n <= 8; ++n) { |
||
Line 174: | Line 173: | ||
printf("\n"); |
printf("\n"); |
||
} |
} |
||
free(p); |
|||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
Revision as of 19:22, 15 March 2021
You are encouraged to solve this task according to the task description, using any language you may know.
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).
ALGOL 68
<lang algol68>BEGIN # show some valuies of the Padovan n-step number sequences #
# returns an array with the elements set to the elements of # # the Padovan sequences from 2 to max s & elements 1 to max e # # max s must be >= 2 # PROC padovan sequences = ( INT max s, max e )[,]INT: BEGIN PRIO MIN = 1; OP MIN = ( INT a, b )INT: IF a < b THEN a ELSE b FI; # sequence 2 # [ 2 : max s, 1 : max e ]INT r; FOR x TO max e MIN 3 DO r[ 2, x ] := 1 OD; FOR x FROM 4 TO max e DO r[ 2, x ] := r[ 2, x - 2 ] + r[ 2, x - 3 ] OD; # sequences 3 and above # FOR n FROM 3 TO max s DO FOR x TO max e MIN n + 1 DO r[ n, x ] := r[ n - 1, x ] OD; FOR x FROM n + 2 TO max e DO r[ n, x ] := 0; FOR p FROM x - n - 1 TO x - 2 DO r[ n, x ] +:= r[ n, p ] OD OD OD; r END # padovan sequences # ; # calculate and show the sequences # [,]INT r = padovan sequences( 8, 15 ); print( ( "Padovan n-step sequences:", newline ) ); FOR n FROM 1 LWB r TO 1 UPB r DO print( ( whole( n, 0 ), " |" ) ); FOR x FROM 2 LWB r TO 2 UPB r DO print( ( " ", whole( r[ n, x ], -3 ) ) ) OD; print( ( newline ) ) OD
END</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
ALGOL W
<lang algolw>begin % show some valuies of the Padovan n-step number sequences %
% sets R(i,j) to the jth element of the ith padovan sequence % % maxS is the number of sequences to generate and maxE is the % % maximum number of elements for each sequence % % maxS must be >= 2 % procedure PadovanSequences ( integer array R ( *, * ) ; integer value maxS, maxE ) ; begin integer procedure min( integer value a, b ) ; if a < b then a else b; % sequence 2 % for x := 1 until min( maxE, 3 ) do R( 2, x ) := 1; for x := 4 until maxE do R( 2, x ) := R( 2, x - 2 ) + R( 2, x - 3 ); % sequences 3 and above % for N := 3 until maxS do begin for x := 1 until min( maxE, N + 1 ) do R( N, x ) := R( N - 1, x ); for x := N + 2 until maxE do begin R( N, x ) := 0; for p := x - N - 1 until x - 2 do R( N, x ) := R( N, x ) + R( N, p ) end for_x end for_N end PadovanSequences ; integer MAX_SEQUENCES, MAX_ELEMENTS; MAX_SEQUENCES := 8; MAX_ELEMENTS := 15; begin % calculate and show the sequences % % array to hold the Padovan Sequences % integer array R ( 2 :: MAX_SEQUENCES, 1 :: MAX_ELEMENTS ); % construct the sequences % PadovanSequences( R, MAX_SEQUENCES, MAX_ELEMENTS ); % show the sequences % write( "Padovan n-step sequences:" ); for n := 2 until MAX_SEQUENCES do begin write( i_w := 1, s_w := 0, n, " |" ); for x := 1 until MAX_ELEMENTS do writeon( i_w := 3, s_w := 0, " ", R( n, x ) ) end for_n end
end.</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
C
<lang c>#include <stdio.h>
void padovanN(int n, size_t t, int *p) {
int i, j; if (n < 2 || t < 3) { for (i = 0; i < t; ++i) p[i] = 1; return; } padovanN(n-1, t, p); for (i = n + 1; i < t; ++i) { p[i] = 0; for (j = i - 2; j >= i - n - 1; --j) p[i] += p[j]; }
}
int main() {
int n, i; const size_t t = 15; int p[t]; printf("First %ld terms of the Padovan n-step number sequences:\n", t); for (n = 2; n <= 8; ++n) { for (i = 0; i < t; ++i) p[i] = 0; padovanN(n, t, p); printf("%d: ", n); for (i = 0; i < t; ++i) printf("%3d ", p[i]); printf("\n"); } return 0;
}</lang>
- Output:
First 15 terms of the Padovan n-step number 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
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
Go
<lang go>package main
import "fmt"
func padovanN(n, t int) []int {
if n < 2 || t < 3 { ones := make([]int, t) for i := 0; i < t; i++ { ones[i] = 1 } return ones } p := padovanN(n-1, t) for i := n + 1; i < t; i++ { p[i] = 0 for j := i - 2; j >= i-n-1; j-- { p[i] += p[j] } } return p
}
func main() {
t := 15 fmt.Println("First", t, "terms of the Padovan n-step number sequences:") for n := 2; n <= 8; n++ { fmt.Printf("%d: %3d\n", n, padovanN(n, t)) }
}</lang>
- Output:
First 15 terms of the Padovan n-step number 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]
Julia
<lang julia> """
First nterms terms of the first 2..max_nstep -step Padowan sequences.
""" function nstep_Padowan(max_nstep=8, nterms=15)
start = [[], [1, 1, 1]] # for n=0 and n=1 (hidden). for n in 2:max_nstep this = start[n][1:n+1] # Initialise from last while length(this) < nterms push!(this, sum(this[end - i] for i in 1:n)) end push!(start, this) end return start[3:end]
end
function print_Padowan_seq(p)
println(strip("""
-
"""))
for (n, seq) in enumerate(p)
println("| $n || $(replace(string(seq[2:end]), r"[ a-zA-Z\[\]]+" => "")), ...\n|-")
end
println("|}")
end
print_Padowan_seq(nstep_Padowan())
</lang>
- Output:
Padovan -step sequences Values Padovan -step sequences Values 1 1,1,2,2,3,4,5,7,9,12,16,21,28,37, ... 2 1,1,2,3,4,6,9,13,19,28,41,60,88,129, ... 3 1,1,2,3,5,7,11,17,26,40,61,94,144,221, ... 4 1,1,2,3,5,8,12,19,30,47,74,116,182,286, ... 5 1,1,2,3,5,8,13,20,32,51,81,129,205,326, ... 6 1,1,2,3,5,8,13,21,33,53,85,136,218,349, ... 7 1,1,2,3,5,8,13,21,34,54,87,140,225,362, ...
-
"""))
for (n, seq) in enumerate(p)
println("| $n || $(replace(string(seq[2:end]), r"[ a-zA-Z\[\]]+" => "")), ...\n|-")
end
println("|}")
end
print_Padowan_seq(nstep_Padowan())
</lang>
Phix
<lang Phix>function padovann(integer n,t)
if n<2 or t<3 then return repeat(1,t) end if sequence p = padovann(n-1, t) for i=n+2 to t do p[i] = sum(p[i-n-1..i-2]) end for return p
end function
constant t = 15,
fmt = "%d: %d %d %d %d %d %d %d %2d %2d %2d %2d %2d %3d %3d %3d\n"
printf(1,"First %d terms of the Padovan n-step number sequences:\n",t) for n=2 to 8 do
printf(1,fmt,n&padovann(n,t))
end for</lang>
- Output:
First 15 terms of the Padovan n-step number 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>
REXX
Some additional code was added for this REXX version to minimize the width for any particular column. <lang rexx>/*REXX program computes and shows the Padovan sequences for M steps for N numbers. */ parse arg n m . /*obtain optional arguments from the CL*/ if n== | n=="," then n= 15 /*Not specified? Then use the default.*/ if m== | m=="," then m= 8 /* " " " " " " */ w.= 1 /*W.c: the maximum width of a column. */
do #=2 for m-1 @.= 0; @.0= 1; @.1= 1; @.2= 1 /*initialize 3 terms of the Padovan seq*/ $= @.0 /*initials the list with the zeroth #. */ do k=2 for n-1; z= pd(k-1) w.k= max(w.k, length(z)); $= $ z /*find maximum width for a specific col*/ end /*k*/ $.#= $ /*save each unaligned line for later. */ end /*#*/
oW= 1
do col=1 for n; oW= oW + w.col + 1 /*add up the width of each column. */ end /*col*/ iw= length(m) + 2
say center('M', iw, " ")"│"center('first ' n " Padovan sequence with step M", ow) say center(, iw, "─")"┼"center( , ow, "─")
do out=2 for m-1; $= /*align columnar elements for outputs. */ do j=1 for n; $= $ right(word($.out, j), w.j) /*align the columns. */ end /*j*/ say center(out,length(m)+2)'│'$ /*display a line of columnar elements. */ end /*out*/
say center(, length(m)+2, "─")"┴"center( , ow, "─") exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ pd: procedure expose @. #; parse arg x; if @.x\==0 then return @.x /*@.x defined?*/
do k=1 for #; _= x-1-k; @.x= @.x + @._; end; return @.x</lang>
- output when using the default inputs:
M │ first 15 Padovan sequence with step M ───┼────────────────────────────────────────── 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 ───┴──────────────────────────────────────────
Wren
<lang ecmascript>import "/fmt" for Fmt
var padovanN // recursive padovanN = Fn.new { |n, t|
if (n < 2 || t < 3) return [1] * t var p = padovanN.call(n-1, t) if (n + 1 >= t) return p for (i in n+1...t) { p[i] = 0 for (j in i-2..i-n-1) p[i] = p[i] + p[j] } return p
}
var t = 15 System.print("First %(t) terms of the Padovan n-step number sequences:") for (n in 2..8) Fmt.print("$d: $3d" , n, padovanN.call(n, t))</lang>
- Output:
First 15 terms of the Padovan n-step number 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