Problem looping through a 4D array

Processing Coding Questions
18

@RichardDL – nice recursive solution.

The “three bits” (or sum of three powers of two) integer sequence is here:

A014311 : Numbers with exactly 3 ones in binary expansion.
https://oeis.org/A014311

I looked it up by entering the first ten results separated by commas. The sequence page for A014311 includes a nice little (cryptic) C solution (which I translated into Processing-Java, below). Rather than looping over the search space (4096) and checking each one with is3bits, you can just input the nth number and get it directly.

void setup() {
  // loop
  for (int i=1; i<=10; i++) {
    int num = A014311(i);
    println(String.format("%4d %s %4d", num, binary(num, 12), i));
  }
  // direct
  int i = 220;
  int num = A014311(i);
  println(String.format("%4d %s %4d", num, binary(num, 12), 220));
}

int A014311(int n) {
  if (n == 1) return 7;
  return hakmem175(A014311(n - 1));
}
int hakmem175(int x) {
  int s, o, r;
  s = x & -x;
  r = x + s;
  o = r ^ x;
  o = Integer.divideUnsigned(o >>> 2, s);
  return r | o;
}

   7 000000000111    1
  11 000000001011    2
  13 000000001101    3
  14 000000001110    4
  19 000000010011    5
  21 000000010101    6
  22 000000010110    7
  25 000000011001    8
  26 000000011010    9
  28 000000011100   10
3584 111000000000  220

That said, the C-to-Java is almost inscrutable.
To understand the “same bit count, but bigger value” HAKMEM 175 algorithm that it is built on, see: http://code.iamkate.com/articles/hakmem-item-175/

Or just use it and enjoy.

4 Likes