179
$\begingroup$

The numbers 14 and 21 are quite interesting.

The prime factorisation of 14 is $2\cdot 7$ and the prime factorisation of $14+1$ is $3\cdot 5$. Note that 3 is the prime after 2 and 5 is the prime before 7.

Similarly, the prime factorisation of 21 is $7\cdot 3$ and the prime factorisation of $21+1$ is $11\cdot 2$. Again, 11 is the prime after 7 and 2 is the prime before 3.

In other words, they both satisfy the following definition:

Definition: A positive integer $n$ is called interesting if it has a prime factorisation $n=pq$ with $p\ne q$ such that the prime factorisation of $n+1$ is $p'q'$ where $p'$ is the prime after $p$ and $q'$ the prime before $q$.

Are there other interesting numbers?

$\endgroup$
  • 8
    $\begingroup$ If $p_n$ denotes the $n$-th prime, then we search examples for $p_{n+1}p_{m-1}-p_np_m=1$. I have seen this before... but where? $\endgroup$ – Dietrich Burde Nov 2 '16 at 14:46
  • 24
    $\begingroup$ Since one of $n$ and $n+1$ is even, you either have $p=2$ and $p'=3$ or $q'=2$ and $q=3$, so that either $q={3q'-1\over2}$ (if $pp'=2\cdot3$) or $p'={3p+1\over2}$ (if $q'q=2\cdot3$). The Prime Number Theorem limits the number of possibilities, and it should be fairly easy to find the upper limit. In effect, you want to find when a "$3/2$" version of Bertrand's Postulate kicks in. $\endgroup$ – Barry Cipra Nov 2 '16 at 14:48
  • 6
    $\begingroup$ @BarryCipra If you see this wikipedia paragraph, they say that the $\frac65$ version of Bertrand's postulate kicks in at $25$. The $\frac32$ version can't kick in later, so there aren't a whole lot of primes that needs to be checked. $\endgroup$ – Arthur Nov 2 '16 at 14:57
  • 5
    $\begingroup$ Well, Parcly Taxel has relieved us both of the burden. $\endgroup$ – Barry Cipra Nov 2 '16 at 15:08
  • 8
    $\begingroup$ I think we should drop the requirement $p\ne q$ and accept $n=9$ as an interesting number as well. $\endgroup$ – Jeppe Stig Nielsen Nov 2 '16 at 23:30
260
$\begingroup$

Note that exactly one of $n$ and $n+1$ is even. It follows that for $n$ to be interesting, either $n=3p$ and $n+1=2N(p)$ or $n=2p$ and $n+1=3P(p)$, where $P(p)$ and $N(p)$ are the previous and next primes to $p$ respectively. Rearranging we get that $p$ must satisfy one of the following two equations: $$\frac{3p+1}2=N(p)\tag1$$ $$\frac{2p+1}3=P(p)\tag2$$ However, by a 1952 result of Jitsuro Nagura, for $p\ge25$ there is always a prime between $p$ and $\frac65p$. In particular, if $p\ge31$ is a prime: $$\frac56p<P(p)<p<N(p)<\frac65p$$ But when $p\ge31$ the following inequalities are also true: $$\frac{2p+1}3<\frac56p\qquad\frac65p<\frac{3p+1}2$$ Therefore, if $p$ is to satisfy $(1)$ or $(2)$ above, it must be less than 31. This leaves a handful of cases to check for $p$, and we find that the only interesting numbers are 14 and 21 as conjectured.


The Nagura paper is a reference in the Wikipedia article on Bertrand's postulate. While those in the comments had saw it, sketching out the approach I use here, I already knew what to do; I did not read those comments in detail until after posting my answer.

$\endgroup$
  • 10
    $\begingroup$ For the record, it is worth pointing out that this method was previously sketched in the comments to the question by Barry Cipra and Arthur, including a link to Wikipedia (which cites Nagura's paper). $\endgroup$ – Bill Dubuque Nov 2 '16 at 22:48
  • 2
    $\begingroup$ Even as a non-mathematician, that paper was great to read, interesting approach (though probably interesting mainly because I'm not well versed in the field). $\endgroup$ – Nit Nov 2 '16 at 23:54

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.