# Boustrophedon transform

Boustrophedon transform
You are encouraged to solve this task according to the task description, using any language you may know.
 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: ${\displaystyle (a_{0},a_{1},a_{2},\ldots )}$, the boustrophedon transform yields another sequence: ${\displaystyle (b_{0},b_{1},b_{2},\ldots )}$, where ${\displaystyle b_{0}}$ is likely defined equivalent to ${\displaystyle 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:

${\displaystyle T_{k,0}=a_{k}}$
${\displaystyle T_{k,n}=T_{k,n-1}+T_{k-1,k-n}}$
${\displaystyle {\text{with }}}$
${\displaystyle \quad k,n\in \mathbb {N} }$
${\displaystyle \quad k\geq n>0}$.

The transformed sequence is defined by ${\displaystyle b_{n}=T_{n,n}}$ (for ${\displaystyle 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).

• 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:
• ${\displaystyle (1,0,0,0,\ldots )}$ ( one followed by an infinite series of zeros )
• ${\displaystyle (1,1,1,1,\ldots )}$ ( an infinite series of ones )
• ${\displaystyle (1,-1,1,-1,\ldots )}$ ( (-1)^n: alternating 1, -1, 1, -1 )
• ${\displaystyle (2,3,5,7,11,\ldots )}$ ( sequence of prime numbers )
• ${\displaystyle (1,1,2,3,5,\ldots )}$ ( sequence of Fibonacci numbers )
• ${\displaystyle (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.

## ALGOL 68

Basic task - assumes LONG INT is large enough, e.g. 64 bits, 39 bits would do...

BEGIN # apply a Boustrophedon Transform to a few sequences                   #
# returns the sequence generated by transforming s                       #
PROC boustrophedon transform = ( []LONG INT s )[]LONG INT:
BEGIN
[]LONG INT a = s[ AT 0 ];      # a is s with lower bound revised to 0 #
[ 0 : UPB a, 0 : UPB a ]LONG INT t;
t[ 0, 0 ] := a[ 0 ];
FOR k TO UPB a DO
t[ k, 0 ] := a[ k ];
FOR n TO k DO
t[ k, n ] := t[ k, n - 1 ] + t[ k - 1, k - n ]
OD
OD;
[ 0 : UPB a ]LONG INT b;
FOR n FROM 0 TO UPB b DO b[ n ] := t[ n, n ] OD;
b
END # boustrophedon transform # ;
# prints the transformed sequence generated from a                       #
PROC print transform = ( STRING name, []LONG INT a )VOID:
BEGIN
[]LONG INT b = boustrophedon transform( a );
print( ( name, " generates:", newline ) );
FOR i FROM LWB b TO UPB b DO print( ( " ", whole( b[ i ], 0 ) ) ) OD;
print( ( newline ) )
END # print transform # ;
BEGIN # test cases                                                       #
print transform( "1, 0, 0, 0, ..."
, []LONG INT( 1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 )
);
print transform( "1, 1, 1, 1, ..."
, []LONG INT( 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1 )
);
print transform( "1, -1, 1, -1, ..."
, []LONG INT( 1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1 )
);
print transform( "primes"
, []LONG INT( 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 )
);
print transform( "fibnonacci numbers"
, []LONG INT( 1,  1,  2,  3,  5,  8, 13, 21, 34, 55, 89, 144, 233, 377, 610 )
);
[ 0 : 14 ]LONG INT factorial;
factorial[ 0 ] := 1;
FOR i TO UPB factorial DO factorial[ i ] := i * factorial[ i - 1 ] OD;
print transform( "factorial numbers",  factorial )
END
END
Output:
1, 0, 0, 0, ... generates:
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
1, 1, 1, 1, ... generates:
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
1, -1, 1, -1, ... generates:
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
primes generates:
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
fibnonacci numbers generates:
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
factorial numbers generates:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547


## C++

#include <cstdint>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<uint32_t> primes;
std::unordered_map<uint32_t, uint64_t> fibonacci_cache;
std::unordered_map<uint32_t, uint64_t> factorial_cache;

void sieve_primes(const uint32_t& limit) {
primes.emplace_back(2);
const uint32_t half_limit = ( limit + 1 ) / 2;
std::vector<bool> composite(half_limit);
for ( uint32_t i = 1, p = 3; i < half_limit; p += 2, ++i ) {
if ( ! composite[i] ) {
primes.emplace_back(p);
for ( uint32_t a = i + p; a < half_limit; a += p ) {
composite[a] = true;
}
}
}
}

uint64_t one_one(const uint32_t& number) {
return ( number == 0 ) ? 1 : 0;
}

uint64_t all_ones(const uint32_t& number) {
return 1;
}

uint64_t alternating(const uint32_t& number) {
return ( number % 2 == 0 ) ? +1 : -1;
}

uint64_t prime(const uint32_t& number) {
return primes[number];
}

uint64_t fibonacci(const uint32_t& number) {
if ( ! fibonacci_cache.contains(number) ) {
if ( number == 0 || number == 1 ) {
fibonacci_cache[number] = 1;
} else {
fibonacci_cache[number] = fibonacci(number - 2) + fibonacci(number - 1);
}
}
return fibonacci_cache[number];
}

uint64_t factorial(const uint32_t& number) {
if ( ! factorial_cache.contains(number) ) {
uint64_t value = 1;
for ( uint32_t i = 2; i <= number; ++i ) {
value *= i;
}
factorial_cache[number] = value;
}
return factorial_cache[number];
}

class Boustrophedon_Iterator {
public:
Boustrophedon_Iterator(const std::function<uint64_t(uint32_t)>& aSequence) : sequence(aSequence) {}

uint64_t next() {
index += 1;
return transform(index, index);
}

private:
uint64_t transform(const uint32_t& k, const uint32_t& n) {
if ( n == 0 ) {
return sequence(k);
}

if ( ! cache[k].contains(n) ) {
const uint64_t value = transform(k, n - 1) + transform(k - 1, k - n);
cache[k][n] = value;
}
return cache[k][n];
}

int32_t index = -1;
std::function<uint64_t(uint32_t)> sequence;
std::unordered_map<uint32_t, std::unordered_map<uint32_t, uint64_t>> cache;
};

void display(const std::string& title, const std::function<uint64_t(uint32_t)>& sequence) {
std::cout << title << std::endl;
Boustrophedon_Iterator iterator = Boustrophedon_Iterator(sequence);
for ( uint32_t i = 1; i <= 15; ++i ) {
std::cout << iterator.next() << " ";
}
std::cout << std::endl << std::endl;
}

int main() {
sieve_primes(8'000);

display("One followed by an infinite series of zeros -> A000111", one_one);
display("An infinite series of ones -> A000667", all_ones);
display("(-1)^n: alternating 1, -1, 1, -1 -> A062162", alternating);
display("Sequence of prime numbers -> A000747", prime);
display("Sequence of Fibonacci numbers -> A000744", fibonacci);
display("Sequence of factorial numbers -> A230960", factorial);
}

Output:
One followed by an infinite series of zeros -> A000111
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981

An infinite series of ones -> A000667
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574

(-1)^n: alternating 1, -1, 1, -1 -> A062162
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530

Sequence of prime numbers -> A000747
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691

Sequence of Fibonacci numbers -> A000744
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189

Sequence of factorial numbers -> A230960
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547


## EasyLang

cache[][] = [ ]
a[] = [ ]
#
func T k n .
if n = 1
return a[k]
.
if cache[k][n] = 0
cache[k][n] = T k (n - 1) + T (k - 1) (k - n + 1)
.
return cache[k][n]
.
#
proc boustrophedon . .
k = len a[]
cache[][] = [ ]
len cache[][] k
for i to k
len cache[i][] k
.
b[] &= a[1]
for n = 2 to k
b[] &= T n n
.
print b[]
.
len a[] 15
print "1 followed by 0's:"
a[1] = 1
boustrophedon
#
print "\nAll 1's:"
proc mkall1 n . a[] .
a[] = [ ]
while len a[] <> n
a[] &= 1
.
.
mkall1 15 a[]
boustrophedon
#
print "\nAlternating 1, -1"
proc mkalt n . a[] .
a[] = [ ]
h = 1
while len a[] <> n
a[] &= h
h *= -1
.
.
mkalt 15 a[]
boustrophedon
#
print "\nPrimes:"
func isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
proc mkprimes n . a[] .
a[] = [ ]
i = 2
while len a[] <> n
if isprim i = 1
a[] &= i
.
i += 1
.
.
mkprimes 15 a[]
boustrophedon
#
print "\nFibonacci numbers:"
proc mkfibon n . a[] .
a[] = [ 1 ]
val = 1
while len a[] <> n
h = prev + val
prev = val
val = h
a[] &= val
.
.
mkfibon 15 a[]
boustrophedon
print "\nFactorials:"
proc mkfact n . a[] .
a[] = [ ]
f = 1
while len a[] <> n
a[] &= f
f *= len a[]
.
.
mkfact 15 a[]
boustrophedon
Output:
1 followed by 0's:
[ 1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981 ]

All 1's:
[ 1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574 ]

Alternating 1, -1
[ 1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530 ]

Primes:
[ 2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691 ]

Fibonacci numbers:
[ 1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189 ]

Factorials:
[ 1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547 ]


## FreeBASIC

### Basic

Translation of: Wren
Function T(Byval k As Integer, Byval n As Integer, a() As Integer, cache() As Integer) As Integer
If n = 0 Then
Return a(k)
Elseif cache(k * Ubound(a) + n) <> 0 Then
Return cache(k * Ubound(a) + n)
Else
cache(k * Ubound(a) + n) = T(k, n - 1, a(), cache()) + T(k - 1, k - n, a(), cache())
Return cache(k * Ubound(a) + n)
End If
End Function

Sub Boustrophedon(a() As Integer)
Dim As Integer k = Ubound(a)
Dim As Integer cache(k * k + k)
Dim As Integer b(k)

b(0) = a(0)
For n As Integer = 1 To k
b(n) = T(n, n, a(), cache())
Next

Print "[";
For n As Integer = 0 To k
Print b(n); ",";
Next
Print Chr(8); !" ]\n"
End Sub

Dim As Integer i
Print "1 followed by 0's:"
Dim As Integer a0(14) = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Boustrophedon(a0())

Print "All 1's:"
Dim As Integer a1(14) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Boustrophedon(a1())

Print "Alternating 1, -1:"
Dim As Integer a2(14)
For i = 0 To 14
a2(i) = Iif((i\2 = i/2), 1, -1)
Next i
Boustrophedon(a2())

Print "Primes:"
Sub primeSieve(n As Integer, primes() As Integer)
Redim primes(n - 1)
Dim As Integer j, i = 2, count = 0
While count < n
j = 2
While j <= i \ 2
If i Mod j = 0 Then Exit While
j += 1
Wend
If j > i \ 2 Then
primes(count) = i
count += 1
End If
i += 1
Wend
End Sub
Dim As Integer a3(14)
primeSieve(15, a3())
Boustrophedon(a3())

Print "Fibonacci numbers:"
Dim As Integer a4(14)
a4(0) = 1 ' start from fib(1)
a4(1) = 1
For i = 2 To 14
a4(i) = a4(i-1) + a4(i-2)
Next i
Boustrophedon(a4())

Print "Factorials:"
Dim As Integer a5(14)
a5(0) = 1
For i = 1 To 14
a5(i) = a5(i-1) * i
Next i
Boustrophedon(a5())

Sleep

Output:
1 followed by 0's:
[ 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981 ]

All 1's:
[ 1, 2, 4, 9, 24, 77, 294, 1309, 6664, 38177, 243034, 1701909, 13001604, 107601977, 959021574 ]

Alternating 1, -1:
[ 1, 0, 0, 1, 0, 5, 10, 61, 280, 1665, 10470, 73621, 561660, 4650425, 41441530 ]

Primes:
[ 2, 5, 13, 35, 103, 345, 1325, 5911, 30067, 172237, 1096319, 7677155, 58648421, 485377457, 4326008691 ]

Fibonacci numbers:
[ 1, 2, 5, 14, 42, 144, 563, 2526, 12877, 73778, 469616, 3288428, 25121097, 207902202, 1852961189 ]

Factorials:
[ 1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547 ]

## F#

### The function

This task uses Extensible Prime Generator (F#)

// Boustrophedon transform. Nigel Galloway:October 26th., 2023
let fG n g=let rec fG n g=[match n with h::[]->yield g+h |h::t->yield g+h; yield! fG t (g+h)] in [yield g; yield! fG n g]|>List.rev


printfn "zeroes"; Seq.unfold(fun n->Some(n,0I))1I|>Seq.take 15|>Boustrophedon|>Seq.iter(printf "%A "); printfn ""
let n=sprintf $"%A{Seq.unfold(fun n->Some(n,0I))1I|>Boustrophedon|>Seq.item 999}" in printfn "%s ... %s (%d digits)" n[0..19] n[n.Length-20..n.Length] (n.Length) printfn "ones"; Seq.unfold(fun n->Some(n,n))1I|>Seq.take 15|>Boustrophedon|>Seq.iter(printf "%A "); printfn "" let n=sprintf$"%A{Seq.unfold(fun n->Some(n,n))1I|>Boustrophedon|>Seq.item 999}" in printfn "%s ... %s  (%d digits)" n[0..19] n[n.Length-20..n.Length] (n.Length)
printfn "1,-1,1,-1....."; Seq.unfold(fun n->Some(n,-n))1I|>Boustrophedon|>Seq.take 15|>Seq.iter(printf "%A "); printfn ""
let n=sprintf $"%A{Seq.unfold(fun n->Some(n,-n))1I|>Boustrophedon|>Seq.item 999}" in printfn "%s ... %s (%d digits)" n[0..19] n[n.Length-20..n.Length] (n.Length) printfn "factorials"; Seq.unfold(fun(n,g)->Some(n,(n*g,g+1I)))(1I,1I)|>Boustrophedon|>Seq.take 15|>Seq.iter(printf "%A "); printfn "" let n=sprintf$"%A{Seq.unfold(fun(n,g)->Some(n,(n*g,g+1I)))(1I,1I)|>Boustrophedon|>Seq.item 999}" in printfn "%s ... %s  (%d digits)" n[0..19] n[n.Length-20..n.Length] (n.Length)
printfn "primes"; let p=primes() in Seq.initInfinite(fun _->bigint(p()))|>Boustrophedon|>Seq.take 15|>Seq.iter(printf "%A "); printfn ""
let n=sprintf $"%A{let p=primes() in Seq.initInfinite(fun _->bigint(p()))|>Boustrophedon|>Seq.item 999}" in printfn "%s ... %s (%d digits)" n[0..19] n[n.Length-20..n.Length] (n.Length)  Output: zeroes 1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981 61065678604283283233 ... 63588348134248415232 (2369 digits) ones 1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574 29375506567920455903 ... 86575529609495110509 (2370 digits) 1,-1,1,-1..... 1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530 12694307397830194676 ... 15354198638855512941 (2369 digits) factorials 1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547 13714256926920345740 ... 19230014799151339821 (2566 digits) primes 2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691 13250869953362054385 ... 82450325540640498987 (2371 digits)  ## J Implementation: b=: {{ M=: (u i.y),.(y-0 1)$x:_
B=:{{
if. x<y do.0
else. i=. <x,y
if. _>i{M do. i{M
else. r=. (x B y-1)+(x-1) B x-y
r[M=: r i} M
end.
end.
}}"0
(<0 1)|:B/~i.y
}}


   =&0 b 15
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
1"0 b 15
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
_1x&^ b 15
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
p: b 15
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
phi=: -:>:%:5
{{ <.0.5+(phi^y)%%:5 }} b 15
0 1 3 8 25 85 334 1497 7635 43738 278415 1949531 14893000 123254221 1098523231
!@x: b 15
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547


### Alternate implementation

Instead of relying on recursion and memoization, we can deliberately perform the operations in the correct order:

B=: {{
M=. |:y#,:u i.y
for_i.(#~>:/"1)1+(,#:i.@*)~y-1 do.
M=. M (<i)}~(M{~<i-0 1)+M{~<(-/\i)-1 0
end.
M|:~<1 0
}}


Here, we start with a square matrix with the a values in sequence in the first column (first line). Then we fill in the remaining needed T values in row major order (for loop). Finally, we extract the diagonal (last line). Usage and results are the same as before.

## Java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;

public final class BoustrophedonTransform {

public static void main(String[] args) {

Function<Integer, BigInteger> oneOne = x -> ( x == 0 ) ? BigInteger.ONE : BigInteger.ZERO;
Function<Integer, BigInteger> alternating = x -> ( x % 2 == 0 ) ? BigInteger.ONE : BigInteger.ONE.negate();

display("One followed by an infinite series of zeros -> A000111", oneOne);
display("An infinite series of ones -> A000667", n -> BigInteger.ONE);
display("(-1)^n: alternating 1, -1, 1, -1 -> A062162", alternating);
display("Sequence of prime numbers -> A000747", n -> primes.get(n));
display("Sequence of Fibonacci numbers -> A000744", n -> fibonacci(n));
display("Sequence of factorial numbers -> A230960", n -> factorial(n));
}

private static void listPrimeNumbersUpTo(int limit) {
primes = new ArrayList<BigInteger>();
final int halfLimit = ( limit + 1 ) / 2;
boolean[] composite = new boolean[halfLimit];
for ( int i = 1, p = 3; i < halfLimit; p += 2, i++ ) {
if ( ! composite[i] ) {
for ( int a = i + p; a < halfLimit; a += p ) {
composite[a] = true;
}
}
}
}

private static BigInteger fibonacci(int number) {
if ( ! fibonacciCache.keySet().contains(number) ) {
if ( number == 0 || number == 1 ) {
fibonacciCache.put(number, BigInteger.ONE);
} else {
fibonacciCache.put(number, fibonacci(number - 2).add(fibonacci(number - 1)));
}
}
return fibonacciCache.get(number);
}

private static BigInteger factorial(int number) {
if ( ! factorialCache.keySet().contains(number) ) {
BigInteger value = BigInteger.ONE;
for ( int i = 2; i <= number; i++ ) {
value = value.multiply(BigInteger.valueOf(i));
}
factorialCache.put(number, value);
}
return factorialCache.get(number);
}

private static String compress(BigInteger number, int size) {
String digits = number.toString();
final int length = digits.length();
if ( length <= 2 * size )  {
return digits;
}
return digits.substring(0, size) + " ... " + digits.substring(length - size) + " (" + length + " digits)";
}

private static void display(String title, Function<Integer, BigInteger> sequence) {
System.out.println(title);
BoustrophedonIterator iterator = new BoustrophedonIterator(sequence);
for ( int i = 1; i <= 15; i++ ) {
System.out.print(iterator.next() + " ");
}
System.out.println();
for ( int i = 16; i < 1_000; i++ ) {
iterator.next();
}
System.out.println("1,000th element: " + compress(iterator.next(), 20) + System.lineSeparator());
}

private static List<BigInteger> primes;
private static Map<Integer, BigInteger> fibonacciCache = new HashMap<Integer, BigInteger>();
private static Map<Integer, BigInteger> factorialCache = new HashMap<Integer, BigInteger>();

}

final class BoustrophedonIterator {

public BoustrophedonIterator(Function<Integer, BigInteger> aSequence) {
sequence = aSequence;
}

public BigInteger next() {
index += 1;
return transform(index, index);
}

private BigInteger transform(int k, int n) {
if ( n == 0 ) {
return sequence.apply(k);
}

Pair pair = new Pair(k, n);
if ( ! cache.keySet().contains(pair) ) {
final BigInteger value = transform(k, n - 1).add(transform(k - 1, k - n));
cache.put(pair, value);
}
return cache.get(pair);
}

private record Pair(int k, int n) {}

private int index = -1;
private Function<Integer, BigInteger> sequence;
private Map<Pair, BigInteger> cache = new HashMap<Pair, BigInteger>();

}

Output:
One followed by an infinite series of zeros -> A000111
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
1,000th element: 61065678604283283233 ... 63588348134248415232 (2369 digits)

An infinite series of ones -> A000667
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
1,000th element: 29375506567920455903 ... 86575529609495110509 (2370 digits)

(-1)^n: alternating 1, -1, 1, -1 -> A062162
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
1,000th element: 12694307397830194676 ... 15354198638855512941 (2369 digits)

Sequence of prime numbers -> A000747
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
1,000th element: 13250869953362054385 ... 82450325540640498987 (2371 digits)

Sequence of Fibonacci numbers -> A000744
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
1,000th element: 56757474139659741321 ... 66135597559209657242 (2370 digits)

Sequence of factorial numbers -> A230960
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
1,000th element: 13714256926920345740 ... 19230014799151339821 (2566 digits)


## jq

Works with gojq, the Go implementation of jq

Works with jq, the C implementation of jq, within the limits of IEEE 764 arithmetic

The results for the "stretch" tasks are based on the use of gojq.

### Generic functions

# The stream of Fibonacci numbers beginning with 1, 1, 2, ...
def fibs:
def f: [0,1] | recurse( [.[1], add] );
f | .[1];

# The stream of factorials beginning with 1, 1, 2, 6, 24, ...
def factorials:
def f: recurse( [.[0] + 1, .[0] * .[1]] );
[1, 1] | f | .[1];

# An array of length specified by .
def array($value): [range(0; .) |$value];

# Give a glimpse of the (very large) input number
def glimpse:
tostring
| "\(.[:20]) ... \(.[-20:]) \(length) digits";

### The Boustrophedon transform
def boustrophedon($a): ($a|length) as $k | ($k | array(0)) as $list | {b:$list,
cache: [] }

# input: {cache}, output: {result, cache}
| def T($k;$n):
if $n == 0 then .result =$a[$k] else .cache[$k][$n] as$kn
| if $kn > 0 then .result =$kn
else T($k;$n-1)
| .result as $r | T($k-1; $k-$n)
| .result = $r + .result | .cache[$k][$n] = .result end end; .b[0] =$a[0]
| reduce range(1; $k) as$n (.; T($n;$n) | .b[$n] = .result ) | .b; ### Exercises "1 followed by 0's:", boustrophedon( [1] + (14 | array(0)) ), "\nAll 1's:", boustrophedon(15|array(1)), "\nAlternating 1, -1", boustrophedon( [range(0;7) | 1, -1] + [1] ), "\nPrimes:", boustrophedon([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]), "\nFibonacci numbers:", boustrophedon([limit(15; fibs)]), "\nFactorials:", boustrophedon([limit(15; factorials)]), ## Stretch tasks require gojq "\nGlimpse of 1000th element for the Fibonaccis", (boustrophedon([limit(1000; fibs)]) | .[999] | glimpse), "\nGlimpse of 1000th element for the factorials:", (boustrophedon([limit(1000; factorials)]) | .[999] | glimpse) Output: 1 followed by 0's: [1,1,1,2,5,16,61,272,1385,7936,50521,353792,2702765,22368256,199360981] All 1's: [1,2,4,9,24,77,294,1309,6664,38177,243034,1701909,13001604,107601977,959021574] Alternating 1, -1 [1,0,0,1,0,5,10,61,280,1665,10470,73621,561660,4650425,41441530] Primes: [2,5,13,35,103,345,1325,5911,30067,172237,1096319,7677155,58648421,485377457,4326008691] Fibonacci numbers: [1,2,5,14,42,144,563,2526,12877,73778,469616,3288428,25121097,207902202,1852961189] Factorials: [1,2,5,17,73,381,2347,16701,134993,1222873,12279251,135425553,1627809401,21183890469,296773827547] Glimpse of the 1000th element for the Fibonaccis: 56757474139659741321 ... 66135597559209657242 2370 digits Glimpse of 1000th element for the factorials: 13714256926920345740 ... 19230014799151339821 2566 digits  ## Julia using Primes function bous!(triangle, k, n, seq) n == 1 && return BigInt(seq[k]) triangle[k][n] > 0 && return triangle[k][n] return (triangle[k][n] = bous!(triangle, k, n - 1, seq) + bous!(triangle, k - 1, k - n + 1, seq)) end boustrophedon(seq) = (n = length(seq); t = [zeros(BigInt, j) for j in 1:n]; [bous!(t, i, i, seq) for i in 1:n]) boustrophedon(f, range) = boustrophedon(map(f, range)) fib(n) = (z = BigInt(0); ccall((:__gmpz_fib_ui, :libgmp), Cvoid, (Ref{BigInt}, Culong), z, n); z) tests = [ ((n) -> n < 2, 1:1000, "One followed by an infinite series of zeros -> A000111"), ((n) -> 1, 1:1000, "An infinite series of ones -> A000667"), ((n) -> isodd(n) ? 1 : -1, 1:1000, "(-1)^n: alternating 1, -1, 1, -1 -> A062162"), ((n) -> prime(n), 1:1000, "Sequence of prime numbers -> A000747"), ((n) -> fib(n), 1:1000, "Sequence of Fibonacci numbers -> A000744"), ((n) -> factorial(BigInt(n)), 0:999, "Sequence of factorial numbers -> A230960") ] for (f, rang, label) in tests println(label) arr = boustrophedon(f, rang) println(Int64.(arr[1:15])) s = string(arr[1000]) println(s[1:20], " ... ", s[end-19:end], " ($(length(s)) digits)\n")
end

Output:
One followed by an infinite series of zeros -> A000111
[1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981]
61065678604283283233 ... 63588348134248415232 (2369 digits)

An infinite series of ones -> A000667
[1, 2, 4, 9, 24, 77, 294, 1309, 6664, 38177, 243034, 1701909, 13001604, 107601977, 959021574]
29375506567920455903 ... 86575529609495110509 (2370 digits)

(-1)^n: alternating 1, -1, 1, -1 -> A062162
[1, 0, 0, 1, 0, 5, 10, 61, 280, 1665, 10470, 73621, 561660, 4650425, 41441530]
12694307397830194676 ... 15354198638855512941 (2369 digits)

Sequence of prime numbers -> A000747
[2, 5, 13, 35, 103, 345, 1325, 5911, 30067, 172237, 1096319, 7677155, 58648421, 485377457, 4326008691]
13250869953362054385 ... 82450325540640498987 (2371 digits)

Sequence of Fibonacci numbers -> A000744
[1, 2, 5, 14, 42, 144, 563, 2526, 12877, 73778, 469616, 3288428, 25121097, 207902202, 1852961189]
56757474139659741321 ... 66135597559209657242 (2370 digits)

Sequence of factorial numbers -> A230960
[1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547]
13714256926920345740 ... 19230014799151339821 (2566 digits)


## Maxima

/* Functions used */
boustrophedon_zero_tail[k,n]:=if n=0 then boustrophedon_zero_tail[k,n]:apply(lambda([x],if x=0 then 1 else 0),[k]) else boustrophedon_zero_tail[k,n-1]+boustrophedon_zero_tail[k-1,k-n]$boustrophedon_ones[k,n]:=if n=0 then boustrophedon_ones[k,n]:1 else boustrophedon_ones[k,n-1]+boustrophedon_ones[k-1,k-n]$

boustrophedon_alternating[k,n]:=if n=0 then boustrophedon_alternating[k,n]:(-1)^k else boustrophedon_alternating[k,n-1]+boustrophedon_alternating[k-1,k-n]$prime_list(n):=block(init:2,append([init],makelist(init:next_prime(init),i,n)))$
boustrophedon_primes[k,n]:=if n=0 then boustrophedon_primes[k,n]:last(prime_list(k)) else boustrophedon_primes[k,n-1]+boustrophedon_primes[k-1,k-n]$boustrophedon_fib[k,n]:=if n=0 then boustrophedon_fib[k,n]:fib(k+1) else boustrophedon_fib[k,n-1]+boustrophedon_fib[k-1,k-n]$

boustrophedon_factorial[k,n]:=if n=0 then boustrophedon_factorial[k,n]:k! else boustrophedon_factorial[k,n-1]+boustrophedon_factorial[k-1,k-n]$/* Test cases */ makelist(boustrophedon_zero_tail[i,i],i,0,14); makelist(boustrophedon_ones[i,i],i,0,14); makelist(boustrophedon_alternating[i,i],i,0,14); makelist(boustrophedon_primes[i,i],i,0,14); makelist(boustrophedon_fib[i,i],i,0,14); makelist(boustrophedon_factorial[i,i],i,0,14);  Output: [1,1,1,2,5,16,61,272,1385,7936,50521,353792,2702765,22368256,199360981] [1,2,4,9,24,77,294,1309,6664,38177,243034,1701909,13001604,107601977,959021574] [1,0,0,1,0,5,10,61,280,1665,10470,73621,561660,4650425,41441530] [2,5,13,35,103,345,1325,5911,30067,172237,1096319,7677155,58648421,485377457,4326008691] [1,2,5,14,42,144,563,2526,12877,73778,469616,3288428,25121097,207902202,1852961189] [1,2,5,17,73,381,2347,16701,134993,1222873,12279251,135425553,1627809401,21183890469,296773827547]  ## Nim Library: Nim-Integers import std/[strformat, strutils, tables] import Integers # Build list of primes.import std/[strformat, strutils, tables] import Integers ### Build list of primes ### const N = 3100 var composite: array[(N - 3) shr 1, bool] var n = 3 while n * n <= N: if not composite[(n - 3) shr 1]: for k in countup(n * n, composite.high, 2 * n): composite[(k - 3) shr 1] = true inc n, 2 var primes = @[2] for i, comp in composite: if not comp: primes.add 2 * i + 3 if primes.len < 1000: quit &"Not enough primes ({primes.len}). Increase sieve size.", QuitFailure ### Sequences ### # Common type for sequence procedures. type SeqProc = proc(n: Natural): Integer proc seq1(n: Natural): Integer = result = if n == 0: 1 else: 0 proc seq2(n: Natural): Integer = result = 1 proc seq3(n: Natural): Integer = result = if (n and 1) == 0: 1 else: -1 proc seq4(n: Natural): Integer = result = primes[n] var fibCache: Table[Natural, Integer] proc seq5(n: Natural): Integer = if n in fibCache: return fibCache[n] if n == 0 or n == 1: return 1 result = seq5(n - 1) + seq5(n - 2) fibCache[n] = result proc seq6(n: Natural): Integer = result = factorial(n) ### Boustrophedon transform ### iterator boustrophedon(a: SeqProc): (int, Integer) = var bousCache: Table[(Natural, Natural), Integer] proc t(k, n: Natural): Integer = if (k, n) in bousCache: return bousCache[(k, n)] if n == 0: return a(k) result = t(k, n - 1) + t(k - 1, k - n) bousCache[(k, n)] = result var n = 0 while true: yield (n, t(n, n)) inc n ### Main ### func compressed(str: string; size: int): string = ## Return a compressed value for long strings of digits. if str.len <= 2 * size: str else: &"{str[0..<size]}...{str[^size..^1]} ({str.len} digits)" for (name, s) in {"One followed by an infinite series of zeros": SeqProc(seq1), "Infinite sequence of ones": SeqProc(seq2), "Alternating 1, -1, 1, -1": SeqProc(seq3), "Sequence of prime numbers": SeqProc(seq4), "Sequence of Fibonacci numbers": SeqProc(seq5), "Sequence of factorial numbers": SeqProc(seq6)}: echo name, ':' for n, bn in s.boustrophedon(): if n < 15: stdout.write bn stdout.write if n < 14: ' ' else: '\n' elif n == 999: echo "1000th element: ", compressed($bn, 20)
break
echo()

One followed by an infinite series of zeros:
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
1000th element: 61065678604283283233...63588348134248415232 (2369 digits)

Infinite sequence of ones:
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
1000th element: 29375506567920455903...86575529609495110509 (2370 digits)

Alternating 1, -1, 1, -1:
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
1000th element: 12694307397830194676...15354198638855512941 (2369 digits)

Sequence of prime numbers:
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
1000th element: 13250869953362054385...92714646686153543455 (2371 digits)

Sequence of Fibonacci numbers:
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
1000th element: 56757474139659741321...66135597559209657242 (2370 digits)

Sequence of factorial numbers:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
1000th element: 13714256926920345740...19230014799151339821 (2566 digits)


## Perl

Not really fulfilling the conditions of the stretch goal, but heading a little way down that path.

Translation of: Raku
Library: ntheory
use v5.36; use experimental <builtin for_list>;
use ntheory <factorial lucasu nth_prime vecsum>;

sub abbr ($d) { my$l = length $d;$l < 41 ? $d : substr($d,0,20) . '..' . substr($d,-20) . " ($l digits)" }

sub boustrophedon_transform (@seq) {
my @bt;
my @bx = $seq[0]; for (my$c = 0; $c < @seq;$c++) {
@bx = reverse map { vecsum head $_+1,$seq[$c], @bx } 0 ..$c;
push @bt, $bx[0]; } @bt } my$upto = 100; #1000 way too slow
for my($name,$seq) (
'1 followed by 0\'s A000111', [1, (0) x $upto], 'All-1\'s A000667', [ (1) x$upto],
'(-1)^n             A062162', [1, map { (-1)**$_ } 1..$upto],
'Primes             A000747', [   map { nth_prime $_ } 1..$upto],
'Fibbonaccis        A000744', [   map { lucasu(1, -1, $_) } 1..$upto],
'Factorials         A230960', [1, map { factorial $_ } 1..$upto]
) {
my @bt = boustrophedon_transform @$seq; say "\n$name:\n" . join ' ', @bt[0..14];
say "100th term: " . abbr $bt[$upto-1];
}

Output:
1 followed by 0's A000111:
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
100th term: 45608516616801111821..68991870306963423232 (137 digits)

All-1's           A000667:
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
100th term: 21939873756450413339..30507739683220525509 (138 digits)

(-1)^n             A062162:
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
100th term: 94810791122872999361..65519440121851711941 (136 digits)

Primes             A000747:
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
100th term: 98967625721691921699..78027927576425134967 (138 digits)

Fibbonaccis        A000744:
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
100th term: 42390820205259437020..42168748587048986542 (138 digits)

Factorials         A230960:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
100th term: 31807659526053444023..65546706672657314921 (157 digits)

## Phix

without js -- see below
include mpfr.e

string stretchres = ""
procedure test(sequence ds)
{string desc, sequence s} = ds
integer n = length(s)
sequence t = apply(true,repeat,{0,tagset(n)}),
r15 = repeat("?",15), r1000 = "??"
for k=0 to n-1 do
integer i = k+1, {lo,hi,step} = iff(odd(k)?{k,1,-1}:{2,i,+1})
t[i,step] = s[i]
for j=lo to hi by step do
mpz tk = mpz_init()
t[i][j] = tk
end for
if i<=15 then
r15[i] = mpz_get_str(t[i][-step])
elsif i=1000 then
r1000 = mpz_get_short_str(t[i][-step])
end if
end for
printf(1,"%s:%s\n",{desc,join(r15)})
stretchres &= sprintf("%s[1000]:%s\n",{desc,r1000})
end procedure

function f1000(integer f, sequence v)
sequence res = mpz_inits(1000)
papply(true,f,{res,v})
return res
end function

constant tests = {{"1{0}",mpz_inits(1000,1&repeat(0,999))},
{"{1}",mpz_inits(1000,repeat(1,1000))},
{"+-1",mpz_inits(1000,flatten(repeat({1,-1},500)))},
{"pri",mpz_inits(1000,get_primes(-1000))},
{"fib",f1000(mpz_fib_ui,tagset(1000))},
{"fac",f1000(mpz_fac_ui,tagstart(0,1000))}}
papply(tests,test)
printf(1,"\n%s",stretchres)

Output:
1{0}:1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
{1}:1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
+-1:1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
pri:2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
fib:1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
fac:1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547

1{0}[1000]:61065678604283283233...63588348134248415232 (2,369 digits)
{1}[1000]:29375506567920455903...86575529609495110509 (2,370 digits)
+-1[1000]:12694307397830194676...15354198638855512941 (2,369 digits)
pri[1000]:13250869953362054385...82450325540640498987 (2,371 digits)
fib[1000]:56757474139659741321...66135597559209657242 (2,370 digits)
fac[1000]:13714256926920345740...19230014799151339821 (2,566 digits)


As was noted somewhat obscurely in p2js/mappings ("When step may or may not be negative...") and now more clearly noted in the for loop documentation, for p2js compatibility the inner loop would have to be something like:

with javascript_semantics
...
if odd(k) then
for j=k to 1 by -1 do
mpz tk = mpz_init()
t[i][j] = tk
end for
else
for j=2 to i do
mpz tk = mpz_init()
t[i][j] = tk
end for
end if


## Python

# bt_transform.py by Xing216
from math import factorial
from itertools import islice
from sys import setrecursionlimit
setrecursionlimit(1000000)
def gen_one_followed_by_zeros():
yield 1
while True:
yield 0
def gen_ones():
while True:
yield 1
def gen_alternating_signs():
s = 1
while True:
yield s
s *= -1
def gen_primes():
"""Code by David Eppstein, UC Irvine, 28 Feb 2002 http://code.activestate.com/recipes/117119/"""
D = {}
q = 2
while True:
if q not in D:
yield q
D[q * q] = [q]
else:
for p in D[q]:
D.setdefault(p + q, []).append(p)
del D[q]
q += 1
def gen_fibonacci():
a=0
b=1
while True:
yield b
a,b= b,a+b
def gen_factorials():
f = 0
while True:
yield factorial(f)
f += 1
def compressed(n):
strn = str(n)
return f"{strn[:20]}...{strn[-20:]} ({len(strn)} digits)"
def boustrophedon(a):
# Copied from the Wren Solution
k = len(a)
cache = [None] * k
for i in range(k): cache[i] = [0] * k
b = [0] * k
b[0] = a[0]
def T(k,n):
if n == 0: return a[k]
if cache[k][n] > 0: return cache[k][n]
cache[k][n] = T(k,n-1) + T(k-1,k-n)
return cache[k][n]
for n in range(1,k):
b[n] = T(n,n)
return b
funcs = {"One followed by an infinite series of zeros:":gen_one_followed_by_zeros,
"Infinite sequence of ones:": gen_ones,
"Alternating 1, -1, 1, -1:": gen_alternating_signs,
"Sequence of prime numbers:": gen_primes,
"Sequence of Fibonacci numbers:": gen_fibonacci,
"Sequence of factorial numbers:": gen_factorials}
for title, func in funcs.items():
x = list(islice(func(), 1000))
y = boustrophedon(x)
print(title)
print(y[:15])
print(f"1000th element: {compressed(y[-1])}\n")

Output:
One followed by an infinite series of zeros:
[1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981]
1000th element: 61065678604283283233...63588348134248415232 (2369 digits)

Infinite sequence of ones:
[1, 2, 4, 9, 24, 77, 294, 1309, 6664, 38177, 243034, 1701909, 13001604, 107601977, 959021574]
1000th element: 29375506567920455903...86575529609495110509 (2370 digits)

Alternating 1, -1, 1, -1:
[1, 0, 0, 1, 0, 5, 10, 61, 280, 1665, 10470, 73621, 561660, 4650425, 41441530]
1000th element: 12694307397830194676...15354198638855512941 (2369 digits)

Sequence of prime numbers:
[2, 5, 13, 35, 103, 345, 1325, 5911, 30067, 172237, 1096319, 7677155, 58648421, 485377457, 4326008691]
1000th element: 13250869953362054385...82450325540640498987 (2371 digits)

Sequence of Fibonacci numbers:
[1, 2, 5, 14, 42, 144, 563, 2526, 12877, 73778, 469616, 3288428, 25121097, 207902202, 1852961189]
1000th element: 56757474139659741321...66135597559209657242 (2370 digits)

Sequence of factorial numbers:
[1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547]
1000th element: 13714256926920345740...19230014799151339821 (2566 digits)


## 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), 'Fibonaccis 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) Fibonaccis 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) ## Sidef func boustrophedon_transform(seq) { func T(k,n) is cached { return seq[k] if (n == 0) T(k, n-1) + T(k-1, k-n) } var bt = seq.range.map {|n| T(n,n) } T.uncache return bt } const N = 100 # n terms [ '1 followed by 0\'s A000111', Math.seq(1,{0}), 'All-1\'s A000667', Math.seq({1}), '(-1)^n A062162', Math.seq({|_,k| (-1)**(k+1) }), 'Primes A000747', Math.seq(2,{ .tail.next_prime }), 'Fibbonaccis A000744', Math.seq(1,1,{ .last(2).sum }), 'Factorials A230960', Math.seq(1,{|a,k| a.last * (k-1) }), ].each_slice(2, {|name, seq| var bt = boustrophedon_transform(seq.first(N)) say "\n#{name}:\n#{bt.first(15).join(' ')}" var v = bt[N-1] say ("#{N}th term: ", Str(v).first(20), '..', Str(v).last(20), " (%s digits)" % v.len) })  Output: 1 followed by 0's A000111: 1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981 100th term: 45608516616801111821..68991870306963423232 (137 digits) All-1's A000667: 1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574 100th term: 21939873756450413339..30507739683220525509 (138 digits) (-1)^n A062162: 1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530 100th term: 94810791122872999361..65519440121851711941 (136 digits) Primes A000747: 2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691 100th term: 98967625721691921699..78027927576425134967 (138 digits) Fibbonaccis A000744: 1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189 100th term: 42390820205259437020..42168748587048986542 (138 digits) Factorials A230960: 1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547 100th term: 31807659526053444023..65546706672657314921 (157 digits)  ## Wren Library: Wren-math ### Basic import "./math" for Int var boustrophedon = Fn.new { |a| var k = a.count var cache = List.filled(k, null) for (i in 0...k) cache[i] = List.filled(k, 0) var b = List.filled(k, 0) b[0] = a[0] var T T = Fn.new { |k, n| if (n == 0) return a[k] if (cache[k][n] > 0) return cache[k][n] return cache[k][n] = T.call(k, n-1) + T.call(k-1, k-n) } for (n in 1...k) b[n] = T.call(n, n) return b } System.print("1 followed by 0's:") var a = [1] + ([0] * 14) System.print(boustrophedon.call(a)) System.print("\nAll 1's:") a = [1] * 15 System.print(boustrophedon.call(a)) System.print("\nAlternating 1, -1") a = [1, -1] * 7 + [1] System.print(boustrophedon.call(a)) System.print("\nPrimes:") a = Int.primeSieve(200)[0..14] System.print(boustrophedon.call(a)) System.print("\nFibonacci numbers:") a[0] = 1 // start from fib(1) a[1] = 1 for (i in 2..14) a[i] = a[i-1] + a[i-2] System.print(boustrophedon.call(a)) System.print("\nFactorials:") a[0] = 1 for (i in 1..14) a[i] = a[i-1] * i System.print(boustrophedon.call(a))  Output: 1 followed by 0's: [1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981] All 1's: [1, 2, 4, 9, 24, 77, 294, 1309, 6664, 38177, 243034, 1701909, 13001604, 107601977, 959021574] Alternating 1, -1 [1, 0, 0, 1, 0, 5, 10, 61, 280, 1665, 10470, 73621, 561660, 4650425, 41441530] Primes: [2, 5, 13, 35, 103, 345, 1325, 5911, 30067, 172237, 1096319, 7677155, 58648421, 485377457, 4326008691] Fibonacci numbers: [1, 2, 5, 14, 42, 144, 563, 2526, 12877, 73778, 469616, 3288428, 25121097, 207902202, 1852961189] Factorials: [1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547]  ### Stretch Library: Wren-big Library: Wren-fmt import "./math" for Int import "./big" for BigInt import "./fmt" for Fmt var boustrophedon1000 = Fn.new { |a| var k = a.count var cache = List.filled(k, null) for (i in 0...k) { cache[i] = List.filled(k, null) for (j in 0...k) cache[i][j] = BigInt.zero } var T T = Fn.new { |k, n| if (n == 0) return a[k] if (cache[k][n] > BigInt.zero) return cache[k][n] return cache[k][n] = T.call(k, n-1) + T.call(k-1, k-n) } return T.call(999, 999) } System.print("1 followed by 0's:") var a = ([1] + [0] * 999).map { |i| BigInt.new(i) }.toList var bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nAll 1's:") a = ([1] * 1000).map { |i| BigInt.new(i) }.toList bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nAlternating 1, -1") a = ([1, -1] * 500).map { |i| BigInt.new(i) }.toList bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nPrimes:") a = Int.primeSieve(8000)[0..999].map { |i| BigInt.new(i) }.toList bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nFibonacci numbers:") a[0] = BigInt.one // start from fib(1) a[1] = BigInt.one for (i in 2..999) a[i] = a[i-1] + a[i-2] bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a ($d digits)", bs, bs.count) System.print("\nFactorials:") a[0] = BigInt.one for (i in 1..999) a[i] = a[i-1] * i bs = boustrophedon1000.call(a).toString Fmt.print("1000th term:$20a (\$d digits)", bs, bs.count)

Output:
1 followed by 0's:
1000th term: 61065678604283283233...63588348134248415232 (2369 digits)

All 1's:
1000th term: 29375506567920455903...86575529609495110509 (2370 digits)

Alternating 1, -1
1000th term: 12694307397830194676...15354198638855512941 (2369 digits)

Primes:
1000th term: 13250869953362054385...82450325540640498987 (2371 digits)

Fibonacci numbers:
1000th term: 56757474139659741321...66135597559209657242 (2370 digits)

Factorials:
1000th term: 13714256926920345740...19230014799151339821 (2566 digits)