This blog post, https://blog.plover.com/math/prime-mnemonics.html posed the intriguing task of memorizing the primes up to 1000. The most straightforward method is just to memorize the 168 of them in order.
However, it might be slightly easier to break the task into 4 smaller roughly equal sized tasks. The numbers in each list below have the same last digit (residue classes modulo 10):
11 31 41 61 71 101 131 151 181 191 211 241 251 271 281 311 331 401 421 431 461 491 521 541 571 601 631 641 661 691 701 751 761 811 821 881 911 941 971 991
3 13 23 43 53 73 83 103 113 163 173 193 223 233 263 283 293 313 353 373 383 433 443 463 503 523 563 593 613 643 653 673 683 733 743 773 823 853 863 883 953 983
7 17 37 47 67 97 107 127 137 157 167 197 227 257 277 307 317 337 347 367 397 457 467 487 547 557 577 587 607 617 647 677 727 757 787 797 827 857 877 887 907 937 947 967 977 997
19 29 59 79 89 109 139 149 179 199 229 239 269 349 359 379 389 409 419 439 449 479 499 509 569 599 619 659 709 719 739 769 809 829 839 859 919 929
One also needs to add primes 2 and 5 to the above lists.
Incidentally, "Prime number races" by Andrew Granville and Greg Martin discusses the comparative lengths of these lists.
When memorizing the lists, it might be helpful to keep in mind that multiples of 3 occur periodically within each reside class. For example, numbers in this arithmetic sequence will never occur in the first list because they are all divisible by 3:
(x mod 10)==1: 21, 51, 81, 111, 141,...
Similarly for the other residue classes:
(x mod 10)==3: 3, 33, 63, 93, 123,...
(x mod 10)==7: 27, 57, 87, 117, 147,...
(x mod 10)==9: 9, 39, 69, 99, 129,...
However, rather than remembering these, it might be easier just to do the digital-root divisibility test of 3.
Here are the lists for multiples of 7:
(x mod 10)==1: 21, 91, 161, 231, 301,...
(x mod 10)==3: 63, 133, 203, 273, 343,...
(x mod 10)==7: 7, 77, 147, 217, 287,...
(x mod 10)==9: 49, 119, 189, 259, 329,...
Multiples of larger primes yield diminishing returns; you end up just memorizing the composites.
We now turn our attention back to the idea explored in the motivating post mentioned above, that there can be at most 4 primes in each decade. It's kind of the transpose of the four lists above.
We first thought we might be able to do better by considering blocks of 30=2*3*5 instead of 10. There can be at most 8 primes in a block of 30, and 8/30 (eliminating 73%) is more efficient than 4/10 (eliminating 60%). However the extra factor of 3 in 30 versus 10 doesn't buy us much because of the easy sum-the-digits divisibility test for 3.
The motivating post mapped the pattern of up to 4 primes within a decade to 4-bit binary numbers 0..15, then assigned the binary numbers to letters. We don't go so far, and simply give below each decade with its corresponding little-endian binary number converted to decimal. We can imagine learning these associations with flash cards. For example, in the tuple (90,4), the 4 is 0010 in little-endian binary (NB: this is the reverse of the traditional big-endian, how binary numbers are typically written). The bits correspond to offsets 1379, so the bit for 7 is set, so 90+7 is prime.
(0,6), (10,15), (20,10), (30,5), (40,7), (50,10), (60,5), (70,11), (80,10), (90,4), (100,15), (110,2), (120,4), (130,13), (140,8), (150,5), (160,6), (170,10), (180,1), (190,15), (200,0), (210,1), (220,14), (230,10), (240,1), (250,5), (260,10), (270,5), (280,3), (290,2), (300,4), (310,7), (320,0), (330,5), (340,12), (350,10), (360,4), (370,10), (380,10), (390,4), (400,9), (410,8), (420,1), (430,11), (440,10), (450,4), (460,7), (470,8), (480,4), (490,9), (500,10), (510,0), (520,3), (530,0), (540,5), (550,4), (560,10), (570,5), (580,4), (590,10), (600,5), (610,14), (620,0), (630,1), (640,7), (650,10), (660,1), (670,6), (680,2), (690,1), (700,9), (710,8), (720,4), (730,10), (740,2), (750,5), (760,9), (770,2), (780,4), (790,4), (800,8), (810,1), (820,15), (830,8), (840,0), (850,14), (860,2), (870,4), (880,7), (890,0), (900,4), (910,9), (920,8), (930,4), (940,5), (950,2), (960,4), (970,5), (980,2), (990,5)
Incidentally, the decades whose number is 15, e.g., 10 100 190, corresponding to 4 primes in a decade, are maximally dense groupings of 4 primes known as prime decades or prime quadruplets, cf., twin primes.
We improve upon the above list by noting that multiples of 3 are easily to eliminate by digital root. In some decades (in fact, in 2/3 of them), two of the four possibilities are eliminated by divisibility by 3. In those decades we only need to remember a 2-bit number, not 4. It's trickier to figure out which bits correspond to which number, though. In the list below, the number of bits is given after the slash, though it's not necessary to memorize that number. For example, consider (90,2/2). In the decade 91 93 97 99, two of the numbers (93, 99) are eliminated by divisibility by 3. The number 2 before the slash is 01 in little-endian binary and corresponds to the remaining two {91,97}. Therefore 97 is prime and 91 is not.
(0,6/3), (10,15/4), (20,3/2), (30,3/2), (40,7/4), (50,3/2), (60,3/2), (70,11/4), (80,3/2), (90,2/2), (100,15/4), (110,1/2), (120,2/2), (130,13/4), (140,2/2), (150,3/2), (160,6/4), (170,3/2), (180,1/2), (190,15/4), (200,0/2), (210,1/2), (220,14/4), (230,3/2), (240,1/2), (250,5/4), (260,3/2), (270,3/2), (280,3/4), (290,1/2), (300,2/2), (310,7/4), (320,0/2), (330,3/2), (340,12/4), (350,3/2), (360,2/2), (370,10/4), (380,3/2), (390,2/2), (400,9/4), (410,2/2), (420,1/2), (430,11/4), (440,3/2), (450,2/2), (460,7/4), (470,2/2), (480,2/2), (490,9/4), (500,3/2), (510,0/2), (520,3/4), (530,0/2), (540,3/2), (550,4/4), (560,3/2), (570,3/2), (580,4/4), (590,3/2), (600,3/2), (610,14/4), (620,0/2), (630,1/2), (640,7/4), (650,3/2), (660,1/2), (670,6/4), (680,1/2), (690,1/2), (700,9/4), (710,2/2), (720,2/2), (730,10/4), (740,1/2), (750,3/2), (760,9/4), (770,1/2), (780,2/2), (790,4/4), (800,2/2), (810,1/2), (820,15/4), (830,2/2), (840,0/2), (850,14/4), (860,1/2), (870,2/2), (880,7/4), (890,0/2), (900,2/2), (910,9/4), (920,2/2), (930,2/2), (940,5/4), (950,1/2), (960,2/2), (970,5/4), (980,1/2), (990,3/2)
The pattern of bits needed is periodic: 422 422...
Is this list better? It's of course subjective. There are the same number of numbers to memorize, but the magnitudes are smaller. Previously, hypothesizing that smaller numbers are easier to memorize.
No comments :
Post a Comment