Maximum value of $x$ such that $3^x-2^n$ is a prime.

What is the maximum possible value of $x$ such that expression $3^x - 2^n $ results in a prime, where $n$ is the maximum value such that $2^n<3^x$ and $2^{n+1} > 3^x$?

Using some brute force, till now I have found that $x = 33077 $ to be the maximum value for which the difference is a prime number. But is this the maximum value?

Can anyone please explain, for what values would we get a prime number.

Also, Would changing any of the constants from 2 and 3 to other values , give much more interesting results ? Would it be even solvable?

Solution 1:

I can't prove anything, but I will suggest that there are probably infinitely many $x$ for which this value is prime by the standard heuristics that one might use for these problems and also that this problem is very similar to long-standing open questions, so probably not easily answered.

For the first part, the prime number theorem is often interpreted as saying:

If we choose a natural number $n$ at random, the probability that it is prime is roughly $1/\log(n)$.

This is not a formal statement - not least because "random" and "probability" are involved with "natural number" but without any further specification - but it is commonly used and is close enough to statements that really do follow from the prime number theorem.

Using this alone, we can note that $3^x-2^n$ is definitely no bigger than $3^x$, so has about a $\frac{1}{\log(3)x}$ chance of being prime. The expected number of primes would then be the sum of this over all integer $x$, which is the harmonic series and is infinite - suggesting infinitely many primes.

If we're being a bit more careful, we might look at each $p$: the sequence $3^x-2^n$ will take on every value that can possibly be represented as a difference of a power of $3$ with a power of $2$ mod $p$ since $n=\lfloor\log_2(3)\cdot x\rfloor$ and $\log_2(3)$ is irrational, meaning that mod $p-1$, the pair $(x,n)$ could obtain any possible two values due to the equidistribution theorem and actually obtains every possible pair equally often - so the proportion of values of $3^x-2^n$ that a given $p$ divides is precisely equal to the probability that, if we choose a random power of $3$ and a random power of $2$ mod $p$ that they are equal - which, doesn't create any clear conspiracies that would contradict our heuristic, although this probability is greater than $1/p$, which is sort of what the heuristic would have suggested - how much greater, I don't know. (But also, the fact that it is greater than $1/p$ is somewhat counteracted by the lack of independence between this condition holding for various primes simultaneously)

However, this brings us to the second part: it is not known whether there are infinitely Mersenne primes - that is, primes of the form $2^n-1$. This has been a prominent open question for a while, and it touches on a lot of the same issues that arise in yours - which suggests that this is a question that is beyond the current reach of mathematics. (But maybe that will change someday!)

Solution 2:

COMMENT

Some of these type of primes may have a relation with Merssene and Fermat numbers:

$$N=3^x-2^n=3^x-2-2^n+2=3^x-2-2(2^n-1)$$

Where $M=2^n-1$ is Merssene Number. Also:

$$N=3^x-2^n=3^x+2-2^n -2=3^x+2 -2(2^n +1)$$

If $n=2^m$ then $F=2^n+1$ is a Fermat number.The equal linear form of N is:

$$N=3^x-2^n=3^x-(3-1)^n=3q ±1$$

depending on n (even or odd).$S=3q ±1$ can generate of a set of infinitely many primes, therefore set of primes like N is the subset of S.It is not known such primes has a limit.