Mini-challenge: First Prime of form 403333...

[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