274 digits
4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111
This took about 20 hours of CPU time to find, and about 2 minutes per prime to prove. In contrast, the 84 digit solution can be found in around 3 minutes.
84 digits
444444444444444444444444444444444444444444444444441111111113333333333333333333333333
77777777999999999999999777777777 (32 digits)
66666666666666622222222222222333 (32 digits)
647777777777777777777777777 (27 digits)
44444441333333333333 (20 digits)
999996677777777777 (18 digits)
167777777777777 (15 digits)
I recommend this tool if you want to confirm primality: D. Alpern's ECM Applet
Also using a repdigit approach, which seems to be the approach most likely to find large values. The following script algorithmically skips over most numbers or truncations which will result in multiples of 2, 3, 5 and now 11 c/o PeterTaylor (his contribution increased the efficiency by approximately 50%).
from my_math import is_prime
sets = [
(set('147'), set('0147369'), set('1379')),
(set('369'), set('147'), set('1379')),
(set('369'), set('0369'), set('17')),
(set('258'), set('0258369'), set('39')),
(set('369'), set('258'), set('39'))]
div2or5 = set('024568')
for n in range(3, 100):
for sa, sb, sc in sets:
for a in sa:
for b in sb-set([a]):
bm1 = int(b in div2or5)
for c in sc-set([b]):
if int(a+b+c)%11 == 0: continue
for na in xrange(1, n-1, 1+(n&1)):
eb = n - na
for nb in xrange(1, eb-bm1, 1+(~eb&1)):
nc = eb - nb
if not is_prime(long(a*(na-1) + b*nb + c*nc)):
continue
if not is_prime(long(a*na + b*(nb-1) + c*nc)):
continue
if not is_prime(long(a*na + b*nb + c*(nc-1))):
continue
if not is_prime(long(a*na + b*nb + c*nc)):
continue
print a*na + b*nb + c*nc
my_math.py
can be found here: http://codepad.org/KtXsydxK
Alternatively, you could also use the gmpy.is_prime
function: GMPY Project
Some small speed improvements as a result of profiling. The primality check for the longest of the four candidates has been moved to the end, xrange
replaces range
, and long
replaces int
type casts. int
seems to have unnecessary overhead if the evaluated expression results in a long
.
Divisibility Rules
Let N be a postitive integer of the form a...ab...bc...c, where a, b and c are repeated digits.
By 2 and 5
- To avoid divisibility by 2 and 5, c may not be in the set [0, 2, 4, 5, 6, 8]. Additionally, if b is a member of this set, the length of c may be no less than 2.
By 3
- If N = 1 (mod 3), then N may not contain any of [1, 4, 7], as removing any of these would trivially result in a multiple of 3. Likewise for N = 2 (mod 3) and [2, 5, 8]. This implementation uses a slightly weakened form of this: if N contains one of [1, 4, 7], it may not contain any of [2, 5, 8], and vice versa. Additionally, N may not consist solely of [0, 3, 6, 9]. This is largely an equivalent statement, but it does allow for some trivial cases, for example a, b, and c each being repeated a multiple of 3 times.
By 11
- As PeterTaylor notes, if N is of the form aabbcc...xxyyzz, that is it consists only of digits repeated an even number of times, it is trivially divisible by 11: a0b0c...x0y0z. This observation eliminates half of the search space. If N is of odd length, then the length of a, b and c must all be odd as well (75% search space reduction), and if N is of even length, then only one of a, b or c may be even in length (25% search space reduction).
- Conjecture: if abc is a multiple of 11, for example 407, then all odd repetitions of a, b and c will also be multiples of 11. This falls out of the scope of the above divisibility by 11 rule; in fact, only odd repetitions are among those which are explicitly allowed. I don't have a proof for this, but systematic testing was unable to find a counter-example. Compare: 444077777, 44444000777, 44444440000077777777777, etc. Anyone may feel free to prove or disprove this conjecture. aditsu has since demonstrated this to be correct.
Other Forms
2 sets of repeated digits
Numbers of the form that randomra was pursuing, a...ab...b, seem to be much more rare. There are only 7 solutions less than 101700, the largest of which is 12 digits in length.
4 sets of repeated digits
Numbers of this form, a...ab...bc...cd...d, appear to be more densely distributed than those I was searching for. There are 69 solutions less than 10100, compared to the 32 using 3 sets of repeated digits. Those between 1011 and 10100 are as follows:
190000007777
700000011119
955666663333
47444444441111
66666622222399
280000000033333
1111333333334999
1111333333377779
1199999999900111
3355555666999999
2222233333000099
55555922222222233333
444444440004449999999
3366666633333333377777
3333333333999888883333
4441111113333333333311111
2222222293333333333333999999
999999999339999999977777777777
22222226666666222222222299999999
333333333333333333339944444444444999999999
559999999999933333333333339999999999999999
3333333333333333333111111111111666666666611111
11111111333330000000000000111111111111111111111
777777777770000000000000000000033333339999999999999999999999999
3333333333333333333333333333333333333333333333336666666977777777777777
666666666666666666611111113333337777777777777777777777777777777777777777
3333333333333333333888889999999999999999999999999999999999999999999999999933333333
There's a simple heuristic argument as to why this should be the case. For each digital length, there is a number of repeated sets (i.e. 3 repeated sets, or 4 repeated sets, etc.) for which the expected number of solutions will be the highest. The transition occurs when the number of additional possible solutions, taken as a ratio, outweighs the probability that the additional number to be checked is prime. Given the exponential nature of the possibilities to check, and the logarithmic nature of prime number distribution, this happens relatively quickly.
If, for example, we wanted to find a 300 digit solution, checking 4 sets of repeated digits would be far more likely to produce a solution than 3 sets, and 5 sets would be more likely still. However, with the computing power that I have at my disposal, finding a solution much larger than 100 digits with 4 sets would be outside of my capacity, let alone 5 or 6.
9901444133
(a deletion of one 9) isn't prime (7 x 1414492019
). Your previous example was correct, though. \$\endgroup\$