Riordan numbers: Difference between revisions
(Added Wren) |
Thundergnat (talk | contribs) (typo) |
||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
Riordan numbers show up in several places in set theory. They are closely related to [[Motzkin numbers]], and may be used to |
Riordan numbers show up in several places in set theory. They are closely related to [[Motzkin numbers]], and may be used to derive them. |
||
Riordan numbers comprise the sequence '''a''' where: |
Riordan numbers comprise the sequence '''a''' where: |
Revision as of 19:44, 18 August 2022
Riordan numbers show up in several places in set theory. They are closely related to Motzkin numbers, and may be used to derive them.
Riordan numbers comprise the sequence a where:
a(0) = 1, a(1) = 0, for subsequent terms, a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1)
There are other generating functions, and you are free to use one most convenient for your language.
- Task
- Find and display the first 32 Riordan numbers.
- Stretch
- Find and display the digit count of the 1,000th Riordan number.
- Find and display the digit count of the 10,000th Riordan number.
- See also
Raku
<lang perl6>use Lingua::EN::Numbers;
my @riordan = 1, 0, { state $n = 1; (++$n - 1) / ($n + 1) × (3 × $^a + 2 × $^b) } … *;
my $upto = 32; say "First {$upto.&cardinal} Riordan numbers:\n" ~ @riordan[^$upto]».&comma».fmt("%17s").batch(4).join("\n") ~ "\n";
sub abr ($_) { .chars < 41 ?? $_ !! .substr(0,20) ~ '..' ~ .substr(*-20) ~ " ({.chars} digits)" }
say "The {.Int.&ordinal}: " ~ abr @riordan[$_ - 1] for 1e3, 1e4</lang>
- Output:
First thirty-two Riordan numbers: 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 one thousandth: 51077756867821111314..79942013897484633052 (472 digits) The ten thousandth: 19927418577260688844..71395322020211157137 (4765 digits)
Wren
<lang ecmascript>import "./gmp" for Mpz import "./fmt" for Fmt
var limit = 10000 var a = List.filled(limit, null) a[0] = Mpz.one a[1] = Mpz.zero for (n in 2...limit) {
a[n] = (a[n-1] * 2 + a[n-2] * 3) * (n-1) / (n+1)
} System.print("First 32 Riordan numbers:") Fmt.tprint("$,17i", a[0..31], 4) System.print() for (i in [1e3, 1e4]) {
Fmt.print("$,8r: $20a ($,d digits)", i, a[i-1], a[i-1].toString.count)
}</lang>
- Output:
First 32 Riordan numbers: 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 1,000th: 51077756867821111314...79942013897484633052 (472 digits) 10,000th: 19927418577260688844...71395322020211157137 (4,765 digits)