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.
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)):
if not is_prime(long(a*na + b*(nb-1) + c*nc)):
if not is_prime(long(a*na + b*nb + c*(nc-1))):
if not is_prime(long(a*na + b*nb + c*nc)):
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,
int type casts.
int seems to have unnecessary overhead if the evaluated expression results in a
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.
- 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.
- 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.
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:
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.