Why are some numbers "paired" in their prime distribution

Question

Sorry I'm not sure exactly how to word the question. I was exploring off-by-one primes for each number, as I found it curious enormous primes were searched to be one off a power of $2$, and all primes are one off a multiple of $6$, so started searching through all numbers, and quickly noticed that some numbers shared very similar distributions. As an example, take a look at $17$ and $19$, if you take all multiples that have a prime off-by-one up to $1000$:

17: 4, 6, 8, 14, 16, 18, 22, 24, 26, 30, 34, 36, 38, 52, 54, 56, 60, 64, 66, 72, 74, 76, 78, 80, 84, 90, 94, 98, 100, 102, 106, 110, 116, 120, 126, 132, 136, 138, 140, 144, 150, 154, 158, 160, 162, 164, 168, 174, 180, 186, 190, 194, 196, 202, 204, 210, 214, 216, 220, 228, 230, 232, 236, 240, 248, 252, 260, 266, 270, 274, 276, 280, 282, 286, 290, 294, 300, 304, 308, 312, 318, 320, 324, 336, 340, 342, 344, 346, 356, 360, 366, 368, 372, 374, 378, 384, 386, 396, 402, 404, 410, 414, 424, 426, 430, 436, 440, 444, 446, 450, 454, 456, 462, 474, 476, 480, 486, 488, 490, 492, 496, 498, 500, 510, 514, 518, 520, 526, 530, 532, 540, 546, 550, 554, 560, 564, 566, 570, 576, 580, 584, 594, 596, 604, 606, 608, 610, 624, 630, 638, 644, 652, 654, 664, 666, 672, 676, 678, 682, 690, 696, 698, 702, 704, 708, 710, 720, 726, 728, 730, 734, 736, 738, 742, 744, 756, 760, 762, 774, 780, 784, 788, 792, 794, 798, 802, 804, 816, 818, 824, 832, 834, 840, 844, 850, 854, 856, 860, 862, 866, 876, 886, 890, 894, 896, 900, 906, 918, 920, 930, 934, 936, 952, 954, 956, 960, 966, 980, 982, 984, 986, 990, 996

19: 2, 6, 8, 10, 12, 20, 22, 24, 30, 32, 34, 36, 40, 42, 48, 56, 58, 64, 68, 72, 78, 82, 84, 90, 92, 94, 96, 98, 100, 108, 110, 112, 116, 118, 120, 124, 126, 138, 140, 142, 150, 152, 154, 156, 158, 160, 162, 168, 170, 174, 176, 182, 186, 188, 198, 204, 210, 212, 222, 232, 234, 236, 238, 240, 242, 244, 246, 250, 252, 258, 272, 278, 288, 296, 300, 302, 306, 308, 312, 318, 320, 330, 338, 352, 356, 358, 360, 364, 368, 372, 380, 384, 386, 390, 394, 396, 398, 402, 408, 410, 412, 414, 422, 426, 430, 432, 448, 454, 456, 460, 462, 468, 470, 472, 474, 476, 482, 490, 492, 498, 502, 506, 510, 514, 516, 530, 538, 540, 544, 552, 558, 560, 566, 570, 572, 582, 588, 594, 600, 602, 608, 618, 620, 628, 630, 632, 640, 642, 658, 660, 662, 666, 680, 682, 686, 690, 692, 694, 702, 708, 714, 720, 724, 728, 732, 746, 750, 754, 758, 762, 768, 770, 772, 778, 780, 784, 798, 800, 804, 806, 810, 812, 814, 818, 820, 822, 828, 832, 838, 840, 846, 848, 852, 858, 860, 864, 866, 868, 870, 872, 874, 882, 888, 894, 900, 902, 910, 912, 918, 922, 930, 932, 934, 936, 948, 950, 952, 954, 966, 978, 988

They vary slightly, but they are largely similar. Comparatively, other combinations don't follow a similarly close-fit pattern:

15: 2, 4, 6, 10, 12, 14, 16, 18, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 62, 66, 68, 70, 74, 78, 80, 82, 84, 86, 88, 92, 94, 96, 98, 100, 102, 104, 108, 114, 116, 120, 122, 124, 126, 130, 132, 134, 136, 138, 140, 142, 144, 148, 150, 152, 154, 156, 158, 160, 164, 168, 170, 172, 174, 178, 180, 182, 186, 188, 190, 192, 194, 196, 198, 200, 204, 206, 208, 212, 214, 218, 220, 222, 224, 226, 230, 234, 236, 238, 242, 244, 246, 248, 252, 262, 266, 268, 270, 272, 274, 276, 280, 282, 284, 286, 290, 294, 296, 304, 306, 308, 310, 312, 320, 322, 324, 326, 328, 330, 334, 336, 340, 346, 352, 354, 360, 362, 368, 372, 376, 378, 380, 386, 388, 390, 392, 396, 402, 406, 408, 410, 414, 418, 420, 422, 424, 426, 428, 430, 432, 438, 440, 444, 446, 448, 452, 456, 458, 460, 464, 466, 468, 472, 474, 482, 488, 490, 494, 500, 502, 504, 506, 508, 510, 512, 516, 522, 528, 530, 534, 536, 538, 540, 544, 546, 548, 554, 558, 562, 564, 568, 572, 574, 576, 578, 580, 582, 584, 588, 590, 596, 598, 600, 602, 604, 606, 610, 612, 614, 616, 626, 628, 632, 634, 636, 640, 642, 644, 646, 648, 650, 652, 654, 656, 658, 660, 662, 672, 674, 676, 678, 684, 686, 688, 700, 702, 704, 706, 710, 714, 716, 718, 720, 722, 724, 726, 730, 732, 738, 742, 744, 750, 752, 754, 758, 760, 766, 768, 770, 772, 780, 782, 786, 788, 794, 796, 798, 808, 810, 814, 816, 818, 820, 822, 826, 828, 830, 832, 834, 836, 838, 840, 844, 846, 848, 852, 854, 856, 860, 864, 870, 874, 878, 882, 884, 886, 892, 894, 896, 898, 900, 906, 908, 910, 912, 914, 920, 922, 924, 928, 934, 938, 944, 948, 950, 952, 956, 958, 960, 962, 964, 966, 968, 970, 976, 978, 980, 982, 984, 988, 990, 992, 996, 998

17: 4, 6, 8, 14, 16, 18, 22, 24, 26, 30, 34, 36, 38, 52, 54, 56, 60, 64, 66, 72, 74, 76, 78, 80, 84, 90, 94, 98, 100, 102, 106, 110, 116, 120, 126, 132, 136, 138, 140, 144, 150, 154, 158, 160, 162, 164, 168, 174, 180, 186, 190, 194, 196, 202, 204, 210, 214, 216, 220, 228, 230, 232, 236, 240, 248, 252, 260, 266, 270, 274, 276, 280, 282, 286, 290, 294, 300, 304, 308, 312, 318, 320, 324, 336, 340, 342, 344, 346, 356, 360, 366, 368, 372, 374, 378, 384, 386, 396, 402, 404, 410, 414, 424, 426, 430, 436, 440, 444, 446, 450, 454, 456, 462, 474, 476, 480, 486, 488, 490, 492, 496, 498, 500, 510, 514, 518, 520, 526, 530, 532, 540, 546, 550, 554, 560, 564, 566, 570, 576, 580, 584, 594, 596, 604, 606, 608, 610, 624, 630, 638, 644, 652, 654, 664, 666, 672, 676, 678, 682, 690, 696, 698, 702, 704, 708, 710, 720, 726, 728, 730, 734, 736, 738, 742, 744, 756, 760, 762, 774, 780, 784, 788, 792, 794, 798, 802, 804, 816, 818, 824, 832, 834, 840, 844, 850, 854, 856, 860, 862, 866, 876, 886, 890, 894, 896, 900, 906, 918, 920, 930, 934, 936, 952, 954, 956, 960, 966, 980, 982, 984, 986, 990, 996

Taking a wider look and comparing all numbers from $2$ to $40$, it gets a bit messy and hard to decipher anything reasonable:

I'm not sure if there's some formalized theory behind the frequency of this, so any information related would be really helpful!

EDIT: A more specific definition of what I mean by "off-by-one"

I am taking all multiples $k$ of a number $n$ such that $kn \pm 1$ is prime.

So for $17$:

$k = 1$: $\quad1\cdot17 \pm 1$ isn't prime

$k = 2$: $\quad2\cdot17 \pm 1$ isn't prime

$k = 3$: $\quad3\cdot17 \pm 1$ isn't prime

$k = 4$: $\quad4\cdot17 - 1$ is prime

$k = 5$: $\quad5\cdot17 \pm 1$ isn't prime

$k = 6$: $\quad6\cdot17 - 1$ is prime (and so is $6\cdot17 + 1$)

EDIT $2$: A graph comparing just the sequences for $(15, 17)$, and $(17, 19)$:

Answer 1

Kudos for spotting such a pattern on your own. Here are some ideas from number theory (though I'm not sure if they will be satisfactory for you):

• First, you should check out Dirichlet's theorem on arithmetic progressions. One of the consequences of that theorem is that for any number $n$, about one in $\phi(n)$ prime numbers is of the form $kn-1$. ($\phi$ is Euler's totient function.)
• Secondly, you might know that up to some upper bound $M$, there are about $\frac{M}{\log(M)}$ prime numbers in total (Prime number theorem).

These two facts together imply that for some upper bound $K$, the number of possible $k\in\{1,...,K\}$ for which $kn-1$ is prime, is about $$\frac{Kn-1}{\log(Kn-1)}\cdot\frac{1}{\phi(n)} \approx K\frac{n}{\phi(n)}\frac{1}{\log(K)}$$ (approximation is good for large $K$).

Now to your examples:

• For $n=15$, it is $\phi(15)=8$, so the proprtion of $k$ that works is approximately $$\frac{n}{\phi(n)}\frac{1}{\log(K)}=\frac{15}{8}\frac{1}{\log(K)}$$
• For $n=17$ and $\phi(17)=16$ the proportion is approximately $$\frac{17}{16}\frac{1}{\log(K)}$$
• and for $n=19$ with $\phi(19)=18$, it is about $$\frac{19}{18}\frac{1}{\log(k)}$$

So it makes a lot of sense that the graphs of $17$ and $19$ are very close to each other while $15$ is away much further.

Still, this analysis suggests that the graphs for $17$ and $19$ eventually diverge as well (after all, $\frac{17}{16}\neq\frac{19}{18}$). But in practice they will diverge less than this analysis shows because: There is something called Chebyshev's_bias which for our purposes implies that the true proportion of primes of the form $17k-1$ is a little bit higher than $1/\phi(17)$ and the true proportion of primes of the form $19k-1$ is a little bit lower than $1/\phi(19)$. This comes from the fact that $-1$ is a square number modulo $17$, but $-1$ is not a square number modulo $19$. But explaining how this works is WAY beyond the scope of this question, I think. :)

EDIT: after seeing your comments it was clear that more careful analysis is needed.

1. approximating $\log(nK)\approx\log(K)$ is not very good for the values of $K$ you are using.
2. approximating the prime-counting function as $m/\log(m)$ is not precise enough. A better approximation is the Logarithmic integral function $\mathrm{li(x)}$ which has a nice asymptotic expansion. With this, the number of $k\le K$ for which $kn-1$ is prime becomes \begin{align} P(n,K) &\approx \frac{\mathrm{li}(Kn)}{\phi(n)} \\ &= \frac{Kn}{\phi(n)\log(Kn)}\left(1 + \frac{1!}{\log(Kn)} + \frac{2!}{\log^2(Kn)}+...\right). \end{align}

If you plot this function together with your experimental results (using only two ord, you should get a very nice match even for moderate $K$. Also this form correctly predicts that

• the graphs of $24$ and $6$ dont coincide even though the fraction $n/\phi(n)$ is the same for both.
• $n=30$ has more adjacent primes than $n=6$, even though that could seem counterintuitive as all primes are adjacent to multiple of $6$ but only a quarter of all primes are a multiple of $30$. I think the intuitive reason for this is: numbers of the form $6k-1$ are never devisible by $2$ or $3$. Numbers of the form $30k-1$ are never divisible by $2$, $3$ or $5$. Therefore the latter have a higher chance of being prime. (This is really not a rigorous argument, just an intuition)