Każdy palindrom z parzystą liczbą cyfr dzieli się przez 11, więc 11 jest jedyną [liczbą palindromową] z parzystą liczbą cyfr. - David Wasserman, OEIS

Nauczyłem się tego dzisiaj ręcznie, zanim zacząłem swoje badania, kiedy mój program pomijał liczby z parzystą liczbą cyfr (oprócz 11) podczas obliczania liczb pierwszych palindromicznych. Twoje zadanie: stwórz program lub funkcję, która otrzyma liczbę całkowitą N, która wypisze N-ty termin w sekwencji Stephen's Palindromic Sequence ™.

Stephen's Palindromic Sequence ™

Sekwencja Palindromowa Stephena ™ zaczyna się od 11 i kontynuuje od półpierwszych palindromowych podzielnych przez 11. Zasadniczo wszystkie półpierwsze, które byłyby liczbami pierwszymi, gdyby 11 się nie liczyły. Plusem jest to, że ta lista zawiera liczby o parzystej liczbie cyfr! Tak I wiele liczb o nieparzystej liczbie cyfr jest pomijanych, ponieważ były już pierwsze.

Początek sekwencji:

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

_{^{* Chociaż 1331 (11 ^ 3) i podobne pasują do ducha tej sekwencji, nie pasują do reguł.}}

Dłuższe przypadki testowe:

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

Wejście

Liczba całkowita N,> = 1. Możesz użyć N z indeksowaniem 0 (pamiętaj o dostosowaniu przypadków testowych), jeśli podasz to w swojej odpowiedzi. Końcowe znaki nowej linii są dozwolone.

Wynik

Nth termin w Stephen's Palindromic Sequence ™. Końcowe znaki nowej linii są dozwolone.

Zasady

• Jedyne wejście, jakie może przyjąć Twój program / funkcja, to N. Twój program nie może na przykład pobrać sekwencji z OEIS ( obowiązują również standardowe luki ).
• Musisz być w stanie wydrukować wynik do sześciu cyfr (N = 127). Czas nie ma znaczenia - jeśli jednak twój program / funkcja bardzo szybko się wydłuża, musisz udowodnić, że algorytm działa. Jeśli twój język naturalnie pozwala na dłuższe wyniki, możesz pozwolić mu rozwinąć się naturalnie do jego limitu lub ograniczyć go do dziesięciu cyfr, w zależności od tego, co wolisz. Wyjście / zakończenie poza twoim limitem nie ma znaczenia, o ile nie wydaje się być prawidłowym wyjściem.
• Funkcja programu / funkcji przy nieprawidłowym wejściu nie ma znaczenia.

Galaretka , 18 13 bajtów

ṬÆẸש11ŒḂµ#ṛ®

Z jakiegoś powodu jest to znacznie wolniejsze niż moja początkowa wersja, mimo że robię dokładnie to samo.

Wypróbuj online!

N = 127

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

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

Jak to działa

ṬÆẸש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 bajtów

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

Dzięki @WheatWizard za grę w golfa z 3 bajtów!

Dzięki @ ØrjanJohansen za grę w golfa na 1 bajcie!

Dzięki @xnor i @ ØrjanJohansen za utorowanie drogi do 68 bajtów!

Wejście jest indeksowane na 0. Wypróbuj online! lub sprawdź pierwsze 31 przypadków testowych .

tło

Przypomnijmy, że twierdzenie Wilsona stwierdza, że ​​dla wszystkich liczb całkowitych p> 1 ,

co oznacza, że (p - 1)! + 1 można podzielić równo przez p wtedy i tylko wtedy, gdy p jest liczbą pierwszą.

Jeśli p> 1 nie jest liczbą pierwszą, jest złożone; niech q będzie najmniejszym głównym dzielnikiem p . Oczywiście, q ≤ p / q . Istnieją dwa przypadki:

• Jeśli q = p / q , mamy to p = q² .

  Jeśli q = 2 , (p - 1)! = 3! = 6 , więc (p - 1)! jest zgodny z 2 modulo p .

  Jeśli p / q = q> 2 , więc 2q <p . W ten sposób q i 2q należą do 1,…, p - 1 , którego iloczyn jest silnią p - 1 , więc 2p = 2q² = q · 2q dzieli (p - 1)! równomiernie.

• Jeśli q <p / q , q i p / q znajdują się między 1,…, p - 1 , więc p = q · p / q dzieli (p - 1)! równomiernie.

Podsumowując,

dla wszystkich liczb całkowitych p> 1 .

Teraz, dla wszystkich przystawek liczb całkowitych i wszystkich liczb całkowitych a , b i c , obowiązują następujące.

Gdy a = -1 , b = 11 i c = -1 , podążamy za tym

a ponieważ 21 i -23 są przystające modulo 44, a -1 i 11p-1 są przystające modulo 11p , dochodzimy do następującego wniosku.

Dla wszystkich możliwych wartości p wynik ( 11 , 21 lub 11p - 1 ) mieści się w zakresie 0,…, 11p - 1 , więc wartości te są zgodne z wartościami zwracanymi przez %operatora Pythona .

Jak to działa

Inicjujemy c , k oraz m do 11 po zapisaniu danych wejściowych w n . c będzie stały przez pozostałą część programu. Ponieważ istnieją trzy wystąpienia c na poniższej linii i przypisanie c kosztuje tylko dwa bajty, to zapisuje bajt. k można pomyśleć o 11p, używając znaczenia p z poprzedniego akapitu; początkowo k = 11 = 11,1! . m zajmuje miejsce 11 · (p - 1)! ; początkowo m = 11 = 11,0! . k i mspełni relację m = 11 · (k / 11)! w każdym momencie.

n oznacza liczbę „palindromów Szczepana”, którą musimy znaleźć. Ponieważ k = 11 początkowo możemy wypisać k dosłownie bez dalszych obliczeń. Jednak gdy n jest dodatnie, wchodzimy do pętli while. Pętla zaczyna się od pomnożenia m przez k / c = p , a następnie dodania 11 do k , zwiększając w ten sposób p . Jeśli k jest członkiem sekwencji, odejmujemy 1 od n i zaczynamy od nowa. Gdy n osiągnie wartość 0 , znaleźliśmy element sekwencji o pożądanym indeksie i wyrwamy się z pętli, a następnie wypisujemy ostatnią wartość k.

Ekspresja

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

wykonuje rzeczywisty test, a jego wynik ( True / 1 dla elementów sekwencji, 0 / False w przeciwnym razie) jest odejmowany od n . Jak widać wcześniej, ~ m% k = (-m - 1)% k = (-11 · (p - 1)! - 1)% 11p równa się 10, jeśli p jest liczbą pierwszą, 21 jeśli p = 4 , a 11p - 1 > 43, jeżeli p> 4 jest złożony. Tak więc, po odjęciu c = 11 , pozostajemy -1 dla liczby pierwszej p i dodatniej liczby całkowitej większej niż 9 w przeciwnym razie.

Do prime p , ​`k`[::-1]daje nam reprezentację ciąg k z odwróconej kolejności cyfr, więc porównując go do ​`k`​kontroli, czy k jest palindrom. Jeśli tak, wszystkie warunki są spełnione, a k jest członkiem sekwencji. Jeśli jednak p nie jest liczbą pierwszą, krok dużego zakresu i fakt, że k będzie zawsze mieć więcej niż jedną cyfrę, oznacza, że ​`k`[::-1]nie może mieć takiej samej liczby cyfr jak ​`k`​, a co dopiero być równym.

Brachylog , 17 bajtów

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

Wypróbuj online!

Jest to indeks 1.

Wyjaśnienie

: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

Dwie realizacje z tą odpowiedzią:

• Muszę naprawić fakt, że przekazywanie indeksu górnego do metapredicates (with ⁽) nie działa, jeśli nie ma żadnych danych wejściowych do przekazania (dlatego muszę to dodać :I).
• Muszę dodać metapredykat, aby uzyskać Nwynik th predykatu (co pozwoliłoby uniknąć użycia, ᶠ⁽ta zamiast tego np ⁿ⁽.).

Wdrożenie obu zmian sprawiłoby, że ta odpowiedź miałaby 14 bajtów.

Mathematica, 65 60 bajtów

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

Iteruje bezpośrednio przez liczby pierwsze, NextPrimesprawdzając, czy 11 razy liczba pierwsza jest palindromem. Działa do N = 528 . Wyniki 528 i 529 są oddalone o więcej niż 2 ¹⁶ liczb pierwszych, w którym to momencie //.nie uda się podjąć wystarczającej liczby podstawień.

Python 2 , 111 107 103 102 101 100 91 90 89 bajtów

Dennis mnie tu pobił , więc sprawdź jego odpowiedź.

Ta odpowiedź jest indeksowana zerowo

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

Wypróbuj online!

Jeden bajt zaoszczędzony dzięki ćpunowi matematycznemu

Wyjaśnienie

Najpierw pobieramy dane wejściowe i ustawiamy je na n, a także tworzymy nową zmienną r=1. Będziemy liczyć rszukanie palindromów, które są iloczynem liczby pierwszej i 11. Za każdym razem, gdy znajdziemy jedną, zmniejszamy nją, aż osiągnie 0.

Rozpoczynamy pętlę:

while n:

Pierwszą rzeczą, którą robimy, jest przyrost r

r+=1

Predefiniujemy również zmienną c jako reprezentację ciągur*11

c=`r*11`

Teraz chcemy zmniejszyć, njeśli znaleźliśmy taką liczbę. Po prostu odejmiemy wartość logiczną reprezentującą ifr*11 pasuje do wzorca r. Jeśli tak False, odejmiemy zero, a jeśli tak True, odejmiemy 1.

Aby obliczyć wartość logiczną, wykonujemy:

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

Pierwsza część allokreśli, czy rjest liczbą pierwszą. Pomnożymy wynik przez cif rjest liczbą pierwszą, będzie to po prostu, cale jeśli rjest złożone, będzie to ""pusty ciąg znaków. Następnie porównujemy to c[::-1]z odwrotnością c. Gdybyr jest liczbą pierwszą i cjest palindromem, to będzie True, jeśli jedno z nich się nie powiedzie, cała rzecz będzie oceniana jako fałszywa.

Gdy n wynosi zero, po prostu print c.

83 bajty

Oto rozwiązanie rekurencyjne, które jest krótsze, ale niestety nie spełnia specyfikacji, ponieważ zbyt szybko uderza w limit rekurencyjny Pythona.

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

Wypróbuj online!

05AB1E , 15 bajtów

0-indeksowane.

11Iµ11N*DÂQNp*½

Wypróbuj online!

Wyjaśnienie

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 bajtów

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]!!)

Wypróbuj online! Przykładowe zastosowania: ([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127.

[0,11..]konstruuje nieskończoną listę [0,11,22,33, ...](zero jest potrzebne, aby sekwencja była indeksowana 1). Dla każdej nz tej listy sprawdzamy n==(read.reverse.show)n, czy njest to palindrom. 3>2#nsprawdza, czy nma najwyżej dwa główne dzielniki. Ponieważ nzawsze jest podzielna przez 11, nie otrzymujemy żadnych liczb pierwszych rzeczywistych, a tylko półpierwsze.

Edycja: Podziękowania dla Ørjana Johansena za grę w 4 bajty!

PHP, 82 bajty

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

Wypróbuj online!

Aksjomat, 105 bajtów

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, kod testu i wyniki

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

Tutaj g (700) = 92511529, więc limit wynosiłby> 700; ww (1000) = 703999307, ale przy użyciu nextPrime ()