Smallest prime

Number Theory Level 4

$\large q = 2^{ \pi (p) } - p$

In the above equation, $p$ and $q$ are prime numbers where $q>3$ and $\pi (p)$ is the number of primes that are less than or equal to $p$ .

Find the smallest value of $q$ satisfying the above conditions.

The answer is 2017.

1 solution

Maria Kozlowska
Jan 6, 2017

$2^{11}-31=2017$ .

$\pi(31)=11$ .

This question was taken from here

Is there a way to solve this problem without trial and error? (I did brute force to get the answer)

Pi Han Goh - 4 years, 5 months ago

I do not know that. I just found out that it is also called a Solinas prime .

Maria Kozlowska - 4 years, 5 months ago

The next smallest value is $2^{19} - 67 = 524221$ .

I guess the natural follow-up question would be whether the number of such pairs $(p,q)$ is finite or infinite. This is likely an open question, but it's still interesting to think about.

Brian Charlesworth - 4 years, 5 months ago

@Brian Charlesworth – I wonder if it works only for prime values of $\pi(p)$ .

Maria Kozlowska - 4 years, 5 months ago

@Maria Kozlowska – It doesn't look like it. The next two cases are $\pi(89) = 24$ and $\pi(101) = 26$ before getting to another prime with $\pi(283) = 61$ . This list ramps up quite quickly, with the 23rd entry being in excess of $50000$ , but if I had to guess I would say that the list in infinite.

Brian Charlesworth - 4 years, 5 months ago

Smallest prime

The answer is 2017.

1 solution

0 pending reports