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