Riordan numbers

Riordan numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

• OEIS:A005043 - Riordan numbers

F#

<lang fsharp> // Riordan numbers. Nigel Galloway: August 19th., 2022 let r()=seq{yield 1I; yield 0I; yield! Seq.unfold(fun(n,n1,n2)->let r=(n-1I)*(2I*n1+3I*n2)/(n+1I) in Some(r,(n+1I,r,n1)))(2I,0I,1I)} let n=r()|>Seq.take 10000|>Array.ofSeq in n|>Array.take 32|>Seq.iter(printf "%A "); printfn "\nr[999] has %d digits\nr[9999] has %d digits" ((string n.[999]).Length) ((string n.[9999]).Length) </lang>

Output:

1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595 13393689 37458330 105089229 95673994 834086421 2358641376 6684761125 18985057351 54022715451 154000562758 439742222071 1257643249140
r[999] has 472 digits
r[9999] has 4765 digits

J

Sequence extender:<lang J>riordanext=: (, (<: % >:)@# * 3 2 +/ .* _2&{.)</lang> Task example:<lang J> riordanext^:(30) 1x 0 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</lang>Stretch:<lang J> #":(1e3-1){riordanext^:(1e3) x:1 0 472

  #":(1e4-1){riordanext^:(1e4) x:1 0

4765</lang>

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

Library: Wren-gmp

Library: Wren-fmt

<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)