Padovan n-step number sequences
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_nPadovan -step number sequences as defined above. - Use this to print and show here at least the first
t=15values 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
Python: Procedural
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>
Python: Functional
Defined in terms of a generic anamorphism.
<lang python>Padovan N-step series
from itertools import islice, repeat
- padovans :: Int -> [Int]
def padovans(n):
Non-finite series of N-step Padovan numbers,
defined by a recurrence relation.
def recurrence(ns):
return ns[0], ns[1:] + [sum(take(n)(ns))]
return unfoldr(recurrence)(
take(1 + n)(
repeat(1) if 3 > n else padovans(n - 1)
)
)
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
First 15 terms each n-step Padovan(n) series
where n is drawn from [2..8]
def sample(n):
return take(15)(padovans(n))
def columnWidth(n):
def go(xs):
return .join([
str(x).rjust(n, ' ') for x in xs
])
return go
print(
fTable('Padovan n-step series:')(repr)(
columnWidth(4)
)(sample)(range(2, 1 + 8))
)
- ----------------------- GENERIC ------------------------
- unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
def unfoldr(f):
Generic anamorphism.
A lazy (generator) list unfolded from a seed value by
repeated application of f until no residue remains.
Dual to fold/reduce.
f returns either None, or just (value, residue).
For a strict output value, wrap list().
def go(x):
valueResidue = f(x)
while None is not valueResidue:
yield valueResidue[0]
valueResidue = f(valueResidue[1])
return go
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n,
or xs itself if n > length xs.
def go(xs):
return (
xs[0:n]
if isinstance(xs, (list, tuple))
else list(islice(xs, n))
)
return go
- ---------------------- FORMATTING ----------------------
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function ->
fx display function -> f -> xs -> tabular string.
def gox(xShow):
def gofx(fxShow):
def gof(f):
def goxs(xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
def arrowed(x, y):
return y.rjust(w, ' ') + ' ->' + (
fxShow(f(x))
)
return s + '\n' + '\n'.join(
map(arrowed, xs, ys)
)
return goxs
return gof
return gofx
return gox
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
Padovan n-step series: 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
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