Boustrophedon transform

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

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

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 g with h::[]->yield n+h |h::t->yield n+h; yield! fG (n+h) t] in [yield n; yield! fG n g]|>List.rev
let rec Boustrophedon n g=seq{yield List.head g; yield! Boustrophedon n (fG (n()) g)}

The Task

printfn "zeroes"; Boustrophedon (fun()->0I) [1I]|>Seq.take 15|>Seq.iter(printf "%A "); printfn ""
let n=sprintf $"%A{Boustrophedon (fun()->0I) [1I]|>Seq.item 999}" in printfn "%s ... %s  (%d digits)" n[0..19] n[n.Length-20..n.Length] (n.Length)
printfn "ones"; Boustrophedon (fun()->1I) [1I]|>Seq.take 15|>Seq.iter(printf "%A "); printfn ""
let n=sprintf $"%A{Boustrophedon (fun()->1I) [1I]|>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....."; Boustrophedon (let mutable n=1I in (fun()->n<- -n; n)) [1I]|>Seq.take 15|>Seq.iter(printf "%A "); printfn ""
let n=sprintf $"%A{Boustrophedon (let mutable n=1I in (fun()->n<- -n; n)) [1I]|>Seq.item 999}" in printfn "%s ... %s  (%d digits)" n[0..19] n[n.Length-20..n.Length] (n.Length)
printfn "factorials"; Boustrophedon (let mutable n,g=1I,2I in (fun()->let r=n in n<-n*g; g<-g+1I; r)) [1I]|>Seq.take 15|>Seq.iter(printf "%A "); printfn ""
let n=sprintf $"%A{Boustrophedon (let mutable n,g=1I,2I in (fun()->let r=n in n<-n*g; g<-g+1I; r)) [1I]|>Seq.item 999}" in printfn "%s ... %s  (%d digits)" n[0..19] n[n.Length-20..n.Length] (n.Length)
printfn "primes"; let p=primesI() in Boustrophedon (fun()->Seq.head p) [Seq.head p]|>Seq.take 15|>Seq.iter(printf "%A "); printfn ""
let p=primesI() in let n=sprintf $"%A{Boustrophedon (fun()->Seq.head p) [Seq.head p]|>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
}}

Task examples:

   =&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) {
		listPrimeNumbersUpTo(8_000);		
		
		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>();
		primes.add(BigInteger.TWO);
		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] ) {
				primes.add(BigInteger.valueOf(p));
				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)

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>;
use List::Util 'head';
use bigint;

sub abbr ($d) { my $l = length $d; $l < 41 ? $d : substr($d,0,20) . '..' . substr($d,-20) . " ($l digits)" }
sub sum  (@a) { my $sum = Math::BigInt->bzero(); $sum += $_ for @a; $sum }

sub boustrophedon_transform (@seq) {
    my @bt;
    my @bx = $seq[0];
    for (my $c = 0; $c < @seq; $c++) {
        @bx = reverse map { sum 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()
            mpz_add(tk,t[i,j-step],t[i-1,j-even(k)])
            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()
                mpz_add(tk,t[i,j+1],t[i-1,j])
                t[i][j] = tk
            end for
        else
            for j=2 to i do
                mpz tk = mpz_init()
                mpz_add(tk,t[i,j-1],t[i-1,j-1])
                t[i][j] = tk
            end for
        end if

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)

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)