Zadanie polega na nznalezieniu najmniejszej liczby pierwszej, rozpoczynającej się od NAJMNIEJ n liczby 2na początku liczby. To sekwencja, którą znalazłem w OEIS ( A068103 ).

Pierwsze 17 liczb w sekwencji podano poniżej, jeśli chcesz więcej, będę musiał wdrożyć sekwencję, co nie mam nic przeciwko.

0  = 2
1  = 2
2  = 223
3  = 2221
4  = 22229
5  = 2222203
6  = 22222223                # Notice how 6 and 7 are the same! 
7  = 22222223                # It must be **AT LEAST** 6, but no more than necessary.
8  = 222222227
9  = 22222222223             # Notice how 9 and 10 are the same!
10 = 22222222223             # It must be **AT LEAST** 9, but no more than necessary.
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221

Pomyślałem, że byłoby to fajne połączenie manipulacji ciągiem, detekcji liczby pierwszej i sekwencji. To jest golf golfowy , najniższa liczba bajtów zostanie ogłoszona zwycięzcą prawdopodobnie pod koniec miesiąca.

Brachylog , 12 11 bajtów

:2rj:Acb#p=

Wypróbuj online!

To zaskakująco bezpośrednio przekłada się na Brachylog. Jest to funkcja, a nie pełny program (chociaż podanie interpretera Zjako argumentu wiersza poleceń powoduje, że dodaje on odpowiednie opakowanie, aby przekształcić funkcję w program; to właśnie zrobiłem, aby łącze TIO działało). Jest to również dość niefortunne, że jwydaje się być indeksowane -1 i wymaga korekty, aby to umożliwić.

Możesz uzasadnić argument, że =nie jest to konieczne, ale myślę, że biorąc pod uwagę sposób sformułowania problemu, jest on; bez, funkcja opisuje zbiór wszystkich liczb pierwszych, które zaczynają się od podanej liczby 2s, i bez jakiejś wyraźnej instrukcji, że program powinien zrobić coś z tym opisem (w tym przypadku generując pierwszą wartość), prawdopodobnie nie zgodne ze specyfikacją.

Wyjaśnienie

:2rjbAcb#p=
:2rj         2 repeated a number of times equal to the input plus one
    :Ac      with something appended to it
       b     minus the first element
        #p   is prime;
          =  figure out what the resulting values are and return them

Gdy jest używana jako funkcja zwracająca liczbę całkowitą, nic nigdy nie żąda wartości przekraczających pierwszą, więc pierwszą musimy się martwić.

Jedna subtelność (wskazana w komentarzach): :Acbi b:Acsą matematycznie równoważne (jak jedna usuwa się od początku, a druga dodaje do końca, a region pomiędzy nimi nigdy się nie nakłada); Wcześniej miałem b:Ac, co jest bardziej naturalne, ale psuje się na wejściu 0 (zgaduję, ponieważ codmawia połączenia pustej listy z czymkolwiek; wiele wbudowanych Brachylog z jakiegoś powodu ma tendencję do łamania się na pustych listach). :Acbzapewnia, że cnigdy nie musi widzieć pustej listy, co oznacza, że ​​przypadek wejścia 0 może teraz również działać.

Java (OpenJDK 8) , 164 110 bajtów

a->{int i=0;for(;!(i+"").matches("2{"+a+"}.*")|new String(new char[i]).matches(".?|(..+)\\1+");i++);return i;}

Dzięki @FryAmTheEggman za garść bajtów!

Wypróbuj online!

Pyth, 12 bajtów

f&!x`T*Q\2P_

W pseudokodzie:

f                key_of_first_truthy_value( lambda T:
  !                  not (
   x`T*Q\2               repr(T).index(input()*'2')
                     )
 &                   and
          P_T        is_prime(T)
                 )

Pętle lambdarozpoczynając od T=1, zwiększając o 1, aż warunek zostanie spełniony. Łańcuch 2s musi być podciągiem od początku łańcucha, tzn. Metoda indeksu musi zwrócić 0. Jeśli podciąg nie zostanie znaleziony, zwraca, -1co dogodnie jest również zgodne z prawdą, więc nie ma wyjątkowego przypadku.

Możesz spróbować online tutaj , ale serwer pozwala tylko na wejście 4.

Perl, 50 bajtów

49 bajtów kodu + -pflaga.

++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{

Podaj dane wejściowe bez końcowej nowej linii. Na przykład:

echo -n 4 | perl -pE '++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{'

To zajmuje chwilę, aby uruchomić liczby większe niż 4, ponieważ testuje każdą liczbę (są 2 testy: pierwszy /^2{$_}/sprawdza, czy na początku jest wystarczająca liczba 2, a drugi (1x$\)!~/^1?$|^(11+)\1+$/sprawdza pierwotność (z bardzo słabymi wynikami)).

Haskell, 73 bajty

f n=[x|x<-[2..],all((>0).mod x)[3..x-1],take n(show x)==([1..n]>>"2")]!!0

Przykład użycia: f 3-> 2221.

Brutalna siła. [1..n]>>"2"tworzy listę n 2s, która jest porównywana z pierwszymi nznakami w reprezentacji ciągu bieżącej liczby pierwszej.

Mathematica, 103 bajty

ReplaceRepeated[0,i_/;!IntegerDigits@i~MatchQ~{2~Repeated~{#},___}||!PrimeQ@i:>i+1,MaxIterations->∞]&

Nienazwana funkcja przyjmująca nieujemny argument liczby całkowitej #i zwracająca liczbę całkowitą. Dosłownie testuje kolejno wszystkie dodatnie liczby całkowite, aż znajdzie taki, który zaczyna się od #2s i jest liczbą pierwszą. Strasznie wolne dla wejść powyżej 5.

poprzedni wynik: Mathematica, 155 bajtów

Mathematica byłaby lepsza do gry w golfa, gdyby nie była tak mocno napisana; musimy jawnie przełączać się między typami liczb całkowitych / list / ciągów.

(d=FromDigits)[2&~Array~#~Join~{1}//.{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}//.{a__,b_,10,c___}->{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b})]/. 23->2&

Dziwnie, ten algorytm działa na listach cyfr , zaczynając od {2,...,2,1}. Dopóki nie są to cyfry liczby pierwszej, dodaje jedną cyfrę do ostatniej cyfry, korzystając z reguły {j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}... a następnie ręcznie implementuje przenoszenie jednej do następnej cyfry, o ile dowolna z cyfry równe 10, przy użyciu reguły {a__,b_,10,c___}->{a,b+1,0,c}... a następnie, jeśli zaszliśmy tak daleko, że ostatni z wiodących 2s zmienił się w a 3, zaczyna od nowa z kolejną cyfrą na końcu, używając reguły {a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}. Na /. 23->2końcu naprawiono specjalny przypadek, w którym dane wejściowe to 1: większość liczb pierwszych nie może się kończyć 2, ale 2może. (Kilka błędów jest wypluwanych na wejściach 0i 1, ale funkcja znajduje właściwą odpowiedź).

Ten algorytm jest dość szybki: na przykład na moim laptopie obliczenie, że pierwsza liczba pierwsza zaczyna się od 1000 2s, zajmuje mniej niż 3 sekundy 22...220521.

Pyth, 17 bajtów

f&q\2{<`T|Q1}TPTh

Wydaje się, że nie można rozwiązać tego w n = 4Internecie, ale teoretycznie jest to poprawne.

Wyjaśnienie

               Th    Starting from (input)+1, 
f                    find the first T so that
      <              the first
          Q          (input) characters
         | 1         or 1 character, if (input) == 0
       `T            of T's string representation
     {               with duplicates removed
  q\2                equal "2", 
 &                   and
            }T       T is found in
              PT     the list of T's prime factors.

Perl 6 , 53 bajtów

{($/=2 x$^n-1)~first {+($/~$_) .is-prime&&/^2/},0..*}

Spróbuj

Rozszerzony:

{
  ( $/ = 2 x $^n-1 )       # add n-1 '2's to the front (cache in ｢$/｣)
  ~
  first {
    +( $/ ~ $_ ) .is-prime # find the first that when combined with ｢$/｣ is prime
    &&
    /^2/                   # that starts with a 2 (the rest are in ｢$/｣)
  },
  0..*
}

Galaretka , 14 bajtów

D=2×\S:³aÆPµ1#

Bardzo nieefektywne. Wypróbuj online!

Pyke, 14 bajtów

.fj`Q\2*.^j_P&

Wypróbuj tutaj!

.fj            - first number (asj)
   `    .^     -   str(i).startswith(V)
    Q\2*       -    input*"2"
             & -  ^ & V
          j_P  -   is_prime(j)

12 bajtów po poprawce błędu i nowej funkcji

~p#`Q\2*.^)h

Wypróbuj tutaj!

~p           - all the primes
  #       )h - get the first where...
   `    .^   - str(i).startswith(V)
    Q\2*     -  input*"2"

Sage, 69 68 bajtów

lambda n:(x for x in Primes()if '2'*len(`x`)=>'2'*n==`x`[:n]).next()

Używa generatora do znalezienia pierwszego (a więc najmniejszego) z nieskończenie wielu terminów.

Japt, 20 bajtów

L²o@'2pU +Xs s1)nÃæj

Przetestuj online! Kończy się w ciągu dwóch sekund na moim komputerze dla wszystkich danych wejściowych do 14, a następnie naturalnie traci precyzję (JavaScript ma tylko całkowitą dokładność do 2 ⁵³ ).

Ogromne podziękowania dla @obarakon za pracę nad tym :-)

Wyjaśnienie

                       // Implicit: U = input integer, L = 100
L²o                    // Generate the range [0...100²).
   @             Ã     // Map each item X through the following function:
    '2pU               //   Take a string of U "2"s.
         +Xs s1)n      //   Append all but the first digit of X, and cast to a number.
                       // If U = 3, we now have the list [222, 222, ..., 2220, 2221, ..., 222999].
                  æ    // Take the first item that returns a truthy value when:
                   j   //   it is checked for primality.
                       // This returns the first prime in the forementioned list.
                       // Implicit: output result of last expression

W najnowszej wersji Japt może to być 12 bajtów:

_n j}b!+'2pU   // Implicit: U = input integer
_   }b         // Return the first non-negative bijective base-10 integer that returns
               // a truthy value when run through this function, but first,
      !+       //   prepend to each integer
        '2pU   //   a string of U '2's.
               // Now back to the filter function:
 n j           //   Cast to a number and check for primality.
               // Implicit: output result of last expression

Przetestuj online! Kończy się w ciągu pół sekundy na moim komputerze dla wszystkich danych wejściowych do 14.

PHP, 76 bajtów

for($h=str_pad(2,$i=$argv[1],2);$i>1;)for($i=$p=$h.++$n;$p%--$i;);echo$p?:2;

pobiera dane wejściowe z argumentu wiersza poleceń. Uruchom z -r.

awaria

for($h=str_pad(2,$i=$argv[1],2) # init $h to required head
    ;$i>1;                      # start loop if $p>2; continue while $p is not prime
)
    for($i=$p=$h.++$n               # 1. $p = next number starting with $h
                                    #    (first iteration: $p is even and >2 => no prime)
    ;$p%--$i;);                     # 2. loop until $i<$p and $p%$i==0 ($i=1 for primes)
echo$p?:2;                      # print result; `2` if $p is unset (= loop not started)

Bash (+ coreutils), 53 bajty

Działa do 2 ^ 63-1 (9223372036854775807) , zajmuje dużo czasu, aby zakończyć dla N> 8.

Grał w golfa

seq $[2**63-1]|factor|grep -Pom1 "^2{$1}.*(?=: \S*$)"

Test

>seq 0 7|xargs -L1 ./twist

2
2
223
2221
22229
2222203
22222223
22222223

Python 3, 406 bajtów

w=2,3,5,7,11,13,17,19,23,29,31,37,41
def p(n):
 for q in w:
  if n%q<1:return n==q
  if q*q>n:return 1
 m=n-1;s,d=-1,m
 while d%2==0:s,d=s+1,d//2
 for a in w:
  x=pow(a,d,n)
  if x in(1,m):continue
  for _ in range(s):
   x=x*x%n
   if x==1:return 0
   if x==m:break
  else:return 0
 return 1
def f(i):
 if i<2:return 2
 k=1
 while k:
  k*=10;l=int('2'*i)*k
  for n in range(l+1,l+k,2):
   if p(n):return n

kod testowy

for i in range(31):
    print('{:2} = {}'.format(i, f(i)))

wyjście testowe

 0 = 2
 1 = 2
 2 = 223
 3 = 2221
 4 = 22229
 5 = 2222203
 6 = 22222223
 7 = 22222223
 8 = 222222227
 9 = 22222222223
10 = 22222222223
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
17 = 222222222222222221
18 = 22222222222222222253
19 = 222222222222222222277
20 = 2222222222222222222239
21 = 22222222222222222222201
22 = 222222222222222222222283
23 = 2222222222222222222222237
24 = 22222222222222222222222219
25 = 222222222222222222222222239
26 = 2222222222222222222222222209
27 = 2222222222222222222222222227
28 = 222222222222222222222222222269
29 = 2222222222222222222222222222201
30 = 222222222222222222222222222222053

Zdecydowałem się na szybkość w dość dużym zakresie, zamiast wielkości bajtów. :) Używam deterministycznego testu pierwotności Millera-Rabina, który jest gwarantowany do 3317044064679887385961981 z tym zestawem świadków. Większe liczby pierwsze zawsze pomyślnie przejdą test, ale niektóre kompozyty mogą również przejść, chociaż prawdopodobieństwo jest bardzo niskie. Jednak przetestowałem również liczby wyjściowe dla i> 22 za pomocą programu Pecec i programu faktoryzacji krzywej eliptycznej i wydaje się, że są one pierwsze.

Python 3, 132 bajty

def f(x):
 k=10;p=2*(k**x//9)
 while x>1:
  for n in range(p*k,p*k+k):
   if all(n%q for q in range(2,n)):return n
  k*=10
 return 2

Wszelkie nadzieje na wydajność zostały poświęcone dla mniejszej liczby bajtów.

Java, 163 bajty

BigInteger f(int a){for(int x=1;x>0;x+=2){BigInteger b=new BigInteger(new String(new char[a]).replace("\0","2")+x);if(b.isProbablePrime(99))return b;}return null;}

kod testowy

    public static void main(String[] args) {
    for(int i = 2; i < 65; i++)
        System.out.println(i + " " + new Test20170105().f(i));
    }

wydajność:

2 223
3 2221
4 22229
5 2222219
6 22222223
7 22222223
8 222222227
9 22222222223
10 22222222223
11 2222222222243
12 22222222222229
13 22222222222229
14 222222222222227
15 222222222222222143
16 222222222222222221
17 222222222222222221
18 22222222222222222253
19 222222222222222222277
20 2222222222222222222239
21 22222222222222222222261
22 222222222222222222222283
23 2222222222222222222222237
24 22222222222222222222222219
25 222222222222222222222222239
26 2222222222222222222222222213
27 2222222222222222222222222227
28 222222222222222222222222222269
29 22222222222222222222222222222133
30 222222222222222222222222222222113
31 222222222222222222222222222222257
32 2222222222222222222222222222222243
33 22222222222222222222222222222222261
34 222222222222222222222222222222222223
35 222222222222222222222222222222222223
36 22222222222222222222222222222222222273
37 222222222222222222222222222222222222241
38 2222222222222222222222222222222222222287
39 22222222222222222222222222222222222222271
40 2222222222222222222222222222222222222222357
41 22222222222222222222222222222222222222222339
42 222222222222222222222222222222222222222222109
43 222222222222222222222222222222222222222222281
44 2222222222222222222222222222222222222222222297
45 22222222222222222222222222222222222222222222273
46 222222222222222222222222222222222222222222222253
47 2222222222222222222222222222222222222222222222219
48 22222222222222222222222222222222222222222222222219
49 2222222222222222222222222222222222222222222222222113
50 2222222222222222222222222222222222222222222222222279
51 22222222222222222222222222222222222222222222222222289
52 2222222222222222222222222222222222222222222222222222449
53 22222222222222222222222222222222222222222222222222222169
54 222222222222222222222222222222222222222222222222222222251
55 222222222222222222222222222222222222222222222222222222251
56 2222222222222222222222222222222222222222222222222222222213
57 222222222222222222222222222222222222222222222222222222222449
58 2222222222222222222222222222222222222222222222222222222222137
59 22222222222222222222222222222222222222222222222222222222222373
60 222222222222222222222222222222222222222222222222222222222222563
61 2222222222222222222222222222222222222222222222222222222222222129
62 2222222222222222222222222222222222222222222222222222222222222227
63 2222222222222222222222222222222222222222222222222222222222222227
64 2222222222222222222222222222222222222222222222222222222222222222203

582,5858 milisekund

Objaśnienie: zapętla liczby całkowite i dodaje je jako ciągi do ciągu głównego, który jest danym ciągiem „2”, i sprawdza, czy jest liczbą pierwszą, czy nie.