Znajdź największą liczbę pierwszą, która wciąż jest liczbą pierwszą po usunięciu cyfr

Powyżej na /math/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-to zadaje się następujące pytanie. Ile jest liczb pierwszych, które pozostają pierwsze po usunięciu jednej z jej cyfr? Na przykład 719jest taka pierwsza, jak masz 71, 19i 79. Chociaż to pytanie pozostaje nierozwiązane, pomyślałem, że będzie to miłe wyzwanie w kodowaniu.

Zadanie. Podaj największą liczbę pierwszą, jaką możesz znaleźć, która pozostaje liczbą pierwszą po usunięciu którejkolwiek z jej cyfr. Powinieneś także podać kod, który go znajdzie.

Wynik. Wartość liczby pierwszej, którą dajesz.

Możesz używać dowolnego języka programowania i bibliotek, pod warunkiem, że są one bezpłatne.

Na początek 99444901133jest to największa podana na połączonej stronie.

Limit czasu. Przyjmę największą poprawną odpowiedź podaną dokładnie tydzień po pierwszej poprawnej odpowiedzi, większą niż 99444901133podana w odpowiedzi.

Dotychczasowe wyniki.

Python (primo)

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

J (randomra) (Ta odpowiedź uruchomiła programator tygodniowy 21 lutego 2013 r.)

222223333333

274 cyfry

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

Znalezienie zajęło około 20 godzin czasu procesora i około 2 minut na liczbę pierwszą. Natomiast 84-cyfrowe rozwiązanie można znaleźć w około 3 minuty.

84 cyfry

444444444444444444444444444444444444444444444444441111111113333333333333333333333333

77777777999999999999999777777777 (32 cyfr)
66666666666666622222222222222333 (32 cyfr)
647777777777777777777777777 (27 cyfr)
44444441333333333333 (20 cyfr)
999996677777777777 (18 cyfr)
167777777777777 (15) cyfry

Polecam to narzędzie, jeśli chcesz potwierdzić pierwotność: aplet ECM D. Alpern

Również stosując podejście repdigit, które wydaje się być podejściem, które najprawdopodobniej znajdzie duże wartości. Poniższy skrypt algorytm pomija większość numerów lub obcięcia, które prowadzą do wielokrotności 2, 3, 5 i obecnie 11 c / o PeterTaylor (jego wkład wzrost wydajności o około 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.pymożna znaleźć tutaj: http://codepad.org/KtXsydxK
Alternatywnie możesz również użyć gmpy.is_primefunkcji: Projekt GMPY

Niektóre niewielkie ulepszenia prędkości wynikające z profilowania. Kontrola pierwotności najdłuższego z czterech kandydatów została przeniesiona na koniec, xrangezastępuje rangei longzastępuje intrzutowania typu. intwydaje się mieć niepotrzebny narzut, jeśli ocenione wyrażenie daje w wynikulong .

Zasady podzielności

Niech N będzie dodatnią liczbą całkowitą w postaci a ... ab ... bc ... c , gdzie a , b i c są powtarzającymi się cyframi.

Przez 2 i 5
- Aby uniknąć podzielności przez 2 i 5 , c może nie być w zestawie [0, 2, 4, 5, 6, 8] . Dodatkowo, jeśli b jest członkiem tego zestawu, długość c może być nie mniejsza niż 2.

O 3
- Jeśli N = 1 (mod 3) , wówczas N może nie zawierać żadnego z [1, 4, 7] , ponieważ usunięcie któregokolwiek z nich w trywialny sposób dałoby wielokrotność 3 . Podobnie dla N = 2 (mod 3) i [2, 5, 8] . W tej implementacji zastosowano nieco osłabioną formę: jeśli N zawiera jeden z [1, 4, 7] , może nie zawierać żadnego z [2, 5, 8] i odwrotnie. Ponadto N może nie składać się wyłącznie z [0, 3, 6, 9] . Jest to w dużej mierze równoważne stwierdzenie, ale pozwala na pewne trywialne przypadki, na przykład a , b i ckażdy powtórzony 3- krotnie.

Przez 11
- jak zauważa PeterTaylor , jeśli N ma postać aabbcc ... xxyyzz , to znaczy składa się tylko z cyfr powtórzonych parzystą liczbę razy, jest on trywialnie podzielny przez 11 : a0b0c ... x0y0z . Ta obserwacja eliminuje połowę przestrzeni wyszukiwania. Jeżeli N jest długością nieparzystą, wówczas długość , b i c , powinien być dziwne, jak również (75% zmniejszenie przestrzeni poszukiwań) i, jeżeli N jest o jednakowej długości, wówczas tylko jeden z , b i c mogą być również długości (zmniejszenie przestrzeni wyszukiwania o 25%). - Przypuszczenie
: jeśli abc jest wielokrotnością 11 , na przykład 407 , wówczas wszystkie nieparzyste powtórzenia a , b i c będą również wielokrotnościami 11 . Jest to poza zakresem powyższej podzielności według zasady 11 ; w rzeczywistości tylko nieparzyste powtórzenia należą do tych, które są wyraźnie dozwolone. Nie mam na to dowodów, ale systematyczne testy nie były w stanie znaleźć kontrprzykładu. Porównaj: 444077777 , 44444000777 , 44444440000077777777777 itd. Każdy może swobodnie udowodnić lub obalić to przypuszczenie. Od tego czasu aditsu wykazało, że jest to poprawne.

Inne formy

2 zestawy powtarzających się cyfr
Liczby postaci, którą dążyła randomra , a ... ab ... b , wydają się znacznie rzadsze. Istnieje tylko 7 rozwiązań mniejszych niż 10 ¹⁷⁰⁰ , z których największe ma 12 cyfr.

4 zestawy powtarzających się cyfr
Numery tego formularza, a ... ab ... bc ... cd ... d , wydają się być bardziej gęsto rozmieszczone niż te, których szukałem. Istnieje 69 rozwiązań mniej niż 10 ¹⁰⁰ , w porównaniu do 32 przy użyciu 3 zestawów powtarzających się cyfr. Wartości między 10 ¹¹ a 10 ¹⁰⁰ są następujące:

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

Istnieje prosty heurystyczny argument, dlaczego tak powinno być. Dla każdej długości cyfrowej istnieje szereg powtarzanych zestawów (tj. 3 powtarzane zestawy lub 4 powtarzane zestawy itp.), Dla których oczekiwana liczba rozwiązań będzie najwyższa. Przejście ma miejsce, gdy liczba dodatkowych możliwych rozwiązań, wzięta za stosunek, przewyższa prawdopodobieństwo, że dodatkowa liczba do sprawdzenia jest liczbą pierwszą. Biorąc pod uwagę wykładniczy charakter możliwości sprawdzania i logarytmiczny charakter rozkładu liczb pierwszych, dzieje się to stosunkowo szybko.

Jeśli na przykład chcielibyśmy znaleźć rozwiązanie 300-cyfrowe, sprawdzenie 4 zestawów powtarzających się cyfr byłoby znacznie bardziej prawdopodobne, aby uzyskać rozwiązanie niż 3 zestawy, a 5 zestawów byłoby jeszcze bardziej prawdopodobne. Jednak przy mocy obliczeniowej, którą mam do dyspozycji, znalezienie rozwiązania znacznie większego niż 100 cyfr z 4 zestawami byłoby poza moim zasięgiem, nie mówiąc już o 5 lub 6.

222223333333 (12 cyfr)

Tutaj przeszukałem tylko format aa..aabb..bb do 100 cyfr. Tylko inne trafienia to 23 37 53 73 113 311.

Kod J (oczyszczony) (przepraszam, brak wyjaśnień):

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

Edycja: Ktoś już zrobił głębszą analizę niż ja tutaj.

Nie rozwiązanie, ale przybliżone oszacowanie liczby n-cyfrowych rozwiązań.

Generowanie kodu J.

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

JavaScript (Brute Force)

Nie znalazł jeszcze większej liczby

http://jsfiddle.net/79FDr/4/

Bez biblioteki bigint JavaScript jest ograniczony do liczb całkowitych <= 2^53 .

Ponieważ jest to Javascript, przeglądarka będzie narzekać, jeśli nie zwolnimy wątku wykonania interfejsu użytkownika do aktualizacji, dlatego postanowiłem śledzić, gdzie algorytm postępuje w interfejsie użytkownika.

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);

Link do analizy problemu został opublikowany, ale myślałem, że brakuje kilku rzeczy. Spójrzmy na liczby m cyfr, składające się z k sekwencji 1 lub więcej identycznych cyfr. Wykazano, że jeśli podzielimy cyfry na grupy {0, 3, 6, 9}, {1, 4, 7} i {2, 5, 8}, rozwiązanie nie może zawierać cyfr z drugiej i trzeciej grupy , i musi zawierać 3n + 2 cyfry z jednej z tych grup. Co najmniej dwie z k sekwencji muszą mieć nieparzystą liczbę cyfr. Spośród cyfr {1, 4, 7} tylko 1 i 7 mogą być najniższą cyfrą. Żaden z {2, 5, 8} nie może być najniższą cyfrą. Istnieją więc cztery (1, 3, 7, 9) lub dwie (3, 9) opcje dla najniższej cyfry,

Ilu jest kandydatów? Mamy m cyfr podzielonych na k sekwencji o długości co najmniej 1 cyfry. Istnieją (m - k + 1) ponad (k - 1) sposoby wyboru długości tych sekwencji, czyli około (m - 1,5k + 2) ^ (k - 1) / (k - 1) !. Dostępne są 2 lub 4 opcje dla najniższej cyfry, w sumie sześć. Dla pozostałych cyfr jest sześć opcji, z wyjątkiem 36/7 dla najwyższej cyfry; suma wynosi (6/7) * 6 ^ k. Istnieją dwa sposoby wyboru, czy długość sekwencji jest parzysta czy nieparzysta; k + 1 z nich jest wykluczonych, ponieważ żaden lub tylko jeden nie jest nieparzysty; pomnożymy liczbę wyborów przez (1 - (k + 1) / 2 ^ k), czyli 1/4, gdy k = 2, 1/2, gdy k = 3, 11/16, gdy k = 4 itd. Liczba cyfr z zestawu {1, 4, 7} lub {2, 5, 8} musi wynosić 3n + 2, więc liczba opcji jest podzielona przez 3.

Mnożąc wszystkie te liczby, liczba kandydatów wynosi

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

lub

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

Sam kandydat i liczby k utworzone przez usunięcie cyfry muszą być liczbami pierwszymi. Prawdopodobieństwo, że losowa liczba całkowita wokół N jest liczbą pierwszą, wynosi około 1 / ln N. Prawdopodobieństwo losowej liczby m wynosi około 1 / (mnn 10). Jednak liczby tutaj nie są losowe. Wszystkie zostały wybrane jako niepodzielne przez 2, 3 lub 5. 8 z dowolnych 30 kolejnych liczb całkowitych nie jest podzielnych przez 2, 3 lub 5. Dlatego prawdopodobieństwo bycia liczbą pierwszą wynosi (30/8) / (w 10) lub około 1,6286 / m.

Oczekiwana liczba rozwiązań to około

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

lub dla dużych m około

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

Dla k = 2, 3, 4, ... otrzymujemy:

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

Począwszy od k = 10 liczba znów się zmniejsza.