Codesignal Solution: onesPosition

Original Problem

Little Sander found a lot of numbers lying around, so he decided to have some fun with them. Since he's a #1 fan of prime numbers, he decided to associate each number he found with a prime number. He's also extremely proficient in the binary numeral system, so it's no wonder his association technique has something to do with it.

For each number num Sander found, he calculates the number of '1's in its binary representation. Let this number be o . The prime number associated with num is thus the o^th prime number (0-based).

Given num, your task is to find the prime number associated with it. You should probably keep in mind that Sander believes that 0 and 1 are also prime numbers, and we're not going to argue with him right now.

Example

For num = 15, the output should be
onesPosition(num) = 5.

15₁₀ = 1111₂, so the answer is the fourth 0-based prime number (as Sanders sees them). Here are the first five Sanders-prime numbers: 0, 1, 2, 3, 5. Thus, the output should be 5.

Input/Output

• [time limit] 4000ms (py)

• [input] integer num

  Guaranteed constraints:
  0 ≤ k < 2³¹.

• [output] integer

  The prime number that Sander associates with num.

Solution

An algorithm that counts the number of bits set can be stated quite easily:

function countBit(x) {
	var c = 0;
	while (x > 0) {
		c++;
		x >>>= 1;
	}
	return c;
}

My first idea was to implement this algorithm recursively and look up the appropriate prime from a table. Since we can have at most 32 bit set, this table isn't too large. But it costs too much bytes to have a short solution. The same counting mechanism, which does not have a runtime of \(\log(n)\) but \(\#(n)\), where \(\#\) denotes the number of set bits is given by:

function countBit(x) {

	var c = 0;
	while (x > 0) {
		c++;
		x&= x - 1;
	}
	return c;
}

What we need is a way to check if the number of set bits is prime. We could implement a classical prime check loop for this. But this wastes way too much CPU cycles and bytes to win the contest. Remembering Fermat's little theorem, which states that

\[a^p\equiv a \pmod{p}\]

might help. It doesn't mean that other numbers couldn't fall into the same modular class, but checking for the first 32 numbers reveals that this is an appropriate prime check, using \(a:= 2\), (3 for example has too many false positives):

function onesPosition(n) {
	var p = 0
	while (n > 0) {
		p++
		if (p < 3 || Math.pow(2, p) % p == 2) 
			n&= n-1; 
	}
	return p 
}

Now it comes to minification of the function:

onesPosition = n => eval(`
	for (p = 0; n > 0; )
		n&= n - (++p < 3 || (1 << p) % p == 2)
	p
`)