2
$\begingroup$

This is closely related to this question, in which I asked about pairing of numbers in the same problem, which I defined as follows:

Given a number $n$, the sequence of "prime-adjacent multiples" is defined as any multiple $k$ that is $\pm 1$ away from a prime number.

It essentially boils down to: How frequently do multiples of my number live next to a prime number?

This can be calculated by running an extremely simple python script (as follows, just if you wanted to try this yourself):

import sympy
import numpy as np

c = []
for i in range(1000):
    c.append(0)
    for j in range(5000):
        if sympy.isprime(i*j - 1) or sympy.isprime(i*j + 1):
            c[-1] += 1
ind = np.argmax(c)
print(ind, c[ind])

Which will calculate the number of times a multiple of a number $n$ is adjacent to a prime for each $n$ from 0 to 1000, for the first 5000 multiples.

Running this shows that 30 has the most "prime-adjacent multiples" for the first 5000 multiples. As there was a bit of preamble, I'll restate: I want to know why this is. Why are multiples of 30 adjacent to prime numbers more often than any other number?

Not entirely related:

This may beg the question of how do I know 30 has prime-adjacent multiples "more often than any other number"? It's mainly down to observation, by plotting the count of prime-adjacent multiples for all numbers between 0 and 20,000 (this time for the first 1000 multiples, to save on computation time) gives the following graph:

enter image description here

Where the initial peak at the start is 30 (closely followed by 6). The graph would indicate that no number would ever be able to reach a peak similar in size to the numbers at the start.

$\endgroup$
6
  • 1
    $\begingroup$ Just to comment: I wouldn't be too sure about this conclusion. Number-theoretic conclusions like this have a tendency to suffer from our inability to compute out to sufficient range. Perhaps, if you compute much more than 5000 multiples, a number like 210=7*30 or 2310=11*210 will catch up to 30. Of course, there is some tension here, since, by the prime number theorem, the probability that a random number x is prime is roughly 1/ln(x). Presumably you could turn this into a heuristic argument that might confirm or refute your suspicion that 30 has the most prime-adjacent multiples. $\endgroup$
    – Stephen
    May 19, 2021 at 14:33
  • 1
    $\begingroup$ @Stephen You're right, I just tested the first 1,000,000 multiples for 30 and 210, and after a while 210 does eventually surpass 30 (if you're curious 30 has 413,647 and 210 has 427,024). Thanks for the suggestion! $\endgroup$
    – Recessive
    May 19, 2021 at 14:39
  • $\begingroup$ Sure, you're welcome! Now I'm interested to know if there is a number with more prime-adjacent multiples than any other or not. It might be that taking the product of the first $n$ primes, for each $n$, gives you a sequence of numbers each of which surpasses the last in primes-adjacent-to-mutiplesness. $\endgroup$
    – Stephen
    May 19, 2021 at 14:46
  • 1
    $\begingroup$ Cf. prime number races $\endgroup$ May 19, 2021 at 14:53
  • $\begingroup$ @J.W.Tanner Technically prime number races concern the fine-grained differences between admissible residues modulo the same number. Differences between distinct moduli can already be explained by PNT-AP. Though it could be reasonable to consider races between two moduli that share the same value of $\phi(n)/n$. $\endgroup$
    – Erick Wong
    May 21, 2021 at 3:39

2 Answers 2

2
$\begingroup$

The rough "reason" is that $30$ is the product of the first three primes, so the neighbors of its multiples can't have those primes as factors, which increases the probability that a neighbor is prime. That's why $6$ is another peak. If you look carefully (I haven't) you may find a kind of peak at $7 \times 30 = 210$.

$\endgroup$
5
  • $\begingroup$ Yes that's right, a more zoomed in graph shows exactly as you said, and it would seem my assertion 30 has the most prime-adjacent multiples is incorrect, as after a sufficient number of multiples, 210 surpasses 30. $\endgroup$
    – Recessive
    May 19, 2021 at 14:43
  • 2
    $\begingroup$ Following up on the comment from @Stephen you may find that the product of the first $k$ primes is always the leader for a while. That might even be a provable theorem. $\endgroup$ May 19, 2021 at 14:47
  • $\begingroup$ @EthanBolker Yes, while it is certainly a theorem that each primorial has a long term advantage over the previous, the question of whether it is always a leader comes down to 2 delicate factors: (cont’d) $\endgroup$
    – Erick Wong
    May 21, 2021 at 21:37
  • $\begingroup$ 1) Does every primorial have enough “runway” to take the lead before being overtaken by the next one? 2) Higher multiples have the same modular advantages (e.g. 30 vs 60) and are almost tied except for the influence of size. Are there enough fluctuations among these close competitors for a non-primorial to take the lead temporarily? $\endgroup$
    – Erick Wong
    May 21, 2021 at 21:43
  • 1
    $\begingroup$ @ErickWong I'm glad I only said "might be a provable theorem". $\endgroup$ May 22, 2021 at 2:03
2
$\begingroup$

There are two things. Factors of 30, and smallness of 30.
Neighbours of 30 are odd. Since almost all primes are odd and half of numbers are odd, that makes neighbours of 30 twice as likely to be prime. Also, not being multiples of 3 raises the odds by 3/2, and not being multiples of 5 gives another factor of 5/4. That is 15/4 times higher, compared with random numbers. Neighbours of 29 only get a boost of 29/28.
The other is the size of 30. Primes get rarer when you get higher; random numbers near N have a chance of about $1/\ln N$ to be prime. The middle of 1000 multiples of 30 is 15000, and $\ln15000=9.6$, but the middle of 1000 multiples of 210 is 105000, whose log is $11.56$. So, although 210 also excludes factors of 7 which gave an extra factor of 7/6 in the first paragraph, the log here washes it out. If you do 10000 multiples, neighbours of 210 might start to win out over multiples of 30.

$\endgroup$

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.