## Wednesday, September 07, 2022

### [aybvgyej] prime binary truncations

consider a number N.  if N is odd, test whether N is prime.  if N is even, test whether N+1 is prime.  set N := floor(N/2) and repeat primality testing until N=0.  of all the bitwise right shifts, how may are prime?

for example, start at N := 1580011307924772.  N+1 is prime (1)
N := floor(N/2) = 790005653962386.  N+1 is prime (2)
N := floor(N/2) = 395002826981193.
N := floor(N/2) = 197501413490596.  N+1 is prime (3)
N := floor(N/2) = 98750706745298.
N := floor(N/2) = 49375353372649.
N := floor(N/2) = 24687676686324.
N := floor(N/2) = 12343838343162.
N := floor(N/2) = 6171919171581.
N := floor(N/2) = 3085959585790.  N+1 is prime (4)
N := floor(N/2) = 1542979792895.
N := floor(N/2) = 771489896447.  N is prime (5)
N := floor(N/2) = 385744948223.  N is prime (6)
N := floor(N/2) = 192872474111.  N is prime (7)
N := floor(N/2) = 96436237055.
N := floor(N/2) = 48218118527.  N is prime (8)
N := floor(N/2) = 24109059263.  N is prime (9)
N := floor(N/2) = 12054529631.
N := floor(N/2) = 6027264815.
N := floor(N/2) = 3013632407.  N is prime (10)
N := floor(N/2) = 1506816203.  N is prime (11)
N := floor(N/2) = 753408101.  N is prime (12)
N := floor(N/2) = 376704050.
N := floor(N/2) = 188352025.
N := floor(N/2) = 94176012.  N+1 is prime (13)
N := floor(N/2) = 47088006.  N+1 is prime (14)
N := floor(N/2) = 23544003.
N := floor(N/2) = 11772001.
N := floor(N/2) = 5886000.
N := floor(N/2) = 2943000.  N+1 is prime (15)
N := floor(N/2) = 1471500.  N+1 is prime (16)
N := floor(N/2) = 735750.  N+1 is prime (17)
N := floor(N/2) = 367875.
N := floor(N/2) = 183937.
N := floor(N/2) = 91968.  N+1 is prime (18)
N := floor(N/2) = 45984.
N := floor(N/2) = 22992.  N+1 is prime (19)
N := floor(N/2) = 11496.  N+1 is prime (20)
N := floor(N/2) = 5748.  N+1 is prime (21)
N := floor(N/2) = 2874.
N := floor(N/2) = 1437.
N := floor(N/2) = 718.  N+1 is prime (22)
N := floor(N/2) = 359.  N is prime (23)
N := floor(N/2) = 179.  N is prime (24)
N := floor(N/2) = 89.  N is prime (25)
N := floor(N/2) = 44.
N := floor(N/2) = 22.  N+1 is prime (26)
N := floor(N/2) = 11.  N is prime (27)
N := floor(N/2) = 5.  N is prime (28)
N := floor(N/2) = 2.  N+1 is prime (29)
N := floor(N/2) = 1.
N := floor(N/2) = 0.

thus, the number produces 29 primes, which is the most (a record) among numbers up to that starting N.

when examining N=1, we've arbitrarily chosen not to count N+1 = 2 being prime.

the Pari/GP code below is brute force for pedagogical purposes:

countp(p)=my(numprimes=0); my(bitwidth=0); while(p>0, if(p%2, if(isprime(p), numprimes+=1); p=(p-1)/2, if(isprime(p+1), numprimes+=1); p/=2); bitwidth+=1); [numprimes, bitwidth]

best=0; for(n=0,+oo, a=countp(n); if(a[1]>best, best=a[1]; printbinary(n); print(" ",n," ",a," ",n+1)))

here are starting N which set records of producing increasing number of primes.  we give the number in binary (using period to signify zero) (illustrating rich veins of primes which work for a while, peter out, and later revive), in decimal, the number of primes, starting bitwidth, and N+1 (which I think is always prime).

```1. 2 [1, 2] 3 1.. 4 [2, 3] 5 1.1. 10 [3, 4] 11 1.11. 22 [4, 5] 23 1.111. 46 [5, 6] 47 1.1..11. 166 [6, 8] 167 1.11..11. 358 [7, 9] 359 1.11..111. 718 [8, 10] 719 1.11..1111. 1438 [9, 11] 1439 1.11..11111. 2878 [10, 12] 2879 1.11..1111111. 11518 [11, 14] 11519 1.11..11111111. 23038 [12, 15] 23039 1.11..11111111... 92152 [13, 17] 92153 1.11..11111111..... 368608 [14, 19] 368609 1.111111.1....1111.. 783420 [15, 20] 783421 1.111111.1....1111..... 6267360 [16, 23] 6267361 1.111111.1....1111...... 12534720 [17, 24] 12534721 1.111111.1.....111.1111111. 100273918 [18, 27] 100273919 1.11..11111111111111.1..11... 377487000 [19, 29] 377487001 1.11..11111111111111.1..11.... 754974000 [20, 30] 754974001 1.11..11111111111111.1..11...... 3019896000 [21, 32] 3019896001 1.11..11111.1..11111...1.11.1111... 24147626872 [22, 35] 24147626873 1.11..11111.1..11111...1.11.1111...1. 96590507490 [23, 37] 96590507491 1.11..111.1......11....11..1.111111111. 385744948222 [24, 39] 385744948223 1.11..111.1......11....11..1.1111111111. 771489896446 [25, 40] 771489896447 1.11..111.1......11....11..1.111111111111. 3085959585790 [26, 42] 3085959585791 1.11..111.1......11....11..1.1111111111111... 24687676686328 [27, 45] 24687676686329 1.111111.1....11111....111..11..1.11..11..11111. 210298272002878 [28, 48] 210298272002879 1.11..111.1......11....11..1.111111111111.1..1..1.. 1580011307924772 [29, 51] 1580011307924773 1.11..111.1......11....11..1.1111111111111...1.1.1111. 12640090463400286 [30, 54] 12640090463400287 1.111111.1....1111.......1111..11.1.1.11.11111..1..111. 26918107252899406 [31, 55] 26918107252899407 ```

what is the asymptotic growth rate of the records?  it appears worse than O(2^n).

the later entries were calculated with a Haskell program doing branch-and-bound, which is much more efficient than brute force.  below is the key routine.  searching all binary numbers of a given bitwidth is equivalent to traversing a full binary tree of a given height.  because we are looking for records, we know what previous record we need to exceed.  when exploring a node in the middle of the tree, we know how many primes (or primes minus 1) we already have in the path back to the root.  the upper bound of the number of primes left, down to the leaf, is the height above the leaves.  these can be combined to yield an upper bound for the number of primes on this branch of the tree.  if the upper bound is less than the goal, we can prune, abandoning this branch (mzero).

binary numbers are represented as little-endian lists of Bool.  searching the False branch first searches smaller numbers first.  (future work: it's probably better to store the "path so far" as a bitstring.)

dosearch :: forall m . (MonadPlus m) => Integer -> ([Bool], Integer) -> Integer -> m[Bool];
dosearch goal (_, primessofar) numleft | primessofar+numleft < goal = Monad.mzero;
dosearch _ (pathsofar, _) 0 = return pathsofar;
dosearch goal (pathsofar, primessofar) numleft = let {
nextodd :: [Bool] = True:pathsofar;
nextprimesofar :: Integer = if isPrime \$ binarytointeger nextodd
then 1+primessofar
else primessofar;
nextsearch :: [Bool] -> m [Bool];
nextsearch path = dosearch goal (path, nextprimesofar) (pred numleft);
} in nextsearch (False:pathsofar) `Monad.mplus` nextsearch nextodd;

(the infix application of mplus eliminates some parentheses.)

future work: parallelize, faster primality testing.

below is a list that includes numbers that tie (not necessarily exceed) the record number of primes.  these were found by brute force, so the list does not go as far as above.  the last number produces 21 primes.  no longer are all starting numbers prime or one less than a prime.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 16 17 18 19 20 21 22 23 36 37 40 41 42 43 44 45 46 47 72 73 82 83 88 89 92 93 94 95 106 107 144 145 146 147 148 149 150 151 156 157 162 163 164 165 166 167 178 179 190 191 292 293 312 313 330 331 332 333 334 335 346 347 352 353 356 357 358 359 382 383 586 587 660 661 716 717 718 719 1320 1321 1432 1433 1436 1437 1438 1439 2876 2877 2878 2879 5756 5757 5758 5759 6120 6121 11278 11279 11496 11497 11512 11513 11514 11515 11516 11517 11518 11519 12240 12241 22992 22993 23026 23027 23028 23029 23036 23037 23038 23039 24480 24481 46072 46073 46076 46077 46078 46079 48960 48961 48962 48963 84718 84719 90238 90239 91968 91969 92040 92041 92106 92107 92110 92111 92118 92119 92144 92145 92146 92147 92152 92153 97926 97927 184080 184081 184290 184291 184304 184305 184306 184307 184308 184309 195852 195853 195854 195855 195862 195863 360946 360947 360952 360953 360958 360959 367878 367879 368160 368161 368162 368163 368398 368399 368442 368443 368446 368447 368578 368579 368580 368581 368582 368583 368608 368609 391710 391711 737158 737159 737216 737217 737218 737219 783412 783413 783420 783421 1474432 1474433 1474438 1474439 1566826 1566827 1566840 1566841 1566842 1566843 1566846 1566847 2943000 2943001 2948712 2948713 2948864 2948865 2948866 2948867 2948872 2948873 2948876 2948877 2948878 2948879 2949118 2949119 3133642 3133643 3133652 3133653 3133654 3133655 3133680 3133681 3133682 3133683 3133684 3133685 3133686 3133687 3133692 3133693 3133694 3133695 3136512 3136513 4864080 4864081 5775126 5775127 5775148 5775149 5775270 5775271 5775336 5775337 5886000 5886001 5886002 5886003 5886006 5886007 5890582 5890583 5890606 5890607 5895118 5895119 5895166 5895167 5895366 5895367 5895418 5895419 5897250 5897251 5897266 5897267 5897278 5897279 5897424 5897425 5897426 5897427 5897728 5897729 5897730 5897731 5897732 5897733 5897734 5897735 5897744 5897745 5897746 5897747 5897752 5897753 5897754 5897755 5897756 5897757 5897758 5897759 5897760 5897761 5897766 5897767 5897806 5897807 5897818 5897819 5897832 5897833 5897952 5897953 5898236 5898237 5898238 5898239 6237598 6237599 6259972 6259973 6266926 6266927 6267060 6267061 6267070 6267071 6267076 6267077 6267082 6267083 6267284 6267285 6267286 6267287 6267298 6267299 6267304 6267305 6267306 6267307 6267308 6267309 6267310 6267311 6267346 6267347 6267360 6267361 6267366 6267367 6267388 6267389 11550298 11550299 11550540 11550541 11781166 11781167 11795460 11795461 11795470 11795471 11795518 11795519 12534142 12534143 12534568 12534569 12534616 12534617 12534618 12534619 12534720 12534721 12534778 12534779 25068286 25068287 25069138 25069139 25069440 25069441 25069442 25069443 25069468 25069469 25069556 25069557 25069558 25069559 34214398 34214399 47124666 47124667 47124862 47124863 47161342 47161343 47178132 47178133 47178238 47178239 47181960 47181961 50136572 50136573 50136574 50136575 50136660 50136661 50136958 50136959 50138276 50138277 50138278 50138279 50138470 50138471 50138478 50138479 50138880 50138881 50138882 50138883 50138884 50138885 50138886 50138887 50138926 50138927 50138936 50138937 50138938 50138939 50139112 50139113 50139114 50139115 50139116 50139117 50139118 50139119 68428792 68428793 68428796 68428797 68428798 68428799 92402388 92402389 92404198 92404199 92404342 92404343 94176000 94176001 94176012 94176013 94176028 94176029 94176772 94176773 94176778 94176779 94249332 94249333 94249334 94249335 94249338 94249339 94249720 94249721 94249722 94249723 94249724 94249725 94249726 94249727 94321342 94321343 94322684 94322685 94322686 94322687 94325866 94325867 94326666 94326667 94326718 94326719 94356022 94356023 94356264 94356265 94356266 94356267 94356476 94356477 94356478 94356479 94356570 94356571 94358800 94358801 94358808 94358809 94358826 94358827 94363656 94363657 94363680 94363681 94363692 94363693 94363728 94363729 94363768 94363769 94363920 94363921 94363922 94363923 94364026 94364027 94365888 94365889 94365892 94365893 94371750 94371751 100273056 100273057 100273138 100273139 100273140 100273141 100273144 100273145 100273146 100273147 100273148 100273149 100273150 100273151 100273152 100273153 100273320 100273321 100273322 100273323 100273912 100273913 100273916 100273917 100273918 100273919 100277766 100277767 100277872 100277873 188353558 188353559 188727312 188727313 188727456 188727457 188731786 188731787 188743500 188743501 200546302 200546303 200546640 200546641 200547836 200547837 200547838 200547839 200553106 200553107 200553108 200553109 200555520 200555521 200555526 200555527 200555532 200555533 200555534 200555535 200555542 200555543 200555566 200555567 200555700 200555701 200555712 200555713 200555744 200555745 200555746 200555747 200555752 200555753 273715192 273715193 342841318 342841319 369616798 369616799 369617340 369617341 369621540 369621541 376704000 376704001 376704006 376704007 376707116 376707117 376707118 376707119 376707480 376707481 376997280 376997281 376997338 376997339 376997352 376997353 376998406 376998407 376998888 376998889 376998898 376998899 376998900 376998901 377289658 377289659 377303040 377303041 377303470 377303471 377303532 377303533 377306668 377306669 377425056 377425057 377425912 377425913 377426280 377426281 377454624 377454625 377454626 377454627 377454628 377454629 377454768 377454769 377454912 377454913 377454914 377454915 377454996 377454997 377455692 377455693 377456110 377456111 377463552 377463553 377463570 377463571 377463572 377463573 377463574 377463575 377487000 377487001 401111040 401111041 401111068 401111069 401111400 401111401 401111506 401111507 753408000 753408001 754613338 754613339 754850112 754850113 754851826 754851827 754852560 754852561 754909828 754909829 754927140 754927141 754974000 754974001 1509948000 1509948001 1509948002 1509948003 1604444220 1604444221 1604446026 1604446027 3013632406 3013632407 3018453358 3018453359 3019410240 3019410241 3019708566 3019708567 3019896000 3019896001 6036906718 6036906719 6039792000 6039792001 6039792002 6039792003 6039792006 6039792007 6417777072 6417777073 6417807238 6417807239 12073713072 12073713073 12073813436 12073813437 12073813438 12073813439 12077629236 12077629237 12078563326 12078563327 12078595558 12078595559 12078834268 12078834269 12079584000 12079584001 12079584002 12079584003 12079584004 12079584005 12079584006 12079584007 12079584012 12079584013 12079584014 12079584015 12079584016 12079584017 12079584028 12079584029 12079584046 12079584047 12079584052 12079584053 12834985258 12834985259 12835553760 12835553761 12835553770 12835553771 12835554144 12835554145 12835554146 12835554147 12835554232 12835554233 12835587846 12835587847 12835614476 12835614477 12835614478 12835614479