Boustrophedon transform: Difference between revisions

Content added Content deleted

Inline

Revision as of 23:23, 18 September 2022

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

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(arr[1:15])
    s = string(arr[1000])
    println(s[1:20], " ... ", s[991:1000], " ($(length(s)) digits)\n")
end

Output:

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

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

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

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

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

Sequence of factorial numbers -> A230960
BigInt[1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547]
13714256926920345740 ... 6070236763 (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),
    'Fibbonaccis        A000744', (1,1,*+*…*),
    'Factorials         A230960', (1,|[\×] 1..∞)
  -> $name, $seq
{ say "\n$name:\n" ~ (my $b-seq = boustrophedon-transform $seq)[^15] ~ "\n1000th term: " ~ abbr $b-seq[999] }

Output:

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

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

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

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

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

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

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)