Skip to content

Instantly share code, notes, and snippets.

@joriki
Created August 1, 2012 09:34
Show Gist options
  • Save joriki/3225461 to your computer and use it in GitHub Desktop.
Save joriki/3225461 to your computer and use it in GitHub Desktop.
Search for common multiples of Voyager polynomials with few monomials: http://math.stackexchange.com/questions/177465
import java.util.BitSet;
public class Question177465 {
static BitSet [] bits = {new BitSet (),new BitSet ()};
static int [] polynomials = {Integer.parseInt ("1011011",2),Integer.parseInt ("1111001",2)};
public static void main (String [] args) {
bits [0] = new BitSet ();
bits [1] = new BitSet ();
recurse (true,0,0);
}
static void recurse (boolean set,int index,int count) {
if (set)
add (index);
for (int i = 0;i < 2;i++)
if (bits [i].get (index))
count++;
if (count < 10) {
recurse (true,index + 1,count);
recurse (false,index + 1,count);
}
if (set)
add (index);
}
static void add (int index) {
for (int i = 0;i < 2;i++)
for (int bit = 0,polynomial = polynomials [i];polynomial != 0;polynomial >>= 1,bit++)
if ((polynomial & 1) == 1)
bits [i].flip (index + bit);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment