Threaded Mode | Linear Mode

Joe Horn · (This post was last modified: 10-27-2016 02:24 PM by Joe Horn.)

Here's a mini-challenge for programmers who enjoy playing with numbers.

Imagine this sequence of integers: {403, 4033, 40333, 403333, ...}. Each term of the sequence is 10 times the previous term +3.

It is not immediately obvious, but not all the terms of this sequence are composite. There are in fact an infinite number of primes in this sequence. However, the smallest one is surprisingly large.

Mini-challenge: Find the smallest prime term in this sequence.

Warning #1: Checking OEIS won't help; it's not there.

Warning #2: Patience may be required, depending on your choice of programming language and hardware.

Jim Horn · 10-27-2016, 07:57 PM

Well, my WP 34S quickly ran through the 19 digit value before overflowing. My '50g is at home and I'm at work.

What's left? I've got Mathematica 10 on my Surface Pro 3 in my work bag. Lessee:

x=403;
d=3;
While[
!PrimeQ[x],
x=10x+3;
d++
];
Print[d];
Print[x];

That ran in under a second with 'd' being sizeable (and the printout of 'x' being more so). I won't spoil the fun with the actual values, though.

Thank you, Joe! How you done it?

(Unrelated note: Bob Hoover, RIP)

Jim Horn · 10-27-2016, 08:02 PM

Hmmm - fun enough to go farther. Next prime is nearly 3x the size. The one after that? The Surface Pro 3 is still chugging...

Gerson W. Barbosa · 10-28-2016, 01:29 AM

(10-27-2016 07:57 PM)Jim Horn Wrote: My '50g is at home and I'm at work.

Whew!!! Too good it was at home! It would have taken it some three or four days if my estimation is correct.

« 40
DO 10 * 3 + DUP
UNTIL ISPRIME?
END
»

EVAL

403333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
333333333333333333333333333
33333333333333333333333333

Joe Horn · 10-28-2016, 03:24 AM

Congrats, Jim & Gerson!

If that was too easy, this one is more difficult: 4103333.... Big Grin

Jim Horn · 10-28-2016, 04:08 PM

Aww, Joe, you printed the first one (485 digits) but not the second (1367 digits). I stopped Mathematica after about 6 hours at 7067 digits so any third prime would be at least that large.

Ron Ross · 10-28-2016, 05:38 PM

"It is not immediately obvious, but not all the terms of this sequence are composite. There are in fact an infinite number of primes in this sequence. However, the smallest one is surprisingly large." Quote of Joe Horn.
.
Just out of curiosity, how can you make this statement? Is this a countable sequence of sorts or of a type that you know will always produce one more prime? I am a novice so please, keep your explanation simple if possible.
.
If I remember correctly, the Mersenne Primes are of such rarity that they are yet to be determined to be infinite or not. Will your prime generator always produce, or will it come up empty at some extremely large value. Just ask'en.

Jim Horn · 10-28-2016, 05:59 PM

(10-28-2016 03:24 AM)Joe Horn Wrote: Congrats, Jim & Gerson!

If that was too easy, this one is more difficult: 4103333....

Yes, it is. I stopped Mathematica after a few hours at 8325 digits. Have you found one?

Thomas Ritschel · 11-02-2016, 07:44 AM

(10-28-2016 05:59 PM)Jim Horn Wrote:
(10-28-2016 03:24 AM)Joe Horn Wrote: Congrats, Jim & Gerson!

If that was too easy, this one is more difficult: 4103333....

Yes, it is. I stopped Mathematica after a few hours at 8325 digits. Have you found one?

The first prime that starts with 410333... has 37401 digits.
Found using PFGW by testing the equivalent sequence (1231*10^n-1)/3.

Both sequences have been tested to at least 50000 digits so far, but no other primes found.

Csaba Tizedes · 11-02-2016, 09:26 AM

OK, so I have no chance on my CASIO fx-50F... (6 register + 1 memory (M) + 29 program steps - and yes, the speed is approx. 21 steps / 1 second) Smile

Csaba

Thomas Ritschel · 11-07-2016, 12:49 PM

(10-28-2016 04:08 PM)Jim Horn Wrote: Aww, Joe, you printed the first one (485 digits) but not the second (1367 digits). I stopped Mathematica after about 6 hours at 7067 digits so any third prime would be at least that large.

The third prime of that sequence (403333...) has 137585 digits! Again found using PFGW.

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.

Thomas Ritschel · 11-14-2016, 09:02 AM

Hi Valentin,

Thanks for the detailed analysis!

One could further reduce the number of candidates by using the fact that every second number of the sequence 403333... (those with an even number of digits) has algebraic factors:

Code:

      4033 =    109 * 37    

    403333 =   1099 * 367   = (7*157) * (367)

  40333333 =  10999 * 3667  = (17*647) * (19*193)

4033333333 = 109999 * 36667 = (317*347) * (37*991)

There is obviously a pattern in the factors.

It becomes more clear if we multiply the above equations by 3:

Code:

      4033 * 3 =    109 * 111    = 109 * (3*37)

    403333 * 3 =   1099 * 1101   = (7*157) * (3*367)

  40333333 * 3 =  10999 * 11001  = (17*647) * (3*19*193)

4033333333 * 3 = 109999 * 110001 = (317*347) * (3*37*991)

The numbers at the left are of the type 121*10^n-1. Since 121=11^2, numbers with even exponent will split into two factors: 121*10^(2n)-1 = (11*10^n-1)*(11*10^n+1).

Thus, in general, one can skip the even exponents; in your case the odd indices. Together with the "mod 6" congruences this reduces to testing only the case index = 4 mod 6.

Valentin Albillo · 11-14-2016, 08:20 PM

Hi, Thomas:

(11-14-2016 09:02 AM)Thomas Ritschel Wrote: Thanks for the detailed analysis!

You're welcome, but I wouldn't call my post an analysis, more like a few observations I made on the go while solving the challenge.

Quote:[...]every second number of the sequence 403333... (those with an even number of digits) has algebraic factors:

           4033 = 109 * 37
        403333 = 1099 * 367 = (7*157) * (367)
        40333333 = 10999 * 3667 = (17*647) * (19*193)
        4033333333 = 109999 * 36667 = (317*347) * (37*991)

There is obviously a pattern in the factors.

Interesting. Did you notice this pattern yourself or did you read about it someplace ? In that case, I would appreciate a link to it.

Quote:Thus, in general, one can skip the even exponents; in your case the odd indices. Together with the "mod 6" congruences this reduces to testing only the case index = 4 mod 6.

Great. This way, instead of having to check 483 candidates, only about 60-70 will need to be checked out, an 800% speed up.

Thanks a lot for posting those really interesting facts, a real textbook example of how a little analysis can do much better than relying in just pure brute force.

Regards.
V.

Thomas Ritschel · (This post was last modified: 11-15-2016 11:50 AM by Thomas Ritschel.)

(11-14-2016 08:20 PM)Valentin Albillo Wrote:

Quote:[...]every second number of the sequence 403333... (those with an even number of digits) has algebraic factors:

           4033 = 109 * 37
        403333 = 1099 * 367 = (7*157) * (367)
        40333333 = 10999 * 3667 = (17*647) * (19*193)
        4033333333 = 109999 * 36667 = (317*347) * (37*991)

There is obviously a pattern in the factors.

Interesting. Did you notice this pattern yourself or did you read about it someplace ? In that case, I would appreciate a link to it.

Well, I found it by myself. But I'm somewhat "preoccupied" since I spend much of my spare time on prime numbers and factorizations.

The above factorization becomes quite natural if you look at the so called rep-digit numbers, for example:

Code:

(10^n-1)   = 999999...

(10^n-1)/3 = 333333...

(10^n-1)/9 = 111111...

For even exponents (e.g. n = 2m) the numbers can be algebraically factorized: 10^(2m)-1 = (10^m-1)*(10^m+1), e.q. equivalent to the factorization of the polynomial (x^2-1) = (x+1)*(x-1) :

Code:

10^6-1      =     999999 =   (10^3-1) * (10^3+1) =   999 *   1001

10^8-1      =   99999999 =   (10^4-1) * (10^4+1) =  9999 *  10001

10^10-1     = 9999999999 =   (10^5-1) * (10^5+1) = 99999 * 100001

(10^6-1)/3  =     333333 = (10^3-1)/3 * (10^3+1) =   333 *   1001

(10^8-1)/3  =   33333333 = (10^4-1)/3 * (10^4+1) =  3333 *  10001

(10^10-1)/3 = 3333333333 = (10^5-1)/3 * (10^5+1) = 33333 * 100001

(10^6-1)/9  =     111111 = (10^3-1)/9 * (10^3+1) =   111 *   1001

(10^8-1)/9  =   11111111 = (10^4-1)/9 * (10^4+1) =  1111 *  10001

(10^10-1)/9 = 1111111111 = (10^5-1)/9 * (10^5+1) = 11111 * 100001

Multiplying by some certain factors will be equivalent to prefixing the numbers by additional digits:

Code:

  (25*10^10-1)/3 =   83333333333

 (121*10^10-1)/3 =  403333333333

(1225*10^10-1)/3 = 4083333333333

(1231*10^10-1)/3 = 4103333333333

(1261*10^10-1)/3 = 4203333333333

(1261*10^10-1)/9 = 1401111111111

One would call such numbers near-repdigits.

If the multiplier itself is a square, then algebraic factorization is still possible:

Code:

  (25*10^10-1)/3 =  (5*10^5-1) * (5*10^5+1)/3  =  499999 *  166667

 (121*10^10-1)/3 = (11*10^5-1) * (11*10^5+1)/3 = 1099999 *  366667

(1225*10^10-1)/3 = (35*10^5-1) * (35*10^5+1)/3 = 3499999 * 1166667

This kind of algebraic factorization is not restricted to polynomials of 2nd degree. It can easily be extended to higher degrees, for example:

Code:

1331*10^3-1 = (11*10^1-1) * ((11*10^1)^2 + 11*10^1 + 1)

1331*10^6-1 = (11*10^2-1) * ((11*10^2)^2 + 11*10^2 + 1)

1331*10^9-1 = (11*10^3-1) * ((11*10^3)^2 + 11*10^3 + 1)

      1330999 =   109 *     12211

   1330999999 =  1099 *   1211101

1330999999999 = 10999 * 121011001

Here we have the polynomial (x^3-1) = (x-1)*(x^2+x+1), where x = 11*10^n.

Thus, in conclusion, I fully agree with you, Valentin: A little analysis can do much better than relying in just pure brute force!

Kind regards,
Thomas

Valentin Albillo · 11-16-2016, 12:41 AM

Hi again, Thomas:

(11-15-2016 08:50 AM)Thomas Ritschel Wrote: Well, I found it by myself. But I'm somewhat "preoccupied" since I spend much of my spare time on prime numbers and factorizations.

Great finding and don't worry, you're not alone in that respect. I spend a lot of free time (~20% or so) with all things mathematical and HP-calc related. It's great fun.

Quote:The above factorization becomes quite natural if you look at the so called rep-digit numbers, for example: [...]

Thank you very much for your detailed, crystal-clear explanation, It's been a great read to me and I'm sure many other forum visitors will certainly enjoy it as well, thanks for taking the time to post it.

It's been my pleasure.

Regards.
V.

Alberto Candel · 11-17-2016, 09:34 PM

(10-27-2016 02:17 PM)Joe Horn Wrote: [...]
Imagine this sequence of integers: {403, 4033, 40333, 403333, ...}. [....]

There are in fact an infinite number of primes in this sequence.
[...].

I tried this but I couldn't. Any hints?