Boustrophedon transform: Difference between revisions
(→{{header|Wren}}: Added stretch goal.) |
(→Stretch: Simplified.) |
||
Line 159: | Line 159: | ||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
var |
var boustrophedon1000 = Fn.new { |a| |
||
var k = a.count |
var k = a.count |
||
var cache = List.filled(k, null) |
var cache = List.filled(k, null) |
||
Line 166: | Line 166: | ||
for (j in 0...k) cache[i][j] = BigInt.zero |
for (j in 0...k) cache[i][j] = BigInt.zero |
||
} |
} |
||
var b = List.filled(k, null) |
|||
for (i in 0...k) b[i] = BigInt.zero |
|||
b[0] = a[0] |
|||
var T |
var T |
||
T = Fn.new { |k, n| |
T = Fn.new { |k, n| |
||
Line 175: | Line 172: | ||
return cache[k][n] = T.call(k, n-1) + T.call(k-1, k-n) |
return cache[k][n] = T.call(k, n-1) + T.call(k-1, k-n) |
||
} |
} |
||
return T.call(999, 999) |
|||
return b |
|||
} |
} |
||
System.print("1 followed by 0's:") |
System.print("1 followed by 0's:") |
||
var a = ([1] + [0] * 999).map { |i| BigInt.new(i) }.toList |
var a = ([1] + [0] * 999).map { |i| BigInt.new(i) }.toList |
||
var bs = |
var bs = boustrophedon1000.call(a).toString |
||
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
||
System.print("\nAll 1's:") |
System.print("\nAll 1's:") |
||
a = ([1] * 1000).map { |i| BigInt.new(i) }.toList |
a = ([1] * 1000).map { |i| BigInt.new(i) }.toList |
||
bs = |
bs = boustrophedon1000.call(a).toString |
||
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
||
System.print("\nAlternating 1, -1") |
System.print("\nAlternating 1, -1") |
||
a = ([1, -1] * 500).map { |i| BigInt.new(i) }.toList |
a = ([1, -1] * 500).map { |i| BigInt.new(i) }.toList |
||
bs = |
bs = boustrophedon1000.call(a).toString |
||
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
||
System.print("\nPrimes:") |
System.print("\nPrimes:") |
||
a = Int.primeSieve(8000)[0..999].map { |i| BigInt.new(i) }.toList |
a = Int.primeSieve(8000)[0..999].map { |i| BigInt.new(i) }.toList |
||
bs = |
bs = boustrophedon1000.call(a).toString |
||
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
||
Line 203: | Line 199: | ||
a[1] = BigInt.one |
a[1] = BigInt.one |
||
for (i in 2..999) a[i] = a[i-1] + a[i-2] |
for (i in 2..999) a[i] = a[i-1] + a[i-2] |
||
bs = |
bs = boustrophedon1000.call(a).toString |
||
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count) |
||
Line 209: | Line 205: | ||
a[0] = BigInt.one |
a[0] = BigInt.one |
||
for (i in 1..999) a[i] = a[i-1] * i |
for (i in 1..999) a[i] = a[i-1] * i |
||
bs = |
bs = boustrophedon1000.call(a).toString |
||
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count)</syntaxhighlight> |
Fmt.print("1000th term: $20a ($d digits)", bs, bs.count)</syntaxhighlight> |
||
Revision as of 22:15, 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: , 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
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
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)