Каждый палиндром с четным числом цифр делится на 11, поэтому 11 - это единственное [палиндромное простое число] с четным числом цифр. - Дэвид Вассерман, OEIS

Я узнал об этом сегодня вручную, до того, как начал свое исследование, когда моя программа пропускала числа с четным числом цифр (кроме 11) при вычислении палиндромных простых чисел. Ваша задача: создать программу или функцию, которая при задании целочисленного значения N выводит N-й член в последовательности Палиндромика Стивена ™.

Палиндромная последовательность Стивена ™

Палиндромная последовательность Стивена ™ начинается с 11 и продолжается палиндромными полупростыми числами, кратными 11. В основном, все полупростые числа, которые были бы простыми числами, если бы 11 не «учитывались». Плюс в том, что этот список содержит числа с четным числом цифр! Ура. И многие числа с нечетным числом цифр пропускаются, так как они уже были простыми.

Начало последовательности:

1   : 11
2   : 22
3   : 33
4   : 55
5   : 77
6   : 121
7   : 737
8   : 979
9   : 1111
10  : 1441
11  : 1661
12  : 1991
13  : 3113
14  : 3223
15  : 3443
16  : 3883
17  : 7117
18  : 7447
19  : 7997
20  : 9119
21  : 9229
22  : 9449
23  : 10901

_{^{* Хотя 1331 (11 ^ 3) и тому подобное соответствуют духу этой последовательности, они не соответствуют правилам.}}

Более длинные тестовые случаи:

26  : 91619
31  : 103301
41  : 139931
51  : 173371
61  : 305503
71  : 355553
81  : 395593
91  : 725527
101 : 772277
127 : 997799
128 : 1099901
141 : 3190913
151 : 3739373
161 : 7589857
171 : 9460649
200 : 11744711
528 : 39988993

вход

Целое число N,> = 1. Вы можете использовать N-индексированное N (обязательно настройте контрольные примеры), если вы укажете это в своем ответе. Конечные переводы строк разрешены.

Выход

N-й член в палиндромной последовательности Стивена ™. Конечные переводы строк разрешены.

правила

• Единственный ввод, который может принять ваша программа / функция, - это N. Ваша программа не может, например, извлечь последовательность из OEIS (иначе применимы стандартные лазейки ).
• Вы должны быть в состоянии напечатать вывод до шести цифр (N = 127). Время не является фактором - однако, если ваша программа / функция выполняется очень долго и очень быстро, вы должны доказать, что алгоритм работает. Если ваш язык, естественно, допускает более длинные выходные данные, вы можете позволить ему естественным образом расширяться до своего предела или ограничить его десятизначными числами, в зависимости от того, что вы предпочитаете. Выход / завершение за пределами вашего предела не имеет значения, если он не является действительным выходом.
• Функция программы / функции на неверном входе не имеет значения.

Желе , 18 13 байт

ṬÆẸש11ŒḂµ#ṛ®

По некоторым причинам, это намного медленнее, чем моя первоначальная ревизия, несмотря на то, что я делаю то же самое

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

N = 127

dennis-home:~$ time jelly eun 'ṬÆẸש11ŒḂµ#ṛ®' <<< 127
997799

real    1m43.745s
user    1m43.676s
sys     0m0.113s

Как это устроено

ṬÆẸש11ŒḂµ#ṛ®  Main link. No arguments.

         µ     Combine all links to the left into a chain.
          #    Read an integer n from STDIN and call the chain monadically, with
               argument k = 0, 1, 2, ... until n values of k result in a truthy
               output. Return the array of all matching values of k.
Ṭ                Untruth; yield [0, 0, 0, ..., 1] (k-1 zeroes followed by a 1) or
                 [] if k = 0.
 ÆẸ              Unexponents; consider the resulting array as exponents of the
                 sequence of primes and yield the corresponding integer. For k = 0,
                 this yields 1. For k > 0, it yields the k-th prime.
   ש11          Multiply the result by 11 and copy the product to the register.
       ŒḂ        Test if the product is a palindrome.
           ṛ®  Replace the resulting array with the integer in the register.

Python 2 , 76 73 72 70 69 68 байт

n=input();c=k=m=11
while n:m*=k/c;k+=c;n-=`k`==`k`[::~m%k-c]
print k

Спасибо @WheatWizard за 3 байта!

Спасибо @ ÖrjanJohansen за отыгрывание 1 байта!

Спасибо @xnor и @ ØrjanJohansen за прокладку пути до 68 байт!

Ввод 0-индексирован. Попробуйте онлайн! или проверьте первые 31 контрольных примеров .

Фон

Напомним, что теорема Вильсона утверждает, что для всех целых чисел p> 1 ,

это означает, что (р - 1)! +1 равномерно делится на р тогда и только тогда, когда р простое.

Если р> 1 это не простое, оно составное; пусть q наименьший простой делитель числа p . Ясно, что q ≤ p / q . Есть два случая:

• Если q = p / q , мы имеем p = q² .

  Если q = 2 , (p - 1)! = 3! = 6 , значит (р - 1)! конгруэнтно 2 по модулю р .

  Если p / q = q> 2 , то 2q <p . Таким образом, q и 2q оба находятся среди 1,…, p - 1 , произведение которых является факториалом p - 1 , поэтому 2p = 2q² = q · 2q делит (p - 1)! равномерно.

• Если q <p / q , q и p / q оба среди 1,…, p - 1 , то p = q · p / q делит (p - 1)! равномерно.

Подводя итог,

для всех целых чисел p> 1 .

Теперь для всех целочисленных конгруэнций и всех целых чисел a , b и c выполняется следующее.

Когда a = -1 , b = 11 и c = -1 , мы следуем этому

и, поскольку 21 и -23 являются конгруэнтными по модулю 44 а -1 и 11p-1 являются конгруэнтными по модулю 11p , мы приходим к следующему выводу.

Для всех возможных значений р , результат ( 11 , 21 или 11p - 1 ) будет находиться в диапазоне 0,…, 11p - 1 , поэтому эти значения соответствуют тем, которые будут возвращены Python% .

Как это устроено

Мы инициализируем c , k и m до 11 после сохранения ввода в n . с будет постоянной для оставшейся части программы. Так как в следующей строке есть три вхождения c, и назначение c стоит всего два байта, это сохраняет байт. k можно представить как 11p, используя значение p из предыдущего абзаца; изначально k = 11 = 11 · 1! , м занимает место 11 · (р - 1)! ; изначально m = 11 = 11 · 0! , К и мбудет удовлетворять соотношению m = 11 · (k / 11)! во все времена.

n представляет число «палиндромов Стивена», которые мы должны найти. Поскольку изначально k = 11 , мы можем вывести k дословно без дальнейших вычислений. Однако, когда n положительно, мы входим в цикл while. Цикл начинается с умножения m на k / c = p , затем добавления 11 к k , увеличивая, таким образом, p . Если k является членом последовательности, мы вычитаем 1 из n и начинаем сначала. Как только n достигнет 0 , мы находим элемент последовательности по нужному индексу и вырываемся из цикла, затем выводим последнее значение k .

Выражение

`k`==`k`[::~m%k-c]

выполняет реальный тест, и его результат ( True / 1 для элементов последовательности, 0 / False в противном случае) вычитается из n . Как было показано ранее, ~ m% k = (-m - 1)% k = (-11 · (p - 1)! - 1)% 11p равно 10, если p простое число, 21, если p = 4 , и 11p - 1 > 43, если p> 4 является составным. Таким образом, после вычитания c = 11 у нас останется -1 для простого p и положительное целое число больше 9 в противном случае.

Для простого р , ​`k`[::-1]дает нам строковое представление к с обратной последовательностью цифр, поэтому сравнивая его ​`k`​проверяет , находится ли к палиндром. Если это так, все условия выполнены, и k является членом последовательности. Однако, если p не является простым, шаг большого диапазона и тот факт, что k всегда будет иметь более одной цифры, означают, что ​`k`[::-1]не может иметь такое же количество цифр, как ​`k`​, не говоря уже о том, чтобы быть равным ему.

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

:I{11|ṗ×₁₁≜.↔}ᶠ⁽t

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

Это 1-индексированный.

объяснение

:I{          }ᶠ⁽t    Find the Input'th result of the following:
   11                  Output = 11
     |                 Or
          ≜.           Output is an integer…
      ṗ×₁₁             …which is the result of multiplying a prime by 11…
           .↔          …and Output reversed is still the Output

Две реализации с этим ответом:

• Мне нужно исправить тот факт, что передача верхнего индекса в метапредикаты (с ⁽) не работает, если нет ввода для передачи (вот почему я должен добавить:I ).
• Мне нужно добавить метапредикат, чтобы получить Nрезультат предиката (который будет избегать использования ᶠ⁽tи вместо него, например ⁿ⁽).

Реализация обоих изменений приведет к тому, что ответ будет 14 байтов.

Mathematica, 65 60 байт

n=NextPrime;11Nest[n@#//.x_/;!PalindromeQ[11x]:>n@x&,1,#-1]&

Выполняет итерацию непосредственно через простые числа NextPrimeи проверяет, является ли 11-кратное простое число палиндромом. Работает до N = 528 . Результаты 528 и 529 разнесены более чем на 2 ¹⁶ простых чисел, и в этот момент //.не удастся выполнить достаточное количество замен.

Python 2 , 111 107 103 102 101 100 91 90 89 байт

Деннис меня избил здесь , так что иди проверь его ответ.

Этот ответ с нулевым индексом

n=input()
r=1
while n:r+=1;c=`r*11`;n-=all(r%x for x in range(2,r))*c==c[::-1]
print r*11

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

Один байт сохранен благодаря математическому наркоману

объяснение

Сначала мы берем ввод и устанавливаем его, nмы также создаем новую переменную r=1. Мы будем считать, что rищем палиндромы, которые являются произведением простого числа и 11. Каждый раз, когда мы находим один, мы будем уменьшатьn пока он не достигнет 0.

Итак, мы начинаем цикл:

while n:

Первое, что мы делаем, это увеличение r

r+=1

Мы также предопределяем переменную cкак строковое представлениеr*11

c=`r*11`

Теперь мы хотим уменьшить, nесли мы нашли такое число. Мы просто вычтем логическое представление, если r*11соответствует шаблону r. Если это так, Falseмы вычтем ноль, а если это Trueтак, то вычтем 1.

Для вычисления логического значения мы делаем:

all(r%x for x in range(2,r))*c==c[::-1]

Первая часть allопределит, rпростое ли. Мы умножаем результат на, cесли rпростое число, это будет просто, cно если rоно составное, это будет ""пустая строка. Затем мы сравним это с c[::-1]противоположностью c. Если rэто простое число и cявляется палиндромом, это будет True, если любой из них потерпит неудачу, все это будет оценено как ложное.

Когда nноль, мы простоprint c .

83 байта

Вот рекурсивное решение, которое короче, но, к сожалению, не соответствует спецификациям, потому что оно слишком быстро достигает предела рекурсии Python.

f=lambda n,r=1:n and f(n-all(r%x*(`r*11`==`r*11`[::-1])for x in range(2,r)),r+1)+11

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

05AB1E , 15 байтов

0 индексированные.

11Iµ11N*DÂQNp*½

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

объяснение

11               # initialize stack with 11
  Iµ             # loop over N in [1 ... inf] until counter equals input
    11N*         # multiply N by 11
        D        # duplicate
         ÂQ      # check if the copy equals its reverse
           Np    # check if N is prime
             *   # multiply the results of the checks together
              ½  # if 1, increase counter

Haskell , 94 90 байт

h#n|n<2=0|mod n h<1=1+h#div n h|j<-h+1=j#n
([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!)

Попробуйте онлайн! Пример использования:([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127 .

[0,11..]создает бесконечный список [0,11,22,33, ...](ноль необходим, чтобы сделать последовательность 1-индексированной). Для каждого nв этом списке мы проверяем n==(read.reverse.show)n, является ли nпалиндром. 3>2#nпроверяет, nимеет ли не более двух простых делителей. Поскольку nвсегда делится на 11, мы не получаем никаких реальных простых чисел, а только полупростые.

Редактировать: Спасибо Орджану Йохансену за игру в гольф 4 байта!

PHP, 82 байта

for(;$d<$argn;$i>1||($p=11*$n)!=strrev($p)?:$d++)for($i=++$n;--$i&&$n%$i;);echo$p;

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

Аксиома, 105 байт

g(n)==(i:=c:=1;repeat(c=n=>break;i:=i+1;if(prime? i)then(x:=(11*i)::String;x=reverse(x)=>(c:=c+1)));i*11)

ungolf, тестовый код и результаты

f(n)==
   i:=c:=1
   repeat
      c=n=>break
      i:=i+1
      if(prime? i)then(x:=(11*i)::String;x=reverse(x)=>(c:=c+1))
   i*11


(5) -> [[i,g(i)]  for i in 1..23]
   (5)
   [[1,11], [2,22], [3,33], [4,55], [5,77], [6,121], [7,737], [8,979],
    [9,1111], [10,1441], [11,1661], [12,1991], [13,3113], [14,3223], [15,3443],
    [16,3883], [17,7117], [18,7447], [19,7997], [20,9119], [21,9229],
    [22,9449], [23,10901]]
                                          Type: List List PositiveInteger
(6) -> [[i,g(i)]  for i in [26,31,41,101,151,200]]
   (6)
   [[26,91619], [31,103301], [41,139931], [101,772277], [151,3739373],
    [200,11744711]]

Здесь g (700) = 92511529, поэтому предел будет> 700; ww (1000) = 703999307, но с использованием nextPrime ()