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 Padovan 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).
11l
F rn(n, k) -> [Int]
assert(k >= 2)
V result = I n == 2 {[1, 1, 1]} E rn(n - 1, n + 1)
L result.len != k
result.append(sum(result[(len)-n-1 .< (len)-1]))
R result
L(n) 2..8
print(n‘: ’rn(n, 15).map(it -> ‘#3’.format(it)).join(‘ ’))
- Output:
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 68
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 ps = padovan sequences( 8, 15 );
print( ( "Padovan n-step sequences:", newline ) );
FOR n FROM 1 LWB ps TO 1 UPB ps DO
print( ( whole( n, 0 ), " |" ) );
FOR x FROM 2 LWB ps TO 2 UPB ps DO print( ( " ", whole( ps[ n, x ], -3 ) ) ) OD;
print( ( newline ) )
OD
END
- 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
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.
- 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
AppleScript
use AppleScript version "2.4"
use framework "Foundation"
use scripting additions
------------------ PADOVAN N-STEP NUMBERS ----------------
-- padovans :: [Int]
on padovans(n)
script recurrence
on |λ|(xs)
{item 1 of xs, ¬
rest of xs & {sum(take(n, xs)) as integer}}
end |λ|
end script
if 3 > n then
set seed to |repeat|(1)
else
set seed to padovans(n - 1)
end if
if 0 > n then
{}
else
unfoldr(recurrence, take(1 + n, seed))
end if
end padovans
--------------------------- TEST -------------------------
on run
script nSample
on |λ|(n)
take(15, padovans(n))
end |λ|
end script
script justified
on |λ|(ns)
concatMap(justifyRight(4, space), ns)
end |λ|
end script
fTable("Padovan N-step Series:", str, justified, ¬
nSample, enumFromTo(2, 8))
end run
------------------------ FORMATTING ----------------------
-- fTable :: String -> (a -> String) -> (b -> String) ->
-- (a -> b) -> [a] -> String
on fTable(s, xShow, fxShow, f, xs)
set ys to map(xShow, xs)
set w to maximum(map(my |length|, ys))
script arrowed
on |λ|(a, b)
|λ|(a) of justifyRight(w, space) & " ->" & b
end |λ|
end script
s & linefeed & unlines(zipWith(arrowed, ¬
ys, map(compose(fxShow, f), xs)))
end fTable
------------------------- GENERIC ------------------------
-- compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
on compose(f, g)
script
property mf : mReturn(f)
property mg : mReturn(g)
on |λ|(x)
mf's |λ|(mg's |λ|(x))
end |λ|
end script
end compose
-- concatMap :: (a -> [b]) -> [a] -> [b]
on concatMap(f, xs)
set lng to length of xs
set acc to {}
tell mReturn(f)
repeat with i from 1 to lng
set acc to acc & (|λ|(item i of xs, i, xs))
end repeat
end tell
if {text, string} contains class of xs then
acc as text
else
acc
end if
end concatMap
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
lst
else
{}
end if
end enumFromTo
-- intercalate :: String -> [String] -> String
on intercalate(delim, xs)
set {dlm, my text item delimiters} to ¬
{my text item delimiters, delim}
set s to xs as text
set my text item delimiters to dlm
s
end intercalate
-- justifyRight :: Int -> Char -> String -> String
on justifyRight(n, cFiller)
script
on |λ|(v)
set strText to v as text
if n > length of strText then
text -n thru -1 of ¬
((replicate(n, cFiller) as text) & strText)
else
strText
end if
end |λ|
end script
end justifyRight
-- length :: [a] -> Int
on |length|(xs)
set c to class of xs
if list is c or string is c then
length of xs
else
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
end if
end |length|
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- maximum :: Ord a => [a] -> a
on maximum(xs)
set ca to current application
unwrap((ca's NSArray's arrayWithArray:xs)'s ¬
valueForKeyPath:"@max.self")
end maximum
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted
-- into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- repeat :: a -> Generator [a]
on |repeat|(x)
script
on |λ|()
return x
end |λ|
end script
end |repeat|
-- Egyptian multiplication - progressively doubling a list, appending
-- stages of doubling to an accumulator where needed for binary
-- assembly of a target length
-- replicate :: Int -> String -> String
on replicate(n, s)
-- Egyptian multiplication - progressively doubling a list,
-- appending stages of doubling to an accumulator where needed
-- for binary assembly of a target length
script p
on |λ|({n})
n ≤ 1
end |λ|
end script
script f
on |λ|({n, dbl, out})
if (n mod 2) > 0 then
set d to out & dbl
else
set d to out
end if
{n div 2, dbl & dbl, d}
end |λ|
end script
set xs to |until|(p, f, {n, s, ""})
item 2 of xs & item 3 of xs
end replicate
-- str :: a -> String
on str(x)
x as string
end str
-- sum :: [Num] -> Num
on sum(xs)
set ca to current application
((ca's NSArray's arrayWithArray:xs)'s ¬
valueForKeyPath:"@sum.self") as real
end sum
-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on take(n, xs)
set c to class of xs
if list is c then
set lng to length of xs
if 0 < n and 0 < lng then
items 1 thru min(n, lng) of xs
else
{}
end if
else if string is c then
if 0 < n then
text 1 thru min(n, length of xs) of xs
else
""
end if
else if script is c then
set ys to {}
repeat with i from 1 to n
set v to |λ|() of xs
if missing value is v then
return ys
else
set end of ys to v
end if
end repeat
return ys
else
missing value
end if
end take
-- unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
on unfoldr(f, v)
-- A lazy (generator) list unfolded from a seed value
-- by repeated application of f to a value until no
-- residue remains. Dual to fold/reduce.
-- f returns either nothing (missing value),
-- or just (value, residue).
script
property valueResidue : {v, v}
property g : mReturn(f)
on |λ|()
set valueResidue to g's |λ|(item 2 of (valueResidue))
if missing value ≠ valueResidue then
item 1 of (valueResidue)
else
missing value
end if
end |λ|
end script
end unfoldr
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set s to xs as text
set my text item delimiters to dlm
s
end unlines
-- until :: (a -> Bool) -> (a -> a) -> a -> a
on |until|(p, f, x)
set v to x
set mp to mReturn(p)
set mf to mReturn(f)
repeat until mp's |λ|(v)
set v to mf's |λ|(v)
end repeat
v
end |until|
-- unwrap :: NSValue -> a
on unwrap(nsValue)
if nsValue is missing value then
missing value
else
set ca to current application
item 1 of ((ca's NSArray's arrayWithObject:nsValue) as list)
end if
end unwrap
-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
on zipWith(f, xs, ys)
set lng to min(length of xs, length of ys)
set lst to {}
if 1 > lng then
return {}
else
tell mReturn(f)
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, item i of ys)
end repeat
return lst
end tell
end if
end zipWith
- 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
BASIC
BASIC256
global t
t = 15
global p
dim p(t)
print "First"; t; " terms of the Padovan n-step number sequences:"
for n = 2 to 8
print n; ":";
call padovanN(n, p)
for i = 0 to t-1
print rjust(p[i],4);
next i
print
next n
end
subroutine padovanN(n, p)
if n < 2 or t < 3 then
for i = 0 to t-1
p[i] = 1
next i
return
end if
call padovanN(n-1, p)
for i = n + 1 to t-1
p[i] = 0
for j = i - 2 to i-n-1 step -1
p[i] += p[j]
next j
next i
return
end subroutine
Chipmunk Basic
100 CLS
110 t = 15
120 DIM p(t)
130 SUB padovann(n,p())
140 IF n < 2 OR t < 3 THEN
150 FOR i = 0 TO t-1
160 p(i) = 1
170 NEXT i
180 EXIT SUB
190 endif
200 padovann(n-1,p())
210 FOR i = n+1 TO t-1
220 p(i) = 0
230 FOR j = i-2 TO i-n-1 STEP -1
240 p(i) = p(i)+p(j)
250 NEXT j
260 NEXT i
270 EXIT SUB
280 END SUB
290 PRINT "First";t;" terms of the Padovan n-step number sequences:"
300 FOR n = 2 TO 8
310 PRINT n;":";
320 padovann(n,p())
330 FOR i = 0 TO t-1
340 PRINT USING "### ";p(i);
350 NEXT i
360 PRINT
370 NEXT n
380 END
FreeBASIC
' Rosetta Code problem: https://rosettacode.org/wiki/Padovan_n-step_number_sequences
' by Jjuanhdez, 05/2023
Const t = 15
Dim Shared As Integer p(t)
Sub padovanN(n As Integer, p() As Integer)
Dim As Integer i, j
If n < 2 Or t < 3 Then
For i = 0 To t-1
p(i) = 1
Next i
Exit Sub
End If
padovanN(n-1, p())
For i = n + 1 To t-1
p(i) = 0
For j = i - 2 To i-n-1 Step -1
p(i) += p(j)
Next j
Next i
End Sub
Print "First"; t; " terms of the Padovan n-step number sequences:"
Dim As Integer n, i
For n = 2 To 8
Print n; ": ";
padovanN(n, p())
For i = 0 To t-1
Print Using "### "; p(i);
Next i
Print
Next n
Sleep
- 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
Just BASIC
global t, p
t = 15
dim p(t)
print "First"; t; " terms of the Padovan n-step number sequences:"
for n = 2 to 8
print n; ":";
call padovanN n, p
for i = 0 to t-1
print using("####", p(i));
next i
print
next n
end
sub padovanN n, p
if n < 2 or t < 3 then
for i = 0 to t-1
p(i) = 1
next i
exit sub
end if
call padovanN n-1, p
for i = n + 1 to t-1
p(i) = 0
for j = i - 2 to i-n-1 step -1
p(i) = p(i) + p(j)
next j
next i
end sub
QBasic
DECLARE SUB padovanN (n!, p!())
CONST t = 15
DIM SHARED p(t)
PRINT "First"; t; " terms of the Padovan n-step number sequences:"
FOR n = 2 TO 8
PRINT n; ":";
CALL padovanN(n, p())
FOR i = 0 TO t - 1
PRINT USING "### "; p(i);
NEXT i
PRINT
NEXT n
SUB padovanN (n, p())
IF n < 2 OR t < 3 THEN
FOR i = 0 TO t - 1
p(i) = 1
NEXT i
EXIT SUB
END IF
CALL padovanN(n - 1, p())
FOR i = n + 1 TO t - 1
p(i) = 0
FOR j = i - 2 TO i - n - 1 STEP -1
p(i) = p(i) + p(j)
NEXT j
NEXT i
END SUB
PureBasic
Global.i t = 15, Dim p(t)
Procedure.i padovanN(n, Array p(1))
If n < 2 Or t < 3
For i = 0 To t - 1
p(i) = 1
Next i
ProcedureReturn
EndIf
padovanN(n - 1, p())
For i.i = n + 1 To t - 1
p(i) = 0
For j.i = i - 2 To i - n - 1 Step -1
p(i) = p(i) + p(j)
Next j
Next i
EndProcedure
If OpenConsole()
PrintN("First" + Str(t) + " terms of the Padovan n-step number sequences:")
For n.i = 2 To 8
Print(Str(n) + ":")
padovanN(n, p())
For i.i = 0 To t - 1
Print(RSet(Str(p(i)),4))
Next i
PrintN("")
Next n
PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input()
CloseConsole()
EndIf
Yabasic
t = 15
dim p(t)
print "First", t, " terms of the Padovan n-step number sequences:"
for n = 2 to 8
print n, ":";
padovanN(n, p())
for i = 0 to t-1
print p(i) using ("###");
next i
print
next n
end
sub padovanN(n, p())
local i, j
if n < 2 or t < 3 then
for i = 0 to t-1
p(i) = 1
next i
return
fi
padovanN(n-1, p())
for i = n + 1 to t-1
p(i) = 0
for j = i - 2 to i-n-1 step -1
p(i) = p(i) + p(j)
next j
next i
return
end sub
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;
}
- 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
C++
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
void padovan(const int32_t& limit, const uint64_t& termCount) {
std::vector<int32_t> previous_terms = { 1, 1, 1 };
for ( int32_t N = 2; N <= limit; ++N ) {
std::vector<int32_t> next_terms = { previous_terms.begin(), previous_terms.begin() + N + 1 };
while ( next_terms.size() < termCount ) {
int32_t sum = 0;
for ( int32_t step_back = 2; step_back <= N + 1; ++step_back ) {
sum += next_terms[next_terms.size() - step_back];
}
next_terms.emplace_back(sum);
}
std::cout << N << ": ";
for ( const int32_t& term : next_terms ) {
std::cout << std::setw(4) << term;
}
std::cout << std::endl;;
previous_terms = next_terms;
}
}
int main() {
const int32_t limit = 8;
const uint64_t termCount = 15;
std::cout << "First " << termCount << " terms of the Padovan n-step number sequences:" << std::endl;
padovan(limit, termCount);
}
- 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
EasyLang
t = 15
len p[] t
#
proc padovan n . .
if n < 2 or t < 3
for i = 1 to t
p[i] = 1
.
return
.
padovan n - 1
for i = n + 2 to t
p[i] = 0
for j = i - 2 downto i - n - 1
p[i] += p[j]
.
.
.
for n = 2 to 8
padovan n
write n & ": "
for i = 1 to t
write p[i] & " "
.
print ""
.
F#
// Padovan n-step number sequences. Nigel Galloway: July 28th., 2021
let rec pad=function 2->Seq.unfold(fun(n:int[])->Some(n.[0],Array.append n.[1..2] [|Array.sum n.[0..1]|]))[|1;1;1|]
|g->Seq.unfold(fun(n:int[])->Some(n.[0],Array.append n.[1..g] [|Array.sum n.[0..g-1]|]))(Array.ofSeq(pad(g-1)|>Seq.take(g+1)))
[2..8]|>List.iter(fun n->pad n|>Seq.take 15|>Seq.iter(printf "%d "); printfn "")
- Output:
1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 1 1 1 2 3 4 6 9 13 19 28 41 60 88 129 1 1 1 2 3 5 7 11 17 26 40 61 94 144 221 1 1 1 2 3 5 8 12 19 30 47 74 116 182 286 1 1 1 2 3 5 8 13 20 32 51 81 129 205 326 1 1 1 2 3 5 8 13 21 33 53 85 136 218 349 1 1 1 2 3 5 8 13 21 34 54 87 140 225 362
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.
- 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
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))
}
}
- 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
import Data.Bifunctor (second)
import Data.List (transpose, uncons, unfoldr)
------------------ PADOVAN N-STEP SERIES -----------------
padovans :: Int -> [Int]
padovans n
| 0 > n = []
| otherwise = unfoldr (recurrence n) $ take (succ n) xs
where
xs
| 3 > n = repeat 1
| otherwise = padovans $ pred n
recurrence :: Int -> [Int] -> Maybe (Int, [Int])
recurrence n =
( fmap
. second
. flip (<>)
. pure
. sum
. take n
)
<*> uncons
--------------------------- TEST -------------------------
main :: IO ()
main =
putStrLn $
"Padovan N-step series:\n\n"
<> spacedTable
justifyRight
( fmap
( \n ->
[show n <> " -> "]
<> fmap show (take 15 $ padovans n)
)
[2 .. 8]
)
------------------------ FORMATTING ----------------------
spacedTable ::
(Int -> Char -> String -> String) -> [[String]] -> String
spacedTable aligned rows =
unlines $
fmap
(unwords . zipWith (`aligned` ' ') columnWidths)
rows
where
columnWidths =
fmap
(maximum . fmap length)
(transpose rows)
justifyRight :: Int -> a -> [a] -> [a]
justifyRight n c = drop . length <*> (replicate n c <>)
- 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
J
padovanN=: {{ (, [: +/ (-m) {. }:)@]^:([-2:)&1 1 }}
{{(":,.y),.': ',"1":{{ y padovanN 15 }}&>y}} 2+i.7
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
Java
import java.util.ArrayList;
import java.util.List;
public final class PadovanNStep {
public static void main(String[] aArgs) {
final int limit = 8;
final int termCount = 15;
System.out.println("First " + termCount + " terms of the Padovan n-step number sequences:");
padovan(limit, termCount);
}
private static void padovan(int aLimit, int aTermCount) {
List<Integer> previous = List.of( 1, 1, 1 );
for ( int N = 2; N <= aLimit; N++ ) {
List<Integer> next = new ArrayList<Integer>(previous.subList(0, N + 1));
while ( next.size() < aTermCount ) {
int sum = 0;
for ( int stepBack = 2; stepBack <= N + 1; stepBack++ ) {
sum += next.get(next.size() - stepBack);
}
next.add(sum);
}
System.out.print(N + ": ");
next.forEach( term -> System.out.print(String.format("%4d", term)));
System.out.println();
previous = next;
}
}
}
- 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
JavaScript
(() => {
"use strict";
// ---------- PADOVAN N-STEP NUMBER SERIES -----------
// padovans :: Int -> [Int]
const padovans = n => {
// Padovan number series of step N
const recurrence = ns => [
ns[0],
ns.slice(1).concat(
sum(take(n)(ns))
)
];
return 0 > n ? (
[]
) : unfoldr(recurrence)(
take(1 + n)(
3 > n ? (
repeat(1)
) : padovans(n - 1)
)
);
};
// ---------------------- TEST -----------------------
// main :: IO ()
const main = () =>
fTable("Padovan N-step series:")(str)(
xs => xs.map(
compose(justifyRight(4)(" "), str)
)
.join("")
)(
compose(take(15), padovans)
)(
enumFromTo(2)(8)
);
// --------------------- GENERIC ---------------------
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
const compose = (...fs) =>
// A function defined by the right-to-left
// composition of all the functions in fs.
fs.reduce(
(f, g) => x => f(g(x)),
x => x
);
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = m =>
n => Array.from({
length: 1 + n - m
}, (_, i) => m + i);
// repeat :: a -> Generator [a]
const repeat = function* (x) {
while (true) {
yield x;
}
};
// sum :: [Num] -> Num
const sum = xs =>
// The numeric sum of all values in xs.
xs.reduce((a, x) => a + x, 0);
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take = n =>
// The first n elements of a list,
// string of characters, or stream.
xs => "GeneratorFunction" !== xs
.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat(...Array.from({
length: n
}, () => {
const x = xs.next();
return x.done ? [] : [x.value];
}));
// unfoldr :: (b -> Maybe (a, b)) -> b -> Gen [a]
const unfoldr = f =>
// A lazy (generator) list unfolded from a seed value
// by repeated application of f to a value until no
// residue remains. Dual to fold/reduce.
// f returns either Nothing or Just (value, residue).
// For a strict output list,
// wrap with `list` or Array.from
x => (
function* () {
let valueResidue = f(x);
while (null !== valueResidue) {
yield valueResidue[0];
valueResidue = f(valueResidue[1]);
}
}()
);
// ------------------- FORMATTING --------------------
// fTable :: String -> (a -> String) ->
// (b -> String) -> (a -> b) -> [a] -> String
const fTable = s =>
// Heading -> x display function ->
// fx display function ->
// f -> values -> tabular string
xShow => fxShow => f => xs => {
const
ys = xs.map(xShow),
w = Math.max(...ys.map(y => [...y].length)),
table = zipWith(
a => b => `${a.padStart(w, " ")} ->${b}`
)(ys)(
xs.map(x => fxShow(f(x)))
).join("\n");
return `${s}\n${table}`;
};
// justifyRight :: Int -> Char -> String -> String
const justifyRight = n =>
// The string s, preceded by enough padding (with
// the character c) to reach the string length n.
c => s => n > s.length ? (
s.padStart(n, c)
) : s;
// str :: a -> String
const str = x => `${x}`;
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
// A list constructed by zipping with a
// custom function, rather than with the
// default tuple constructor.
xs => ys => take(
Math.min(xs.length, ys.length)
)(
xs.map((x, i) => f(x)(ys[i]))
);
// MAIN ---
return main();
})();
- 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
"""
First nterms terms of the first 2..max_nstep -step Padovan sequences.
"""
function nstep_Padovan(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_Padovan_seq(p)
println(strip("""
:::: {| style="text-align: left;" border="4" cellpadding="2" cellspacing="2"
|+ Padovan <math>n</math>-step sequences
|- style="background-color: rgb(255, 204, 255);"
! <math>n</math> !! Values
|-
"""))
for (n, seq) in enumerate(p)
println("| $n || $(replace(string(seq[2:end]), r"[ a-zA-Z\[\]]+" => "")), ...\n|-")
end
println("|}")
end
print_Padovan_seq(nstep_Padovan())
- Output:
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, ...
Mathematica /Wolfram Language
ClearAll[Padovan]
Padovan[2,tmax_]:=Module[{start,a,m},
start={1,1,1};
start=MapIndexed[a[#2[[1]]]==#1&,start];
RecurrenceTable[{a[m]==a[m-2]+a[m-3]}~Join~start,a, {m,tmax}]
]
Padovan[n_,tmax_]:=Module[{start,eq,a,m},
start=Padovan[n-1,n+1];
start=MapIndexed[a[#2[[1]]]==#1&,start];
eq=Range[2,n+1];
eq=Append[start,a[m]==Total[a[m-#]&/@eq]];
RecurrenceTable[eq,a, {m,tmax}]
]
Padovan[2,15]
Padovan[3,15]
Padovan[4,15]
Padovan[5,15]
Padovan[6,15]
Padovan[7,15]
Padovan[8,15]
- Output:
{1,1,1,2,2,3,4,5,7,9,12,16,21,28,37} {1,1,1,2,3,4,6,9,13,19,28,41,60,88,129} {1,1,1,2,3,5,7,11,17,26,40,61,94,144,221} {1,1,1,2,3,5,8,12,19,30,47,74,116,182,286} {1,1,1,2,3,5,8,13,20,32,51,81,129,205,326} {1,1,1,2,3,5,8,13,21,33,53,85,136,218,349} {1,1,1,2,3,5,8,13,21,34,54,87,140,225,362}
Nim
import math, sequtils, strutils
proc rn(n, k: Positive): seq[int] =
assert k >= 2
result = if n == 2: @[1, 1, 1] else: rn(n - 1, n + 1)
while result.len != k:
result.add sum(result[^(n + 1)..^2])
for n in 2..8:
echo n, ": ", rn(n, 15).mapIt(($it).align(3)).join(" ")
- Output:
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
Perl
use strict;
use warnings;
use feature <state say>;
use List::Util 'sum';
use List::Lazy 'lazy_list';
say 'Padovan N-step sequences; first 25 terms:';
for our $N (2..8) {
my $pad_n = lazy_list {
state $n = 2;
state @pn = (1, 1, 1);
push @pn, sum @pn[ grep { $_ >= 0 } $n-$N .. $n++ - 1 ];
$pn[-4]
};
print "N = $N |";
print ' ' . $pad_n->next() for 1..25;
print "\n"
}
- Output:
N = 2 | 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 200 265 351 465 616 N = 3 | 1 1 1 2 3 4 6 9 13 19 28 41 60 88 129 189 277 406 595 872 1278 1873 2745 4023 5896 N = 4 | 1 1 1 2 3 5 7 11 17 26 40 61 94 144 221 339 520 798 1224 1878 2881 4420 6781 10403 15960 N = 5 | 1 1 1 2 3 5 8 12 19 30 47 74 116 182 286 449 705 1107 1738 2729 4285 6728 10564 16587 26044 N = 6 | 1 1 1 2 3 5 8 13 20 32 51 81 129 205 326 518 824 1310 2083 3312 5266 8373 13313 21168 33657 N = 7 | 1 1 1 2 3 5 8 13 21 33 53 85 136 218 349 559 895 1433 2295 3675 5885 9424 15091 24166 38698 N = 8 | 1 1 1 2 3 5 8 13 21 34 54 87 140 225 362 582 936 1505 2420 3891 6257 10061 16178 26014 41830
Phix
with javascript_semantics 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
- 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
def pad_like(max_n=8, t=15):
"""
First t terms of the first 2..max_n-step Padovan 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('''
:::: {| style="text-align: left;" border="4" cellpadding="2" cellspacing="2"
|+ Padovan <math>n</math>-step sequences
|- style="background-color: rgb(255, 204, 255);"
! <math>n</math> !! Values
|-
'''.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)
- Output:
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, ...
Python: Functional
Defined in terms of a generic anamorphism, using the unfold abstraction, which is dual to reduce.
Aims for a legible expression of the Padovan recurrence relation, and a good level of reliability and code reuse, as well as rapid drafting and refactoring.
Functional composition, while widely practiced and written about in the context of Python, is not the dominant Python tradition. The documentation of the Python itertools module does, however, acknowledge its debt to languages like ML and Haskell, both for an algebra of composition, and for a source of function-naming traditions.
This draft is thoroughly linted, for a high degree of compliance with Python language standards and layout.
Patterns of functional composition are constrained more by mathematical necessity than by arbitrary convention, but this still leaves room for alternative idioms of functional coding in Python. It is to be hoped that others will contribute divergent examples, enriching the opportunities for contrastive insight which Rosetta code aims to provide.
'''Padovan n-step number sequences'''
from itertools import chain, islice, repeat
# nStepPadovan :: Int -> [Int]
def nStepPadovan(n):
'''Non-finite series of N-step Padovan numbers,
defined by a recurrence relation.
'''
return unfoldr(recurrence(n))(
take(1 + n)(
repeat(1) if 3 > n else (
nStepPadovan(n - 1)
)
)
)
# recurrence :: Int -> [Int] -> Int
def recurrence(n):
'''Recurrence relation in Fibonacci,
Padovan and Perrin sequences.
'''
def go(xs):
h, *t = xs
return h, t + [sum(take(n)(xs))]
return go
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''First 15 terms each nStepPadovan(n) series
where n is drawn from [2..8]
'''
xs = range(2, 1 + 8)
print('Padovan n-step series:\n')
print(
spacedTable(list(map(
lambda k, n: list(chain(
[k + ' -> '],
(
str(x) for x
in take(15)(nStepPadovan(n))
)
)),
(str(x) for x in xs),
xs
)))
)
# ----------------------- GENERIC ------------------------
# 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
# 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 in list().
'''
def go(x):
valueResidue = f(x)
while None is not valueResidue:
yield valueResidue[0]
valueResidue = f(valueResidue[1])
return go
# ---------------------- FORMATTING ----------------------
# spacedTable :: [[String]] -> String
def spacedTable(rows):
'''A table with right-aligned columns.
'''
columnWidths = [
max([len(x) for x in col])
for col in zip(*rows)
]
return '\n'.join(
' '.join(map(
lambda x, w: x.rjust(w, ' '),
row, columnWidths
))
for row in rows
)
# MAIN ---
if __name__ == '__main__':
main()
- 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
Raku
say 'Padovan N-step sequences; first 25 terms:';
for 2..8 -> \N {
my @n-step = 1, 1, 1, { state $n = 2; @n-step[ ($n - N .. $n++ - 1).grep: * >= 0 ].sum } … *;
put "N = {N} |" ~ @n-step[^25]».fmt: "%5d";
}
- Output:
Padovan N-step sequences; first 25 terms: N = 2 | 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 200 265 351 465 616 N = 3 | 1 1 1 2 3 4 6 9 13 19 28 41 60 88 129 189 277 406 595 872 1278 1873 2745 4023 5896 N = 4 | 1 1 1 2 3 5 7 11 17 26 40 61 94 144 221 339 520 798 1224 1878 2881 4420 6781 10403 15960 N = 5 | 1 1 1 2 3 5 8 12 19 30 47 74 116 182 286 449 705 1107 1738 2729 4285 6728 10564 16587 26044 N = 6 | 1 1 1 2 3 5 8 13 20 32 51 81 129 205 326 518 824 1310 2083 3312 5266 8373 13313 21168 33657 N = 7 | 1 1 1 2 3 5 8 13 21 33 53 85 136 218 349 559 895 1433 2295 3675 5885 9424 15091 24166 38698 N = 8 | 1 1 1 2 3 5 8 13 21 34 54 87 140 225 362 582 936 1505 2420 3891 6257 10061 16178 26014 41830
REXX
Some additional code was added for this REXX version to minimize the width for any particular column.
/*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
- 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 ───┴──────────────────────────────────────────
RPL
« → n t « IF n 2 ≤ t 3 ≤ OR THEN 1 n 1 + NDUPN →LIST ELSE n 1 - n NPADOVAN END WHILE DUP SIZE t < REPEAT DUP DUP SIZE DUP n - SWAP 1 - SUB ∑LIST + END » » 'NPADOVAN' STO
« n 15 NPADOVAN » 'n' 2 8 1 SEQ
- Output:
1: { { 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 } { 1 1 1 2 3 4 6 9 13 19 28 41 60 88 129 } { 1 1 1 2 3 5 7 11 17 26 40 61 94 144 221 } { 1 1 1 2 3 5 8 12 19 30 47 74 116 182 286 } { 1 1 1 2 3 5 8 13 20 32 51 81 129 205 326 } { 1 1 1 2 3 5 8 13 21 33 53 85 136 218 349 } { 1 1 1 2 3 5 8 13 21 34 54 87 140 225 362 } }
Ruby
def padovan(n_step)
return to_enum(__method__, n_step) unless block_given?
ar = [1, 1, 1]
loop do
yield sum = ar[..-2].sum
ar.shift if ar.size > n_step
ar << sum
end
end
t = 15
(2..8).each do |n|
print "N=#{n} :"
puts "%5d"*t % padovan(n).take(t)
end
- Output:
N=2 : 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 N=3 : 2 3 4 6 9 13 19 28 41 60 88 129 189 277 406 N=4 : 2 3 5 7 11 17 26 40 61 94 144 221 339 520 798 N=5 : 2 3 5 8 12 19 30 47 74 116 182 286 449 705 1107 N=6 : 2 3 5 8 13 20 32 51 81 129 205 326 518 824 1310 N=7 : 2 3 5 8 13 21 33 53 85 136 218 349 559 895 1433 N=8 : 2 3 5 8 13 21 34 54 87 140 225 362 582 936 1505
Rust
fn padovan(n: u64, x: u64) -> u64 {
if n < 2 {
return 0;
}
match n {
2 if x <= n + 1 => 1,
2 => padovan(n, x - 2) + padovan(n, x - 3),
_ if x <= n + 1 => padovan(n - 1, x),
_ => ((x - n - 1)..(x - 1)).fold(0, |acc, value| acc + padovan(n, value)),
}
}
fn main() {
(2..=8).for_each(|n| {
print!("\nN={}: ", n);
(1..=15).for_each(|x| print!("{},", padovan(n, x)))
});
}
- Output:
N=2: 1,1,1,2,2,3,4,5,7,9,12,16,21,28,37, N=3: 1,1,1,2,3,4,6,9,13,19,28,41,60,88,129, N=4: 1,1,1,2,3,5,7,11,17,26,40,61,94,144,221, N=5: 1,1,1,2,3,5,8,12,19,30,47,74,116,182,286, N=6: 1,1,1,2,3,5,8,13,20,32,51,81,129,205,326, N=7: 1,1,1,2,3,5,8,13,21,33,53,85,136,218,349, N=8: 1,1,1,2,3,5,8,13,21,34,54,87,140,225,362,
Sidef
func padovan(N) {
Enumerator({|callback|
var n = 2
var pn = [1, 1, 1]
loop {
pn << sum(pn[n-N .. (n++-1) -> grep { _ >= 0 }])
callback(pn[-4])
}
})
}
for n in (2..8) {
say "n = #{n} | #{padovan(n).first(25).join(' ')}"
}
- Output:
n = 2 | 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 65 86 114 151 200 265 351 465 616 n = 3 | 1 1 1 2 3 4 6 9 13 19 28 41 60 88 129 189 277 406 595 872 1278 1873 2745 4023 5896 n = 4 | 1 1 1 2 3 5 7 11 17 26 40 61 94 144 221 339 520 798 1224 1878 2881 4420 6781 10403 15960 n = 5 | 1 1 1 2 3 5 8 12 19 30 47 74 116 182 286 449 705 1107 1738 2729 4285 6728 10564 16587 26044 n = 6 | 1 1 1 2 3 5 8 13 20 32 51 81 129 205 326 518 824 1310 2083 3312 5266 8373 13313 21168 33657 n = 7 | 1 1 1 2 3 5 8 13 21 33 53 85 136 218 349 559 895 1433 2295 3675 5885 9424 15091 24166 38698 n = 8 | 1 1 1 2 3 5 8 13 21 34 54 87 140 225 362 582 936 1505 2420 3891 6257 10061 16178 26014 41830
Wren
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))
- 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
XPL0
\Show some values 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 ( R, MaxS, MaxE) ;
integer R, MaxS, MaxE;
integer X, N, P;
function Min( A, B );
integer A, B;
return if A < B then A else B;
begin
\Sequence 2
for X := 1 to Min( MaxE, 3 ) do R( 2, X ) := 1;
for X := 4 to MaxE do R( 2, X ) := R( 2, X - 2 ) + R( 2, X - 3 );
\Sequences 3 and above
for N := 3 to MaxS do begin
for X := 1 to Min( MaxE, N + 1 ) do R( N, X ) := R( N - 1, X );
for X := N + 2 to MaxE do begin
R( N, X ) := 0;
for P := X - N - 1 to X - 2 do R( N, X ) := R( N, X ) + R( N, P )
end \for X
end \for_N
end; \PadovanSequences
def MAX_SEQUENCES = 8,
MAX_ELEMENTS = 15;
\Array to hold the Padovan Sequences
integer R( (2+MAX_SEQUENCES), (1+MAX_ELEMENTS)), N, X;
begin \Calculate and show the sequences
\Construct the sequences
PadovanSequences( R, MAX_SEQUENCES, MAX_ELEMENTS );
\Show the sequences
Text(0, "Padovan n-step sequences:^m^j" );
Format(4, 0);
for N := 2 to MAX_SEQUENCES do begin
IntOut(0, N); Text(0, " |");
for X := 1 to MAX_ELEMENTS do
RlOut(0, float(R( N, X )));
CrLf(0);
end \for N
end
- 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