6

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?

Barry Cipra
  • 79,832
J. M. Bergot
  • 912
  • 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. – Asinomás Jul 26 '16 at 19:54
  • 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. – hardmath Jul 26 '16 at 20:03
  • 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. – Rob Arthan Jul 26 '16 at 20:12
  • 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. – J. M. Bergot Jul 26 '16 at 20:17
  • @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. – Barry Cipra Jul 26 '16 at 20:17
  • A slight extension: 5 17 17 47 863 863 887 887 887 887 133877 858707 886013 11891003 11891003 – Asinomás Jul 26 '16 at 20:27
  • @J.M. Bergot: As you haven't expressed your definition clearly, it is unsurprising that you have not received any useful answers. Typing "ANY" and "NOT" in upper case does nothing to clarify your vague definition. To help focus your mind on logical precision, perhaps you could explain why 2, 3 and 11 don't belong in your sequence. – Rob Arthan Jul 26 '16 at 20:33
  • @BarryCipra: I think your guess at what the OP meant is probably better than mine, but who are we to say? – Rob Arthan Jul 26 '16 at 20:53
  • To the OP: I've edited the question to clear up the things you mentioned in your "I erred" and "OOOPPPPS" comments, as well as incorporate the clarification that Rob Arthan and I discussed earlier and the suggestions hardmath made. (If you delete your two comments, I'll delete this one, to remove clutter that future readers can do without.) – Barry Cipra Jul 28 '16 at 00:23
  • I trust I did what you requested. You work where it is quiet and I work were it is usually noisy as hell=public library computer. – J. M. Bergot Jul 28 '16 at 17:39

1 Answers1

3

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.

Barry Cipra
  • 79,832