Rosetta Code

Boustrophedon transform: Difference between revisions

Page Discussion

Boustrophedon transform (view source)

Revision as of 00:59, 20 April 2024

55,081 bytes added ,  1 month ago
Added FreeBASIC
(Added FreeBASIC)
 
(21 intermediate revisions by 13 users not shown)
Line 1:
{{draft task}}
{{wikipedia|Boustrophedon transform}}
<br>
Line 45:
 
 
 
=={{header|ALGOL 68}}==
Basic task - assumes LONG INT is large enough, e.g. 64 bits, 39 bits would do...
<syntaxhighlight lang="algol68">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="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);
}
</syntaxhighlight>
{{ out }}
<pre>
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
</pre>
 
=={{header|EasyLang}}==
<syntaxhighlight>
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
 
</syntaxhighlight>
{{out}}
<pre>
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 ]
</pre>
 
=={{header|FreeBASIC}}==
===Basic===
{{trans|Wren}}
<syntaxhighlight lang="vbnet">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</syntaxhighlight>
{{out}}
<pre>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 ]</pre>
 
=={{header|F_Sharp|F#}}==
===The function===
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<syntaxhighlight lang="fsharp">
// 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
let Boustrophedon n=Seq.scan(fun n g->fG n g)[Seq.head n] (Seq.tail n)|>Seq.map(List.head)
 
</syntaxhighlight>
 
===The Task===
<syntaxhighlight lang="fsharp">
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)
 
</syntaxhighlight>
{{out}}
<pre>
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)
</pre>
 
=={{header|J}}==
Line 87 ⟶ 561:
 
Here, we start with a square matrix with the <code>a</code> values in sequence in the first column (first line). Then we fill in the remaining needed <code>T</code> values in row major order (for loop). Finally, we extract the diagonal (last line). Usage and results are the same as before.
 
=={{header|Java}}==
<syntaxhighlight lang="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>();
}
</syntaxhighlight>
{{ out }}
<pre>
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)
</pre>
 
=={{header|jq}}==
'''Works with gojq, the Go implementation of jq'''
 
'''Works with jq, the C implementation of jq, within the limits of IEEE 764 arithmetic'''
 
'''Adapted from [[#Wren|Wren]]'''
 
The results for the "stretch" tasks are based on the use of gojq.
<syntaxhighlight lang="jq">
### 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)
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
 
=={{header|Julia}}==
Line 145 ⟶ 874:
</pre>
 
=={{header|Maxima}}==
<syntaxhighlight lang="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);
</syntaxhighlight>
{{out}}
<pre>
[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]
</pre>
 
=={{header|Nim}}==
{{libheader|Nim-Integers}}
<syntaxhighlight lang="Nim">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()
</syntaxhighlight>
 
<pre>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)
</pre>
 
=={{header|Perl}}==
Not really fulfilling the conditions of the stretch goal, but heading a little way down that path.
{{trans|Raku}}
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>use v5.36; use experimental <builtin for_list>;
use ntheory <factorial lucasu nth_prime vecsum>;
use List::Util 'head';
 
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];
}
</syntaxhighlight>
{{out}}
<pre>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)</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">without</span> <span style="color: #008080;">js</span> <span style="color: #000080;font-style:italic;">-- see below</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">stretchres</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">string</span> <span style="color: #000000;">desc</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ds</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)}),</span>
<span style="color: #000000;">r15</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"?"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">r1000</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"??"</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">lo</span><span style="color: #0000FF;">,</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">step</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)?{</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}:{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">step</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">lo</span> <span style="color: #008080;">to</span> <span style="color: #000000;">hi</span> <span style="color: #008080;">by</span> <span style="color: #000000;">step</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">tk</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">step</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)])</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tk</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">15</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">r15</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][-</span><span style="color: #000000;">step</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1000</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">r1000</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_short_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][-</span><span style="color: #000000;">step</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r15</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">stretchres</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%s[1000]:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r1000</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">f1000</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">"1{0}"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">999</span><span style="color: #0000FF;">))},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"{1}"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">))},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"+-1"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">flatten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">500</span><span style="color: #0000FF;">)))},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"pri"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">get_primes</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">))},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"fib"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1000</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_fib_ui</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">))},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"fac"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1000</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_fac_ui</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">tagstart</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">))}}</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">,</span><span style="color: #000000;">test</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n%s"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">stretchres</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
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)
</pre>
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:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
...
<span style="color: #008080;">if</span> <span style="color: #7060A8;">odd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">k</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">tk</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tk</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">i</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">tk</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tk</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</syntaxhighlight>-->
=={{header|Python}}==
<syntaxhighlight lang="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")
</syntaxhighlight>
{{out}}
<pre style="height:15em">
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)
</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>sub boustrophedon-transform (@seq) { map *.tail, ([@seq[0]], {[[\+] flat @seq[++$ ], .reverse]}…*) }
 
sub abbr ($_) { .chars < 41 ?? $_ !! .substr(0,20) ~ '…' ~ .substr(*-20) ~ " ({.chars} digits)" }
Line 182 ⟶ 1,314:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
1000th term: 13714256926920345740…19230014799151339821 (2566 digits)</pre>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">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)
})</syntaxhighlight>
{{out}}
<pre>
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)
</pre>
 
=={{header|Wren}}==
{{libheader|Wren-math}}
===Basic===
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
 
var boustrophedon = Fn.new { |a|
Line 254 ⟶ 1,439:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./big" for BigInt
import "./fmt" for Fmt
Jjuanhdez
2,123

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/330343...363810"