Riordan numbers: Difference between revisions
Add PARI/GP implementation
(Created Nim solution.) |
(Add PARI/GP implementation) |
||
| (14 intermediate revisions by 12 users not shown) | |||
Line 1:
{{
Riordan numbers show up in several places in set theory. They are closely related to [[Motzkin numbers]], and may be used to derive them.
Line 378:
<pre>Same as FreeBASIC entry.</pre>
==={{header|uBasic/4tH}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="yabasic">l = 31
c = 0
Dim @r(l)
Print "First 32 Riordan numbers:"
Proc _Riordan(l)
For i = 0 To l
Print Using " ____________#"; @r(i);
c = c + 1
If c % 4 = 0 Then Print
Next
End
_Riordan
Param (1)
Local (1)
If (a@ < 0) = 0 Then
@r(0) = 1
If (a@ < 1) = 0 Then
@r(1) = 0
For b@ = 2 To a@
@r(b@) = ((b@-1) * ((2 * @r(b@-1)) + (3 * @r(b@-2)))) / (b@+1)
Next
EndIf
EndIf
Return</syntaxhighlight>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
Line 407 ⟶ 439:
fi
end sub</syntaxhighlight>
=={{header|Bracmat}}==
<syntaxhighlight lang="bracmat">( ( a
=
. !arg:0&1
| !arg:1&0
| !(!arg$A):>0
| (!arg+-1)
* (2*a$(!arg+-1)+3*a$(!arg+-2))
* (!arg+1)^-1
: ?(!arg$A)
)
& "Create a table A that is big enough to memoize 10000 values. All values are initialized to 0."
& "Table elements are selected by using the syntax !index$tableName"
& tbl$(A,10000)
& -1:?n
& whl
' (!n+1:~>32:?n&out$(a$!n))
& "Theoretically, one could just ask for a(10000), but without first computing a(n) for all n < 10000 there is a risk a risk of stack overflow."
& whl'(!n+1:~>10000:?n&a$!n)
& "Apply string pattern matching @(subject:pattern) the the value of a(n) with the special pattern [?variable to find the total length of the string."
& @(a$999:? [?l1000)
& @(a$9999:? [?l10000)
& out$(str$("a(999) has " !l1000 " digits."))
& out$(str$("a(9999) has " !l10000 " digits."))
)</syntaxhighlight>
{{out}}
<pre>
1
0
1
1
3
6
15
36
91
232
603
1585
4213
11298
30537
83097
227475
625992
1730787
4805595
13393689
37458330
105089229
295673994
834086421
2358641376
6684761125
18985057351
54022715451
154000562758
439742222071
1257643249140
3602118427251
a(999) has 472 digits.
a(9999) has 4765 digits.
</pre>
=={{header|C++}}==
Line 439 ⟶ 536:
}
std::string to_string(const big_int& num, size_t
std::string str = num.get_str();
size_t len = str.size();
if (len >
return str;
}
Line 483 ⟶ 580:
The 10000th is 19927418577260688844...71395322020211157137 (4765 digits).
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
cnt = 32
print "First " & cnt & " Riordan numbers:"
app = 1 ; ap = 0
print app ; print ap
for n = 2 to cnt - 1
a = (n - 1) * (2 * ap + 3 * app) / (n + 1)
print a
app = ap
ap = a
.
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
Line 567 ⟶ 679:
if count mod 4 == 0 then print
next
HandleEvents
Line 584 ⟶ 694:
54022715451 154000562758 439742222071 1257643249140
</pre>
=={{header|Haskell}}==
Line 671 ⟶ 780:
#":(1e4-1){riordanext^:(1e4) x:1 0
4765</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.List;
public final class RiordanNumbers {
public static void main(String[] args) {
final int limit = 10_000;
final BigInteger THREE = BigInteger.valueOf(3);
BigInteger[] riordans = new BigInteger[limit];
riordans[0] = BigInteger.ONE;
riordans[1] = BigInteger.ZERO;
for ( int n = 2; n < limit; n++ ) {
BigInteger term = BigInteger.TWO.multiply(riordans[n - 1]).add(THREE.multiply(riordans[n - 2]));
riordans[n] = BigInteger.valueOf(n - 1).multiply(term).divide(BigInteger.valueOf(n + 1));
}
System.out.println("The first 32 Riordan numbers:");
for ( int i = 0; i < 32; i++ ) {
System.out.print(String.format("%14d%s", riordans[i], ( i % 4 == 3 ? "\n" :" " )));
}
System.out.println();
for ( int count : List.of( 1_000, 10_000 ) ) {
int length = riordans[count - 1].toString().length();
System.out.println("The " + count + "th Riordan number has " + length + " digits");
}
}
}
</syntaxhighlight>
{{ out }}
<pre>
The first 32 Riordan numbers:
1 0 1 1
3 6 15 36
91 232 603 1585
4213 11298 30537 83097
227475 625992 1730787 4805595
13393689 37458330 105089229 295673994
834086421 2358641376 6684761125 18985057351
54022715451 154000562758 439742222071 1257643249140
The 1000th Riordan number has 472 digits
The 10000th Riordan number has 4765 digits
</pre>
=={{header|jq}}==
Line 775 ⟶ 933:
The 1,000th Riordan has 472 digits.
The 10,000th Riordan has 4765 digits.
</pre>
=={{header|Lua}}==
{{Trans|ALGOL 68|basic task only, as Lua integers are (usually) limited to 2^53}}
<syntaxhighlight lang="lua">
do -- Riordan numbers
local function riordan( n ) -- returns a table of the Riordan numbers 0 .. n
local a = {}
if n >= 0 then
a[ 0 ] = 1
if n >= 1 then
a[ 1 ] = 0
for i = 2, n do
a[ i ] = math.floor( ( ( i - 1 )
* ( ( 2 * a[ i - 1 ] )
+ ( 3 * a[ i - 2 ] )
)
)
/ ( i + 1 )
)
end
end
end
return a
end
local function commatise( unformatted ) -- returns a string representation of n with commas
local result, chCount = "", 0
for c = #unformatted, 1, -1 do
if chCount <= 2 then
chCount = chCount + 1
else
chCount = 1
result = ( unformatted:sub( c, c ) == " " and " " or "," )..result
end
result = unformatted:sub( c, c )..result
end
return result
end
do -- show the first 32 Riordann numbers
local r, shown = riordan( 31 ), 0
for i = 0, #r do
shown = ( shown + 1 ) % 4
io.write( commatise( string.format( "%15d", r[ i ] ) )
, ( shown == 0 and "\n" or "" )
)
end
end
end
</syntaxhighlight>
{{out}}
<pre>
1 0 1 1
3 6 15 36
91 232 603 1,585
4,213 11,298 30,537 83,097
227,475 625,992 1,730,787 4,805,595
13,393,689 37,458,330 105,089,229 295,673,994
834,086,421 2,358,641,376 6,684,761,125 18,985,057,351
54,022,715,451 154,000,562,758 439,742,222,071 1,257,643,249,140
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="Mathematica">
Riordan[N_] :=
Module[{a = {1, 0, 1}},
Do[AppendTo[a, ((n - 1) (2 a[[n]] + 3 a[[n - 1]])/(n + 1))], {n, 3,
N}];
a]
rios = Riordan[10000];
Do[Print[ToString@NumberForm[rios[[i]], DigitBlock -> 3]], {i, 32}]
Print["The 1,000th Riordan number has ", IntegerLength[rios[[1000]]],
" digits."];
Print["The 10,000th Riordan number has ",
IntegerLength[rios[[10000]]], " digits."];
</syntaxhighlight>
{{out}}
<pre>
1
0
1
1
3
6
15
36
91
232
603
1,585
4,213
11,298
30,537
83,097
227,475
625,992
1,730,787
4,805,595
13,393,689
37,458,330
105,089,229
295,673,994
834,086,421
2,358,641,376
6,684,761,125
18,985,057,351
54,022,715,451
154,000,562,758
439,742,222,071
1,257,643,249,140
The 1,000th Riordan number has 472 digits.
The 10,000th Riordan number has 4765 digits.
</pre>
Line 842 ⟶ 1,117:
<pre>The 1000th Riordan number has 472 digits.
The 10000th Riordan number has 4765 digits.
</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang="PARI/GP">
\\ Increase the stack size if necessary
default(parisize, "32M"); \\ Increase to 32MB, adjust if necessary
Riordan(N) = {
my(a = vector(N));
a[1] = 1; a[2] = 0; a[3] = 1;
for (n = 3, N-1,
a[n+1] = ((n - 1) * (2 * a[n] + 3 * a[n-1]) \ (n + 1)); \\ Integer division
);
return(a);
}
rios = Riordan(10000);
\\ Now print the first 32 elements in the desired format
for (i = 1, 32,{
print1(rios[i]," ")
});
print("")
\\ Print the number of digits for the 1000th and 10000th Riordan numbers
print("The 1,000th Riordan has ", #digits(rios[1000]), " digits.");
print("The 10,000th Riordan has ", #digits(rios[10000]), " digits.");
</syntaxhighlight>
{{out}}
<pre>
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595 13393689 37458330 105089229 295673994 834086421 2358641376 6684761125 18985057351 54022715451 154000562758 439742222071 1257643249140
The 1,000th Riordan has 472 digits.
The 10,000th Riordan has 4765 digits.
</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl" line>use v5.36;
use bigint try => 'GMP';
use experimental <builtin for_list>;
use List::Util 'max';
Line 1,349 ⟶ 1,658:
The one thousandth: 51077756867821111314..79942013897484633052 (472 digits)
The ten thousandth: 19927418577260688844..71395322020211157137 (4765 digits)</pre>
=={{header|RPL}}==
{{works with|HP|28}}
Needed to use unsigned integers to avoid the loss of the last digit of a(31).
≪ { #1 #0 }
'''WHILE''' DUP2 SIZE 1 - > '''REPEAT'''
DUP SIZE 1 -
DUP2 GETI 3 * 4 ROLLD
GET 2 * ROT +
OVER * SWAP 2 + /
+
'''END''' SWAP DROP
≫ '<span style="color:blue">RIORDAN</span>' STO
31 <span style="color:blue">RIORDAN</span>
{{out}}
<pre>
1: { #1d #0d #1d #1d #3d #6d #15d #36d #91d #232d #603d #1585d #4213d 11298d #30537d #83097d #227475d #625992d #1730787d #4805595d #13393689d #37458330d #105089229d #295673994d #834086421d #2358641376d #6684761125d #18985057351d #54022715451d #154000562758d #439742222071d #1257643249140d }
</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
import java.math.BigInteger
import scala.collection.mutable.ArrayBuffer
object RiordanNumbers extends App {a
val limit = 10000
val THREE = BigInteger.valueOf(3)
val riordans: ArrayBuffer[BigInteger] = ArrayBuffer.fill(limit)(BigInteger.ZERO)
riordans(0) = BigInteger.ONE
riordans(1) = BigInteger.ZERO
for (n <- 2 until limit) {
val term = BigInteger.TWO.multiply(riordans(n - 1)).add(THREE.multiply(riordans(n - 2)))
riordans(n) = BigInteger.valueOf(n - 1).multiply(term).divide(BigInteger.valueOf(n + 1))
}
println("The first 32 Riordan numbers:")
for (i <- 0 until 32) {
print(f"${riordans(i)}%14d")
if (i % 4 == 3) println()
else print(" ")
}
println()
List(1000, 10000).foreach { count =>
val length = riordans(count - 1).toString.length
println(s"The ${count}th Riordan number has $length digits")
}
}
</syntaxhighlight>
{{out}}
<pre>
The first 32 Riordan numbers:
1 0 1 1
3 6 15 36
91 232 603 1585
4213 11298 30537 83097
227475 625992 1730787 4805595
13393689 37458330 105089229 295673994
834086421 2358641376 6684761125 18985057351
54022715451 154000562758 439742222071 1257643249140
The 1000th Riordan number has 472 digits
The 10000th Riordan number has 4765 digits
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program riordan;
a := {[0, 1], [1, 0]};
loop for n in [2..9999] do
a(n) := (n-1)*(2*a(n-1) + 3*a(n-2)) div (n+1);
end loop;
loop for n in [0..31] do
putchar(lpad(str a(n), 15));
if n mod 4=3 then print; end if;
end loop;
loop for n in [999, 9999] do
print("The", str (n+1)+"th Riordan number has", #str a(n), "digits.");
end loop;
end program;</syntaxhighlight>
{{out}}
<pre> 1 0 1 1
3 6 15 36
91 232 603 1585
4213 11298 30537 83097
227475 625992 1730787 4805595
13393689 37458330 105089229 295673994
834086421 2358641376 6684761125 18985057351
54022715451 154000562758 439742222071 1257643249140
The 1000th Riordan number has 472 digits.
The 10000th Riordan number has 4765 digits.</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func riordan(n) is cached {
return 1 if (n == 0)
return 0 if (n == 1)
(n-1) * (2*__FUNC__(n-1) + 3*__FUNC__(n-2)) / (n+1)
}
say 32.of(riordan)
for n in (1e3, 1e4) {
var s = Str(riordan(n-1))
say "#{'%6s' % n.commify}th term: #{s.first(20)}..#{s.last(20)} (#{s.len} digits)"
}</syntaxhighlight>
{{out}}
<pre>
[1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140]
1,000th term: 51077756867821111314..79942013897484633052 (472 digits)
10,000th term: 19927418577260688844..71395322020211157137 (4765 digits)
</pre>
=={{header|Wren}}==
{{libheader|Wren-gmp}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||