Mini-challenge: First Prime of form 403333...
11-15-2016, 08:50 AM (This post was last modified: 11-15-2016 11:50 AM by Thomas Ritschel.)
Post: #15
 Thomas Ritschel Member Posts: 66 Joined: Feb 2014
RE: Mini-challenge: First Prime of form 403333...
(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
 « Next Oldest | Next Newest »

 Messages In This Thread Mini-challenge: First Prime of form 403333... - Joe Horn - 10-27-2016, 02:17 PM RE: Mini-challenge: First Prime of form 403333... - Jim Horn - 10-27-2016, 07:57 PM RE: Mini-challenge: First Prime of form 403333... - Gerson W. Barbosa - 10-28-2016, 01:29 AM RE: Mini-challenge: First Prime of form 403333... - Jim Horn - 10-27-2016, 08:02 PM RE: Mini-challenge: First Prime of form 403333... - Joe Horn - 10-28-2016, 03:24 AM RE: Mini-challenge: First Prime of form 403333... - Jim Horn - 10-28-2016, 05:59 PM RE: Mini-challenge: First Prime of form 403333... - Thomas Ritschel - 11-02-2016, 07:44 AM RE: Mini-challenge: First Prime of form 403333... - Jim Horn - 10-28-2016, 04:08 PM RE: Mini-challenge: First Prime of form 403333... - Thomas Ritschel - 11-07-2016, 12:49 PM RE: Mini-challenge: First Prime of form 403333... - Ron Ross - 10-28-2016, 05:38 PM RE: Mini-challenge: First Prime of form 403333... - Csaba Tizedes - 11-02-2016, 09:26 AM RE: Mini-challenge: First Prime of form 403333... - Valentin Albillo - 11-14-2016, 01:20 AM RE: Mini-challenge: First Prime of form 403333... - Thomas Ritschel - 11-14-2016, 09:02 AM RE: Mini-challenge: First Prime of form 403333... - Valentin Albillo - 11-14-2016, 08:20 PM RE: Mini-challenge: First Prime of form 403333... - Thomas Ritschel - 11-15-2016 08:50 AM RE: Mini-challenge: First Prime of form 403333... - Valentin Albillo - 11-16-2016, 12:41 AM RE: Mini-challenge: First Prime of form 403333... - Alberto Candel - 11-17-2016, 09:34 PM

User(s) browsing this thread: 1 Guest(s)