4
$\begingroup$

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:

enter image description here

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)$:

enter image description here

enter image description here

$\endgroup$
8
  • 3
    $\begingroup$ "take all multiples that have a prime off-by-one" - I'm having hard time trying to understand what you mean. Could you, please, elaborate and provide exact definitions? $\endgroup$
    – lisyarus
    May 19, 2021 at 4:59
  • $\begingroup$ @lisyarus I think it means that, for example, $17\cdot4$, $17\cdot6$, $17\cdot8$ are all $1$ away from a prime. But for example $17\cdot2$, $17\cdot10$ are not. $\endgroup$
    – 2'5 9'2
    May 19, 2021 at 5:07
  • $\begingroup$ @MorganRodgers I know why that is for 6, I was just exploring other numbers out of curiosity and noticed some numbers shared similar distributions $\endgroup$
    – Recessive
    May 19, 2021 at 5:16
  • $\begingroup$ @lisyarus I edited the question to be more clear, concisely put: "I am taking all multiples $k$ of a number $n$ such that $kn \pm 1$ is prime" $\endgroup$
    – Recessive
    May 19, 2021 at 5:17
  • 2
    $\begingroup$ This is nice work, but ultimately your terminology is too vague, and it is unclear what you are asking. $\endgroup$ May 19, 2021 at 6:05

1 Answer 1

3
$\begingroup$

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):

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)
$\endgroup$
4
  • $\begingroup$ Thank you for the really interesting maths you brought up! I tried testing your hypothesis on a few other numbers, but it doesn't seem to hold in all cases. Such as the case for 24 and 6, which have $\frac{24}{8}$ and $\frac{6}{2}$ respectively, but have very different sequences (as can be seen in the combined plot in the original post). It does seem that all numbers with close sequences do have similar proportions however. Nonetheless, the maths is really interesting and the related theory is a great help! $\endgroup$
    – Recessive
    May 19, 2021 at 13:25
  • $\begingroup$ A bit of tangent as well, but by looking at the same graph it would seem that 30 has more multiples with adjacent primes (at least within the first 1000 multiples) than 6, which is really interesting because all primes are adjacent to multiples of 6. Could be helpful for probabilistically finding primes $\endgroup$
    – Recessive
    May 19, 2021 at 13:30
  • 1
    $\begingroup$ Hm, indeed. My answer does not really explain these things. Curious. But for now thats all I have time for. Glad it was somewhat interesting at least ;) $\endgroup$
    – Simon
    May 19, 2021 at 13:40
  • $\begingroup$ Another simple explanation is that $$17k\equiv 19k\implies k\equiv 0,3\pmod 6$$ is often a requirement for them both to be prime on the same side. $\endgroup$ Sep 27, 2021 at 21:19

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.