274 자리

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

이 작업을 수행하는 데 약 20 시간의 CPU 시간이 있었고, 소수는 약 2 분이 걸렸습니다. 반면 84 자리 솔루션은 약 3 분 안에 찾을 수 있습니다.

84 자리

444444444444444444444444444444444444444444444444441111111113333333333333333333333333

77777777999999999999999777777777 (32 자리)
66666666666666622222222222222333 (32 자리)
647777777777777777777777777 (27 자리)
44444441333333333333 (20 자리)
999996677777777777 (18 자리)
167777777777777 (15 자리)

우선 순위 를 확인하려면이 도구를 사용하는 것이 좋습니다. D. Alpern의 ECM 애플릿

또한 큰 숫자를 찾을 가능성이 가장 높은 repdigit 방식을 사용합니다. 다음 스크립트는 알고리즘 적으로 대부분의 숫자 또는 잘림을 건너 뛰고 2, 3, 5 및 이제 11 c / o PeterTaylor의 배수가됩니다 (그 기여는 효율성을 약 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.pyhttp://codepad.org/KtXsydxK 에서 찾을 수 있습니다 .
또는 GMPY Projectgmpy.is_prime 함수를 사용할 수도 있습니다.

프로파일 링 결과 약간의 속도 향상. 네 후보의 가장 긴의 소수성 검사가 마지막으로 이동 한 xrange을 대체 range하고 long대체합니다는 int캐스트를 입력합니다. int평가 된식이 결과 인 경우 불필요한 오버 헤드가있는 것 같습니다 long.

분할 규칙

N을 a … ab … bc … c 형식의 postitive integer라고 하자 . 여기서 a , b 및 c 는 반복되는 숫자이다.

(2) (5)
-에 의하여 정제 피하기 위해 2 와 5 , C는 설정 될 수 없다 [0, 2, 4, 5, 6, 8] . 또한 b 가이 세트의 멤버 이면 c 의 길이는 2 이상일 수 있습니다.

3
– N = 1 (mod 3) 이면 N 을 [1, 4, 7]을 포함 할 수 없습니다. 이들 중 하나를 제거하면 3 의 배수가 됩니다. 마찬가지로 N = 2 (mod 3) 및 [2, 5, 8]에서도 마찬가지입니다 . 이 구현은 약간 약화 된 형태를 사용합니다. 만약 N 이 [1, 4, 7] 중 하나를 포함하면 [2, 5, 8] 중 어느 것도 포함하지 않을 수 있으며 그 반대도 마찬가지입니다. 또한, N 은 [0, 3, 6, 9] 로만 구성 될 수 없습니다 . 이것은 대체로 동등한 진술이지만 일부 사소한 경우 (예 : a , b 및 c)를 허용합니다각각 3 번의 배수로 반복된다 .

(11)
-로 PeterTaylor의 경우 노트, N은 양식입니다 AABBCC … xxyyzz ,이 숫자가 짝수 회 반복 만 구성입니다, 그것은에 의해 하찮게 나눌 수 11 : a0b0c … x0y0z . 이 관찰은 검색 공간의 절반을 제거합니다. 경우 N은 홀수 길이의 그 길이이다 , B 및 C를 모든 웰 (75 % 검색 공간의 감소) 홀수이어야하며, 만약 N이 후, 심지어 길이의 하나 , B 또는 C는 심지어 수있다 길이 (검색 공간 25 % 감소)
– 추측
다음의 경우 ABC가 의 배수 인 11 , 예를 들면, 407는 , 다음의 홀수 반복 , B 및 C는 또한 배수 될 것이다 (11) . 이것은 11 규칙에 의한 위의 분할 범위에서 벗어난다 . 실제로, 명백하게 허용되는 것 중에서 홀수 반복 만이있다. 이에 대한 증거는 없지만 체계적인 테스트를 통해 반례를 찾을 수 없습니다. 비교 : 444077777 , 44444000777 , 44444440000077777777777 등. 누구나이 추측을 증명하거나 반증 할 수 있습니다. 이후 aditsu 는 이것이 올바른 것으로 입증되었습니다.

다른 형태

2 자리의 반복 된 숫자 randomra 가 추구
한 형식의 숫자 인 a … ab … b 는 훨씬 더 드문 것 같습니다. 10 ¹⁷⁰⁰ 보다 작은 7 개의 해가 있으며 , 그 중 최대 길이는 12 자리입니다.

반복 자릿수 4 세트이
형식의 숫자 a … ab … bc … cd … d 는 내가 검색 한 것보다 더 조밀하게 분포 된 것으로 보입니다. 3 자리의 반복 된 자릿수를 사용하는 32 ^개 에 비해 10 ¹⁰⁰ 미만의 69 개의 ​​해가 있습니다 . 10 ¹¹ 에서 10 ¹⁰⁰ 사이의 값은 다음과 같습니다.

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

왜 그런지에 대한 간단한 휴리스틱 논쟁이 있습니다. 각각의 디지털 길이에 대해, 예상되는 솔루션 수가 가장 많은 다수의 반복 세트 (즉, 3 개의 반복 세트 또는 4 개의 반복 세트 등)가 존재한다. 전환으로 발생하는 추가 가능한 솔루션의 수가 검사 할 추가 숫자가 소수 일 가능성을 초과 할 때 전환이 발생합니다. 확인할 가능성의 기하 급수적 특성과 소수 분포의 로그 특성을 고려할 때 이는 비교적 빠르게 발생합니다.

예를 들어 300 자리 솔루션을 찾으려면 반복되는 4 자리 숫자를 확인하면 3 세트보다 솔루션이 생성 될 가능성이 훨씬 높고 5 세트는 여전히 가능성이 높습니다. 그러나 내가 사용할 수있는 컴퓨팅 능력으로 인해 4 세트로 100 자리보다 훨씬 큰 솔루션을 찾는 것은 5 또는 6은 물론 내 용량을 벗어난 것입니다.

답변

a=.>,{,~<>:i.100
b=.>,{,~<i.10
num=.".@(1&":)@#~
p=.(*/"1@:((1&p:)@num) (]-"1(0,=@i.@#)))"1 1
]res=./:~~.,b (p#num)"1 1/ a

   ops=: 'title ','Estimated number of solutions by digits',';xcaption ','digits',';ycaption ','log10 #'
   ops plot 10^.((%^.)%(2&(%~)@^.@(%&10))^(10&^.))(10&^(2+i.100))

function isPrime(n){
    return n==2||(n>1&&n%2!=0&&(function(){
        for(var i=3,max=Math.sqrt(n);i<=max;i+=2)if(n%i==0)return false;
        return true;
    })());
};

var o=$("#o"), m=Math.pow(2,53),S=$("#s");

(function loop(n){
    var s = n.toString(),t,p=true,i=l=s.length,h={};
    if(isPrime(n)){
        while(--i){
            t=s.substring(0,i-1) + s.substring(i,l); // cut out a digit
            if(!h[t]){   // keep a hash of numbers tested so we don't end up testing
                h[t]=1;  // the same number multiple times
                if(!isPrime(+t)){p=false;break;}
            }
        }
        if(p)
            o.append($("<span>"+n+"</span>"));
    }
    S.text(n);
    if(n+2 < m)setTimeout(function(){
        loop(n+2);
    },1);
})(99444901133);

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (6/7) * 6^k * (1 - (k + 1) / 2^k) / 3

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (2/7) * 6^k * (1 - (k + 1) / 2^k)

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (2/7) * 6^k * (1 - (k + 1) / 2^k) * (1.6286 / m)^(k + 1)

(1 - (1.5k - 2) / m)^(k - 1) / (k - 1)! * 0.465 * 9.772^k * (1 - (k + 1) / 2^k) / m^2

k = 2: 11.1 * (1 - 1/m) / m^2
k = 3: 108 * (1 - 2.5/m)^2 / m^2
k = 4: 486 * (1 - 4/m)^3 / m^2


k = 10: 10,065 * (1 - 13/m)^9 / m^2