A jovial old grandpa mathematician straight out of central casting often appearing in Numberphile videos, Neil Sloane is behind the Online Encyclopedia of Integer Sequences, a wonderful tool for combinatorial explorations. This lab has you implement two methods to generate elements of two interesting integer sequences whose chaotic behaviour emerges from iteration of a deceptively simple rule. Both sequences are Yilled in ascending order in a greedy fashion, so that each element is always the smallest number that avoids creating a con/lict with the previously generated elements in the sequence. (Also, before you start: remySigrist requires bitwise arithmetic.)

Note that being deYined by mathematicians, these sequences start from the position one instead of the position zero, unlike how sequences work for us budding computer scientists who have to actually get our hands dirty and therefore prefer zero-based indexing. When asked to produce the Yirst n elements of the sequence, these methods should create an array with n + 1 elements. The zeroth element that we don't really care about is set to zero, after which the actual fun begins.

public static int[] forestFire(int n)

Explained in the YouTube video "Amazing Graphs II", the Yirst two elements are both equal to one. Then, each element a[i] is the smallest positive integer for which no positive integer offset j creates an arithmetic progression of three equally spaced elements backwards in the sequence from the position i. More formally, the difference a[i]-a[i-j] may never equal the difference a[i-j]-a[i-2*j], even if your worst enemy got to pick the position i and the offset j.

public static int[] remySigrist(int n)

As explained in the YouTube video "Amazing Graphs III", this sequence devised by Rmy Sigrist assigns to every positive integer a natural number, called the "colour" of that number. After the Yirst colour assignment a[1]=0, each following a[i] thereafter is the smallest natural number c for which the binary representation of any earlier position j that has already been assigned the colour c has any bits turned on common with the binary representation of the position i. This can be checked quickly with the expression i&j == 0, where & is the bitwise and operator of Java.

This problem can be solved with two nested for-loops. The outer loop iterates through the positions of a. The inner loop counts upwards through the colours until it Yinds one that does not create a conYlict. However, you should not be a "Shlemiel" who uses a third level inner loop to determine whether the current colour candidate c creates a conYlict. Instead, you should trade space for time with a second integer array taken whose each element taken[c] gathers all the bits that are on in any previous position that was assigned the colour c. Then, whenever you to assign a[i]=c, update this lookup table with the assignment taken[c] |= i, where | is the bitwise or operator of Java, and |= is its assignment shorthand analogous to += and other such more familiar forms.

TEST CODE:

import org.junit.Test; import java.util.zip.CRC32; import static org.junit.Assert.assertArrayEquals; import static org.junit.Assert.assertEquals; public class P2J12Test { private static final int[] FOREST_FIRE_EXPECTED = { 0, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10, 12, 10, 11, 14, 20, 13 }; private static final int[] REMY_SIGRIST_EXPECTED = { 0, 0, 0, 1, 0, 2, 3, 4, 0, 3, 2, 5, 1, 6, 7, 8, 0, 7, 6, 9, 5, 10, 11, 12, 4, 13, 14, 15, 16, 17, 18, 19, 0, 11, 10, 16, 9, 14, 13, 20, 12, 21, 22, 23, 24, 25, 26, 27, 1, 28, 29 }; private static final int ROUNDS = 10000; @Test public void testForestFire() { int[] actual = P2J12.forestFire(FOREST_FIRE_EXPECTED.length - 1); assertArrayEquals(FOREST_FIRE_EXPECTED, actual); CRC32 check = new CRC32(); actual = P2J12.forestFire(ROUNDS); for(int e: actual) { check.update(e); } assertEquals(3940994222L, check.getValue()); } @Test public void testRemySigrist() { int[] actual = P2J12.remySigrist(REMY_SIGRIST_EXPECTED.length - 1); assertArrayEquals(REMY_SIGRIST_EXPECTED, actual); CRC32 check = new CRC32(); actual = P2J12.remySigrist(ROUNDS); for(int e: actual) { check.update(e); } assertEquals(186819056L, check.getValue()); } }