Padovan n-step number sequences: Difference between revisions
m (added whitespace before the TOC.) |
m (→{{header|REXX}}: centered the output grid.) |
||
Line 593: | Line 593: | ||
do col=1 for n; oW= oW + w.col + 1 /*add up the width of each column. */ |
do col=1 for n; oW= oW + w.col + 1 /*add up the width of each column. */ |
||
end /*col*/ |
end /*col*/ |
||
iw= length(m) + 2 |
iw= length(m) + 2; pad= left('', 20*(n<21)) /*maybe indent.*/ |
||
say center('M', iw, " ")"│"center('first ' |
say pad center('M', iw, " ")"│"center('first ' n " Padovan sequence with step M", ow) |
||
say center('', iw, "─")"┼"center('' |
say pad center('', iw, "─")"┼"center('', ow, "─") |
||
do out=2 for m-1; $= /*align columnar elements for outputs. */ |
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. */ |
do j=1 for n; $= $ right(word($.out, j), w.j) /*align the columns. */ |
||
end /*j*/ |
end /*j*/ |
||
say center(out,length(m)+2)'│'$ |
say pad center(out,length(m)+2)'│'$ /*display a line of columnar elements. */ |
||
end /*out*/ |
end /*out*/ |
||
say center('', length(m)+2, "─")"┴"center('' |
say pad center('', length(m)+2, "─")"┴"center('', ow, "─") |
||
exit 0 /*stick a fork in it, we're all done. */ |
exit 0 /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
Line 610: | Line 610: | ||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
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 |
|||
───┴────────────────────────────────────────── |
|||
───┴────────────────────────────────────────── |
|||
</pre> |
</pre> |
||
Revision as of 21:04, 17 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]
Haskell
<lang haskell>import Data.List (unfoldr)
PADOVAN N-STEP SERIES -----------------
padovans :: Int -> [Int] padovans n = unfoldr f $ take (succ n) window
where f ns = Just (head ns, tail ns <> [sum $ take n ns]) window | 3 > n = repeat 1 | otherwise = padovans $ pred n
TEST -------------------------
main :: IO () main =
putStrLn $ fTable "Padovan N-step series:" show (justifyRight 4 ' ' . show =<<) (take 15 . padovans) [2 .. 8]
FORMATTING ----------------------
fTable ::
String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String
fTable s xShow fxShow f xs =
unlines $ s : fmap ( ((<>) . justifyRight w ' ' . xShow) <*> ((" ->" <>) . fxShow . f) ) xs where w = maximum (length . xShow <$> xs)
justifyRight :: Int -> a -> [a] -> [a] justifyRight n c = drop . length <*> (replicate n c <>)</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
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; pad= left(, 20*(n<21)) /*maybe indent.*/
say pad center('M', iw, " ")"│"center('first ' n " Padovan sequence with step M", ow) say pad 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 pad center(out,length(m)+2)'│'$ /*display a line of columnar elements. */ end /*out*/
say pad 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