Mini-challenge: First Prime of form 403333... - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: Not HP Calculators (/forum-7.html) +--- Forum: Not remotely HP Calculators (/forum-9.html) +--- Thread: Mini-challenge: First Prime of form 403333... (/thread-7110.html) Mini-challenge: First Prime of form 403333... - Joe Horn - 10-27-2016 02:17 PM 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. RE: Mini-challenge: First Prime of form 403333... - 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) RE: Mini-challenge: First Prime of form 403333... - 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... RE: Mini-challenge: First Prime of form 403333... - 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 RE: Mini-challenge: First Prime of form 403333... - Joe Horn - 10-28-2016 03:24 AM Congrats, Jim & Gerson! If that was too easy, this one is more difficult: 4103333.... RE: Mini-challenge: First Prime of form 403333... - 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. RE: Mini-challenge: First Prime of form 403333... - 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. RE: Mini-challenge: First Prime of form 403333... - 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? RE: Mini-challenge: First Prime of form 403333... - 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. RE: Mini-challenge: First Prime of form 403333... - 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) Csaba RE: Mini-challenge: First Prime of form 403333... - 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. RE: Mini-challenge: First Prime of form 403333... - 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 40333333333333333333333333333333333333333333333333333333333333333333333333333333​3 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.   RE: Mini-challenge: First Prime of form 403333... - 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. RE: Mini-challenge: First Prime of form 403333... - 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.   RE: Mini-challenge: First Prime of form 403333... - Thomas Ritschel - 11-15-2016 08:50 AM (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 RE: Mini-challenge: First Prime of form 403333... - 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.   RE: Mini-challenge: First Prime of form 403333... - 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?