Boustrophedon transform

Boustrophedon transform 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.

This page uses content from Wikipedia. The original article was at Boustrophedon transform. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

A boustrophedon transform is a procedure which maps one sequence to another using a series of integer additions.

Generally speaking, given a sequence: $(a_{0},a_{1},a_{2},\ldots )$, the boustrophedon transform yields another sequence: $(b_{0},b_{1},b_{2},\ldots )$, where $b_{0}$ is likely defined equivalent to $a_{0}$.

There are a few different ways to effect the transform. You may construct a boustrophedon triangle and read off the edge values, or, may use the recurrence relationship:

$T_{k,0}=a_{k}$

$T_{k,n}=T_{k,n-1}+T_{k-1,k-n}$

${\text{with }}$

$\quad k,n\in \mathbb {N}$

$\quad k\geq n>0$.

The transformed sequence is defined by $b_{n}=T_{n,n}$ (for $T_{2,2}$ and greater indices).

You are free to use a method most convenient for your language. If the boustrophedon transform is provided by a built-in, or easily and freely available library, it is acceptable to use that (with a pointer to where it may be obtained).

Task

• Write a procedure (routine, function, subroutine, whatever it may be called in your language) to perform a boustrophedon transform to a given sequence.
• Use that routine to perform a boustrophedon transform on a few representative sequences. Show the first fifteen values from the transformed sequence.

Use the following sequences for demonstration:

• $(1,0,0,0,\ldots )$ ( one followed by an infinite series of zeros )
• $(1,1,1,1,\ldots )$ ( an infinite series of ones )
• $(1,-1,1,-1,\ldots )$ ( (-1)^n: alternating 1, -1, 1, -1 )
• $(2,3,5,7,11,\ldots )$ ( sequence of prime numbers )
• $(1,1,2,3,5,\ldots )$ ( sequence of Fibonacci numbers )
• $(1,1,2,6,24,\ldots )$ ( sequence of factorial numbers )

Stretch

If your language supports big integers, show the first and last 20 digits, and the digit count of the 1000th element of each sequence.

See also

• Wikipedia - Boustrophedon transform
• OEIS:A000111 - Euler, or up/down numbers
• OEIS:A000667 - Boustrophedon transform of all-1's sequence
• OEIS:A062162 - Boustrophedon transform of (-1)^n
• OEIS:A000747 - Boustrophedon transform of primes
• OEIS:A000744 - Boustrophedon transform of Fibonacci numbers
• OEIS:A230960 - Boustrophedon transform of factorials

Raku

sub boustrophedon-transform (@seq) { map *.tail, ([@seq[0]], {[[\+] flat @seq[++$ ], .reverse]}…*) }

sub abbr ($_) { .chars < 41 ?? $_ !! .substr(0,20) ~ '…' ~ .substr(*-20) ~ " ({.chars} digits)" }

for '1 followed by 0\'s A000111', (flat 1, 0 xx *),
    'All-1\'s           A000667', (flat 1 xx *),
    '(-1)^n             A062162', (flat 1, [\×] -1 xx *),
    'Primes             A000747', (^∞ .grep: &is-prime),
    'Fibbonaccis        A000744', (1,1,*+*…*),
    'Factorials         A230960', (1,|[\×] 1..∞)
  -> $name, $seq
{ say "\n$name:\n" ~ (my $b-seq = boustrophedon-transform $seq)[^15] ~ "\n1000th term: " ~ abbr $b-seq[999] }

Output:

1 followed by 0's A000111:
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
1000th term: 61065678604283283233…63588348134248415232 (2369 digits)

All-1's           A000667:
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
1000th term: 29375506567920455903…86575529609495110509 (2370 digits)

(-1)^n             A062162:
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
1000th term: 12694307397830194676…15354198638855512941 (2369 digits)

Primes             A000747:
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
1000th term: 13250869953362054385…82450325540640498987 (2371 digits)

Fibbonaccis        A000744:
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
1000th term: 56757474139659741321…66135597559209657242 (2370 digits)

Factorials         A230960:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
1000th term: 13714256926920345740…19230014799151339821 (2566 digits)