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?

  • $\begingroup$ if I understand correctly (not clear): take $x=17$. then $n=\big \lfloor \frac {17}{\log_3(2)}\big \rfloor=26$, no? But $3^{17}-2^{26}=62031299 = 11\times 23\times 245183$ is not a prime. $\endgroup$ – lulu Sep 30 '19 at 13:29
  • 1
    $\begingroup$ $x=16$ does not work either. What is the context for this problem? It seems to yield primes sometimes...not often. Is there any reason to consider this form? $\endgroup$ – lulu Sep 30 '19 at 13:52
  • 1
    $\begingroup$ Yes, $16$ does work. My error. Usually, with expressions like this, either there is some simple congruence between the values (not the case here) or there is an algebraic factorization (not the case here) or there's no way to attack the problem. My guess is that this is the case here. $\endgroup$ – lulu Sep 30 '19 at 13:59
  • 2
    $\begingroup$ There is likely no maximum. Compare this to Mersenne primes. $\endgroup$ – Daniel Mathias Sep 30 '19 at 15:05
  • 1
    $\begingroup$ next $x=2236,x=5089,x=7938,x=14387$ and $x=21594$ (all probable primes). $\endgroup$ – pietfermat Oct 1 '19 at 8:52

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!)

  • $\begingroup$ you mean $\lfloor\log_2(3)\cdot x\rfloor$? $\endgroup$ – Collag3n Oct 1 '19 at 18:54
  • $\begingroup$ @Collag3n Yes, thanks. $\endgroup$ – Milo Brandt Oct 1 '19 at 19:05
  • $\begingroup$ @MiloBrandt Thanks for explaining it properly !! But I will still keep the question open for some time for discussion before accepting your answer. $\endgroup$ – The Demonix _ Hermit Oct 2 '19 at 5:40


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


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.

  • $\begingroup$ Thanks for the explanation part ! $\endgroup$ – The Demonix _ Hermit Oct 5 '19 at 10:23
  • $\begingroup$ You are welcome. $\endgroup$ – sirous Oct 5 '19 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.