Boustrophedon transform: Difference between revisions
Created Nim solution.
(Added Algol 68) |
(Created Nim solution.) |
||
Line 155:
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.
<syntaxhighlight lang="julia">using Primes
function bous!(triangle, k, n, seq)
n == 1 &&
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))
Line 210:
[1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547]
13714256926920345740 ... 19230014799151339821 (2566 digits)
</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>
| |||