Boustrophedon transform: Difference between revisions
New post.
Thundergnat (talk | contribs) m (Remove draft tag. Draft for over a year, multiple implementations, little controversy) |
(New post.) |
||
Line 154:
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|Julia}}==
| |||