Задача под рукой, учитывая число n, найти наименьшее простое число, которое начинается с НАИМЕНЬШЕГО n числа числа 2в начале числа. Это последовательность, которую я нашел в OEIS ( A068103 ).

Первые 17 чисел в последовательности даны ниже, если вы хотите больше, мне придется на самом деле реализовать последовательность, что я не против сделать.

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

Просто подумал, что это будет крутая комбинация манипуляции со строками, обнаружения простых чисел и последовательностей. Это код-гольф , наименьшее количество байтов будет объявлено победителем, вероятно, в конце месяца.

Брахилог , 12 11 байт

:2rj:Acb#p=

Попробуйте онлайн!

Это переводит на брахилог на удивление напрямую. Это функция, а не полная программа (хотя предоставление интерпретатора Zв качестве аргумента командной строки заставляет его добавить соответствующую обертку для превращения функции в программу; это то, что я сделал, чтобы заставить работать ссылку TIO). Также jвесьма прискорбно, что, кажется, индексирован -1 и нуждается в исправлении, чтобы учесть это.

Вы можете привести разумный аргумент, что в =этом нет необходимости, но я думаю, что, если сформулировать проблему, это так; без, функция, описывающая набор всех простых чисел, которые начинаются с заданного числа 2s, и без какого-либо явного утверждения, что программа должна что- то делать с этим описанием (в данном случае, генерируя первое значение), она, вероятно, не соответствовать спецификации.

объяснение

: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

При использовании в качестве функции, возвращающей целое число, ничто никогда не запрашивает значения после первого, поэтому первое, о чем нам следует беспокоиться.

Одна тонкость (указано в комментариях): :Acbи b:Acматематически эквивалентны (так как один удаляется с начала, а другой добавляет к концу, а область между ними никогда не перекрывается); Раньше у меня было b:Ac, что более естественно, но оно ломается при вводе 0 (что я предполагаю, потому что cотказывается объединять пустой список с чем-либо; многие встроенные функции Brachylog имеют тенденцию разбиваться на пустые списки по некоторым причинам). :Acbгарантирует, что cникогда не будет видеть пустой список, а это означает, что регистр ввода 0 теперь тоже может работать.

Java (OpenJDK 8) , 164 110 байт

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

Спасибо @FryAmTheEggman за кучу байтов!

Попробуйте онлайн!

Pyth, 12 байт

f&!x`T*Q\2P_

В псевдокоде:

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

Цикл lambdaначинается с T=1, увеличиваясь на 1, пока условие не будет выполнено. Строка 2s должна быть подстрокой с начала строки, то есть метод индекса должен возвращаться 0. Если подстрока не найдена, она возвращает, -1что удобно и верно, поэтому исключительного случая не существует.

Вы можете попробовать это онлайн здесь , но сервер допускает только ввод 4.

Perl, 50 байт

49 байтов кода + -pфлаг.

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

Предоставить ввод без окончательного перевода строки. Например:

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

Это займет некоторое время, чтобы запустить числа больше 4, поскольку он проверяет каждое число (есть 2 теста: первый /^2{$_}/проверяет, достаточно ли 2 в начале, а второй (1x$\)!~/^1?$|^(11+)\1+$/проверяет на простоту (с очень плохими характеристиками)).

Haskell, 73 байта

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

Пример использования: f 3-> 2221.

Грубая сила. [1..n]>>"2"создает список n 2s, который сравнивается с первыми nсимволами в строковом представлении текущего простого числа.

Mathematica, 103 байта

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

Безымянная функция, принимающая неотрицательный целочисленный аргумент #и возвращающая целое число. Он буквально проверяет все положительные целые числа по очереди, пока не найдет то, которое начинается с #2 и является простым. Ужасно медленно для входов выше 5.

предыдущий результат: Mathematica, 155 байт

Mathematica была бы лучше для игры в гольф, если бы она не была так сильно напечатана; мы должны явно переключаться между типами integer / list / string.

(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&

Этот алгоритм работает со списками цифр , как ни странно, начиная с {2,...,2,1}. Пока они не являются цифрами простого числа, он добавляет единицу к последней цифре, используя правило {j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}..., а затем вручную реализует перенос числа "один к следующему разряду", пока любой из цифры равны 10, используя правило {a__,b_,10,c___}->{a,b+1,0,c}... и затем, если мы зашли так далеко, что последний из ведущих 2s превратился в a 3, начинается с другой цифры в конце, используя правило {a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}. В /. 23->2конце просто исправляется особый случай ввода 1: большинство простых чисел не может заканчиваться 2, но 2может. (Несколько ошибок выплескиваются на входах 0и 1, но функция находит правильный ответ.)

Этот алгоритм довольно быстрый: например, на моем ноутбуке вычисление первого простого числа, начинающегося с 1000 2с, занимает менее 3 секунд 22...220521.

Pyth, 17 байт

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

Кажется, не может решить через n = 4Интернет, но это правильно в теории.

объяснение

               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 байта

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

Попытайся

Expanded:

{
  ( $/ = 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..*
}

Желе , 14 байт

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

Очень неэффективно. Попробуйте онлайн!

Пайк, 14 байт

.fj`Q\2*.^j_P&

Попробуй это здесь!

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

12 байт после исправления и новой функции

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

Попробуй это здесь!

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

Мудрец, 69 68 байт

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

Использует генератор, чтобы найти первое (а следовательно, наименьшее) из бесконечного числа членов.

Japt, 20 байт

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

Проверьте это онлайн! Он завершается в течение двух секунд на моем компьютере для всех входов до 14, и после этого он естественно теряет точность (JavaScript имеет целочисленную точность до 2 ⁵³ ).

Большое спасибо @obarakon за работу над этим :-)

объяснение

                       // 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

В последней версии Japt это может быть 12 байтов:

_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

Проверьте это онлайн! Он заканчивается в течение полсекунды на моей машине для всех входов до 14.

PHP, 76 байт

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

принимает входные данные из аргумента командной строки. Беги с -r.

сломать

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 байта

Работает до 2 ^ 63-1 (9223372036854775807) , занимает значительное время, чтобы закончить для N> 8.

Golfed

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

Тест

>seq 0 7|xargs -L1 ./twist

2
2
223
2221
22229
2222203
22222223
22222223

Python 3, 406 байт

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

тестовый код

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

тестовый вывод

 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

Я решил пойти на скорости в довольно большом диапазоне, а не в байтовом размере. :) Я использую детерминистический критерий первичности Миллера-Рабина, который гарантирован до 3317044064679887385961981 с этим набором свидетелей. Большие простые числа всегда успешно пройдут тест, но некоторые композиты также могут пройти, хотя вероятность крайне мала. Однако я также проверил выходные числа для i> 22, используя pyecm программу факторизации эллиптической кривой, и они выглядят простыми.

Python 3, 132 байта

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

Любая надежда на производительность была принесена в жертву ради меньшего количества байтов.

Java, 163 байта

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

тестовый код

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

выход:

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 миллисекунд

Объяснение: перебирает целые числа и добавляет их в виде строк в корневую строку, которая является заданной строкой «2», и проверяет, является ли она простой или нет.