Threaded Mode | Linear Mode

Valentin Albillo · 11-14-2016, 01:20 AM

Hi, Joe:

(10-27-2016 02:17 PM)Joe Horn Wrote: Imagine this sequence of integers: {403, 4033, 40333, 403333, ...}. Each term of the sequence is 10 times the previous term +3. [...] Mini-challenge: Find the smallest prime term in this sequence.

Just found this mini-challenge, I don't usually check this forum but today I did. This is my first, naive solution using UBASIC running on a very old, 2000-era pc:

        1   word -540:point -2:N=40:clr time
        2   N=N*10+3:if fnPrim(N) print time;len(str(N))-1;N," prime":end else 2

        run

        0:00:16  485   40333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333 prime

i.e: it finds the featured 485-digit prime number in 16 seconds. It repeatedly calls fnPrim(N), which is a typical probabilistic primality test. The timing is quite fast at 16 seconds in such old hardware (a modern pc will be an order of magnitude faster) but it can be greatly improved upon, more than halved in fact, this way:

First, we use this one-liner from the command prompt to generate a list of the first 79 numbers of the required form (plus the origin, 40, which is not of that form), together with their least divisor:

n=40 : for i%=1 to 80 : print i%;n;prmdiv(n) : n=n*10+3 : next i%

index    number    least divisor
----------------------------------
1 40 2
2 403 13
3 4033 37
4 40333 53
5 403333 7
6 4033333 37
7 40333333 17
8 403333333 13
9 4033333333 37
10 40333333333 199
11 403333333333 7
12 4033333333333 37
13 40333333333333 509
14 403333333333333 13
15 4033333333333333 37
16 40333333333333333 43
17 403333333333333333 7
18 4033333333333333333 37
19 40333333333333333333 1523
20 403333333333333333333 13
21 4033333333333333333333 37
22 40333333333333333333333 3467
23 403333333333333333333333 7
24 4033333333333333333333333 37
25 40333333333333333333333333 19
26 403333333333333333333333333 13
27 4033333333333333333333333333 37
28 40333333333333333333333333333 71
29 403333333333333333333333333333 7
30 4033333333333333333333333333333 37
31 40333333333333333333333333333333 61
32 403333333333333333333333333333333 13
33 4033333333333333333333333333333333 37
34 40333333333333333333333333333333333 227
35 403333333333333333333333333333333333 7
36 4033333333333333333333333333333333333 37
37 40333333333333333333333333333333333333 43
38 403333333333333333333333333333333333333 13
39 4033333333333333333333333333333333333333 17
40 40333333333333333333333333333333333333333 1163
41 403333333333333333333333333333333333333333 7
42 4033333333333333333333333333333333333333333 37
43 40333333333333333333333333333333333333333333 19
44 403333333333333333333333333333333333333333333 13
45 4033333333333333333333333333333333333333333333 37
46 40333333333333333333333333333333333333333333333 0 (no divisor <= 131072)
47 403333333333333333333333333333333333333333333333 7
48 4033333333333333333333333333333333333333333333333 37
49 40333333333333333333333333333333333333333333333333 6907
50 403333333333333333333333333333333333333333333333333 13
51 4033333333333333333333333333333333333333333333333333 37
52 40333333333333333333333333333333333333333333333333333 83
53 403333333333333333333333333333333333333333333333333333 7
54 4033333333333333333333333333333333333333333333333333333 37
55 40333333333333333333333333333333333333333333333333333333 17
56 403333333333333333333333333333333333333333333333333333333 13
57 4033333333333333333333333333333333333333333333333333333333 37
58 40333333333333333333333333333333333333333333333333333333333 43
59 403333333333333333333333333333333333333333333333333333333333 7
60 4033333333333333333333333333333333333333333333333333333333333 37
61 40333333333333333333333333333333333333333333333333333333333333 19
62 403333333333333333333333333333333333333333333333333333333333333 13
63 4033333333333333333333333333333333333333333333333333333333333333 37
64 40333333333333333333333333333333333333333333333333333333333333333 0 (ditto)
65 403333333333333333333333333333333333333333333333333333333333333333 7
66 4033333333333333333333333333333333333333333333333333333333333333333 37
67 40333333333333333333333333333333333333333333333333333333333333333333 29
68 403333333333333333333333333333333333333333333333333333333333333333333 13
69 4033333333333333333333333333333333333333333333333333333333333333333333 37
70 40333333333333333333333333333333333333333333333333333333333333333333333 0 (ditto)
71 403333333333333333333333333333333333333333333333333333333333333333333333 7
72 4033333333333333333333333333333333333333333333333333333333333333333333333 37
73 40333333333333333333333333333333333333333333333333333333333333333333333333 229
74 403333333333333333333333333333333333333333333333333333333333333333333333333 13
75 4033333333333333333333333333333333333333333333333333333333333333333333333333 37
76 40333333333333333333333333333333333333333333333333333333333333333333333333333 191
77 403333333333333333333333333333333333333333333333333333333333333333333333333333 7
78 4033333333333333333333333333333333333333333333333333333333333333333333333333333 37
79 40333333333333333333333333333333333333333333333333333333333333333333333333333333 19
80 403333333333333333333333333333333333333333333333333333333333333333333333333333333 13

                (Note: the three numbers above which have no least divisor <= 131072 are composite and their least divisors are the following:

                 46 40333333333333333333333333333333333333333333333 = 126111187283744169246359 * P24
                 64 40333333333333333333333333333333333333333333333333333333333333333 = 14150197 * P58
                 70 40333333333333333333333333333333333333333333333333333333333333333333333 = 1330559 * C65
                 )

and you can readily observe that the highlighted numbers have 7 as a divisor for indexes 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 71, and 77, i.e., for those indexes i which obey

        i mod 6 = 5

Further observation of the first 79 numbers above shows that these primes are their least divisors for indexes obeying the following:

        divisor   indexes                 condition
        -------------------------------------------------------
         7        5, 11, 17, 23,..        i mod 6 = 5
        13        2, 8, 14, 20,...        i mod 6 = 2
        17        7, (23), 39, 55,..      i mod 16 = 7
        19        (7), 25, 43, 61,..      i mod 18 = 7
        37        3, 9, 15, 21,...        i mod 6 = 3
        43        16, 37, 58,...          i mod 21 = 16

so if we filter those indexes which meet those conditions we'll avoid testing a whole lot of the generated numbers, namely:

        - without filtering indexes by mods:  it checks 483 nums. in 16 sec.
        - filtering by the mod 6's:           it checks 241 nums. in  8 sec..
        - filtering also by the other mods:   it checks 190 nums. in  6 sec.

This is the optimized routine which implements filtering by the above mod's and finds the answer in just 6 seconds (a modern pc would run this in less than a second):

        1   word -540:point -2:N=40:I%=1:clr time
        2   inc I%:N=N*10+3:M%=I%@6:if M%=2 or M%=3 or M%=5 then 2
        3   if I%@16=7 then 2 else if I%@18=7 then 2 else if I%@21=16 then 2
        4   if fnPrim(N) print time;len(str(N))-1;N," prime":end else 2

        run

        0:00:06   485 40333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333333333333333333333333333333333333333333333333333333333333333
        33333333333333333333 prime

An examination of a list longer than 79 elements would surely allow us to detect more mod patterns and reduce the number of checks even further but probably not very much so, diminishing returns and all that.

Nice mini-challenge, Joe, thanks for it.

Regards.
V.