Binary Primes

Computer Science Level 4

Let $f$ be a function in the natural numbers, such that $f(n)$ gives the binary representation of $n$ in base 10. For example, $f(5) = 101$ , because 5 is represented as 101 in binary.

A number $n$ is called good if $n$ and $f(n)$ are both prime numbers. For example, 5 is good, because 5 and 101 are prime numbers. 7 is not good, since $f(7) = 111 = 3 \times 37$ is not prime.

The smallest good number is 3. The second smallest good number is 5. Find the $19^\text{th}$ smallest good number.

The answer is 443.

1 solution

João Arruda
Mar 4, 2016

In JavaScript:

function convertBinary(number){
    if(number == 0) return 0;
    var pos = 0;
    while(number >= Math.pow(2,pos)){
        pos++;
    }
    pos = pos - 1;
    var result = "1";
    while(result.length < pos + 1){
        result += "0";
    }
    return parseInt(result) + convertBinary(number - Math.pow(2,pos));
}

function isPrime(number){
    if(number == 2) return true;
    var divisor = number - 1;
    while(divisor >= 2){
        if(number % divisor == 0) return false;
        divisor--;
    }
    return true;
}

function nthGoodNumber(n){
    var i = 3;
    while(n > 0){
        if(isPrime(i) && isPrime(convertBinary(i))) n--;
        i++;
    }
    return i-1;
}

typing nthGoodNumber(19) on the Browser's Console gives the answer $\boxed{443}$

Binary Primes

The answer is 443.

1 solution

0 pending reports