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: , the boustrophedon transform yields another sequence: , where is likely defined equivalent to .
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:
- .
The transformed sequence is defined by (for 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:
- ( one followed by an infinite series of zeros )
- ( an infinite series of ones )
- ( (-1)^n: alternating 1, -1, 1, -1 )
- ( sequence of prime numbers )
- ( sequence of Fibonacci numbers )
- ( 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
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
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
let Boustrophedon n=Seq.scan(fun n g->fG n g)[Seq.head n] (Seq.tail n)|>Seq.map(List.head)
The Task
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
}}
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
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.
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
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)
Wren
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
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)