What is the least odd prime giving a prime remainder when divided by $3$? It is $5$. What is the least odd prime giving prime remainders for both $3$ and $5$? It is $17$. For division by $3,5,7$ it is also $17$. For division by $3,5,7,11$ it is $47$. The sequence is $$5,17,17,47,863,887,887,887,887,887...$$ Note that $887$ leaves prime remainder under division by all the primes from $3$ to $31$ (but not $37$).

If the sequence is continued, will any other prime occur five (or more) times in a row?

  • $\begingroup$ It sounds really unlikely, Leaving prime remainder gets harder and harder, So the probability that the very first number that yields prime remainder mod p1,p2\dots pn also leaves prime remainder mod p_(n+1) seems slim. $\endgroup$ – Jorge Fernández-Hidalgo Jul 26 '16 at 19:54
  • $\begingroup$ Interesting setup, not one that I'd ever thought of. It would improve the problem statement to highlight the actual question (1). Your point (2) is not really a question to be answered, at least not here. If there was a topic that motivated this Question, it would be interesting to learn about how this problem arose. $\endgroup$ – hardmath Jul 26 '16 at 20:03
  • $\begingroup$ You need to be more precise about the definition of your sequence: the least prime giving a prime remainder when divided by 3 (or 5 or 7 or 11 or ...) is 2; no prime leaves an odd remainder when divided by 2. I think the sequence you are interested in may be the sequence of odd primes that leave a prime remainder when divided by any smaller odd prime. But then it should include 3. $\endgroup$ – Rob Arthan Jul 26 '16 at 20:12
  • $\begingroup$ The remainder can be ANY prime. Look at 47 to get 47mod3=2, 47mid5=2, 47mod7=5 and 47mod11=3. If you looked at the second mention of 17, you'd see that a prime remainder means ANY prime remainder. It is NOT the remainder that is specified, but the least prime such that all its divisors 3,5,7...give ANY prime remainder. Just try 863 when divided by 3,5,7,11,13 and you'll see a variety of remainders. Now, I do agree that extending this is a challenge. If no one is up to it, that's not surprising. $\endgroup$ – J. M. Bergot Jul 26 '16 at 20:17
  • $\begingroup$ @RobArthan, I think it would suffice for the OP to ask for the least odd prime giving a prime remainder when divided by each of the first $n$ odd primes. $\endgroup$ – Barry Cipra Jul 26 '16 at 20:17

Here's a very rough heuristic argument that you can expect repeats of length $5$ (or more) to occur infinitely often.

If $P_n$ is the least (odd) prime that gives a prime remainder when divided by each of the primes $3,5,7,\ldots,p_n$, the probability that its remainders under division by the next $4$ primes are also prime is approximately

$$\left(n\over p_n\right)^4$$

(A more "precise" approximation would be ${n\over p_{n+1}}\cdot{n+1\over p_{n+2}}\cdot{n+2\over p_{n+3}}\cdot{n+3\over p_{n+4}}$, but for large $n$, the displayed expression is good enough. The basic heuristic premise is that when you divide a "random" number by $q$, the remainder is equally likely to be any number smaller than $q$.) So the probability that the next $4$ remainders are not all prime is approximately

$$1-\left(n\over p_n\right)^4$$

and so the probability that a repeat of length $5$ never happens again past some point $N$ is approximately

$$\prod_{n\gt N}\left(1-\left(n\over p_n\right)^4\right)$$

Now the prime number theorem implies $p_n\approx n\ln n$, so the approximated probability becomes

$$\prod_{n\gt N}\left(1-\left(1\over\ln n\right)^4\right)$$

But that infinite product "condiverges" to $0$ (i.e., its logarithm is the divergent series $\sum\ln(1-({1\over\ln n})^4)\approx-\sum({1\over\ln n})^4=-\infty)$, which we can interpret, heustically, as saying there is no chance that a repeat of length $5$ won't happens again. Note, there is nothing special about the number $5$; the argument works the same for any fixed repeat length.

| cite | improve this answer | |

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.