Calculation without Words : Doric Columns of Primes

                       1
                       2  =  1 * 2
                       3  =  3

                       2  =  2
                       3  =  1 * 3
                       4  =  2 * 2
                       5  =  5

                      12  =  2^2 * 3
                      13  =  1 * 13
                      14  =  2 *  7
                      15  =  3 *  5
                      16  =  2^4

                   12720  =  2^4 * 3 * 5 * 53
                   12721  =  1 * 12721
                   12722  =  2 *  6361
                   12723  =  3 *  4241
                   12724  =  4 *  3181
                   12725  =  5^2 * 509

                   19440  =  2^4 * 3^5 * 5
                   19441  =  1 * 19441
                   19442  =  2 *  9721
                   19443  =  3 *  6481
                   19444  =  4 *  4861
                   19445  =  5 *  3889
                   19446  =  2 * 3 * 7 * 463

                 5516280  =  2^3 * 3^2 * 5 * 7 * 11 * 199
                 5516281  =  1 * 5516281
                 5516282  =  2 * 2758141
                 5516283  =  3 * 1838761
                 5516284  =  4 * 1379071
                 5516285  =  5 * 1103257
                 5516286  =  6 *  919381
                 5516287  =  7 *  788041
                 5516288  =  2^10 * 5387

              7321991040  =  2^7 * 3^2 * 5 * 7 * 13 * 61 * 229
              7321991041  =  1 * 7321991041
              7321991042  =  2 * 3660995521
              7321991043  =  3 * 2440663681
              7321991044  =  4 * 1830497761
              7321991045  =  5 * 1464398209
              7321991046  =  6 * 1220331841
              7321991047  =  7 * 1045998721
              7321991048  =  8 *  915248881
              7321991049  =  3^2 * 79 * 10298159

            363500177040  =  2^4 * 3^3 * 5 * 7^3 * 11 * 13 * 47 * 73
            363500177041  =  1 * 363500177041
            363500177042  =  2 * 181750088521
            363500177043  =  3 * 121166725681
            363500177044  =  4 *  90875044261
            363500177045  =  5 *  72700035409
            363500177046  =  6 *  60583362841
            363500177047  =  7 *  51928596721
            363500177048  =  8 *  45437522131
            363500177049  =  9 *  40388908561
            363500177050  =  2 * 5^2 * 59 * 2203 * 55933

           2394196081200  =  2^4 * 3^2 * 5^2 * 7 * 11 * 17 * 197 * 2579
           2394196081201  =   1 * 2394196081201
           2394196081202  =   2 * 1197098040601
           2394196081203  =   3 *  798065360401
           2394196081204  =   4 *  598549020301
           2394196081205  =   5 *  478839216241
           2394196081206  =   6 *  399032680201
           2394196081207  =   7 *  342028011601
           2394196081208  =   8 *  299274510151
           2394196081209  =   9 *  266021786801
           2394196081210  =  10 *  239419608121
           2394196081211  =  11 * 29 * 41 * 79 * 2317171

        3163427380990800  =  2^4 * 3^2 * 5^2 * 7^2 * 11 * 281 * 433 * 13399
        3163427380990801  =   1 * 3163427380990801
        3163427380990802  =   2 * 1581713690495401
        3163427380990803  =   3 * 1054475793663601
        3163427380990804  =   4 *  790856845247701
        3163427380990805  =   5 *  632685476198161
        3163427380990806  =   6 *  527237896831801
        3163427380990807  =   7 *  451918197284401
        3163427380990808  =   8 *  395428422623851
        3163427380990809  =   9 *  351491931221201
        3163427380990810  =  10 *  316342738099081
        3163427380990811  =  11 *  287584307362801
        3163427380990812  =  2^2 * 3 * 13 * 23 * 37 * 47 * 977 * 518933


                   n + i  =  i * p
                                  i




Calculation with Words : Doric Columns of Primes

I propose that these striking, delightful columns of primes which are distinguished landmarks of rectilinearity in the beauty found in the complex mixture of regularity and irregularity of the stream of the factors of the integers should be known as Doric Columns of Primes, because of their shape and, especially, in honor of their creative architect, Charlie Dorian.

There were four most significant features of the search algorithm used. Firstly, elementary considerations were used to reduce the number of candidate solutions. For example, n[11] must be divisible by 55440 = 16 * 9 * 5 * 7 * 11. Secondly, and most importantly, for each candidate, as each potentially disqualifying factor was considered, the integers in the entire block were examined, with the most likely factors being considered first. This technique is called Gang Factoring. Generally, the smaller factors are more likely to be misplaced in the block. In seeking n[11], only one candidate in more than 400 required consideration of any factor larger than 29. Thirdly, the small factors were sieved using integer arithmetic, without multiplication or division operations, just 8-bit subtractions and comparisons. Fourthly, highly optimized assembler code allowed the execution of only about 6 instructions to eliminate each small factor. The final algorithm, an unsuccessful search for n[12], was about 300 billion times more efficient than the one first implemented. As a result, running on a V-20 and 8087 equipped 4.77 MHz IBM-PC, the entire search, which extended to 2^53, took only a few months of execution time.

Open questions:
1) Do arbitrarily tall Doric Columns exist?
2) If not, how many and how large?

-

2000 Mathematics Subject Classification : Primary 11Y11 , 11A51 ; Secondary 11Y05 , 11A05 , 11A41 , 11N05 , 11N25 , 11Y11 , 11Y50 , 11Y55 .

This calculation was proposed and reported on the NUMBER Conference of the MIX Bulletin Board System of the Capital PC User Group .
The illustrious Roger Fajman was the SYSOP of MIX , the Member Information eXchange .
I was the moderator of the conference .
This calculation arose from a spirit of fun in part engendered by Oystein Ore's Number Theory and Its History , McGraw-Hill , 1948 ; Dover reprint , 1988 , ISBN: 9780486656205 .

Walter Nissen
written between 1991-06-26 and 1991-08-12
posted 2008-06-16