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

[Thomas Ritschel]

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.