Setiap palindrom dengan angka genap dibagi menjadi 11, jadi 11 adalah satu-satunya [prima palindromik] dengan angka genap. - David Wasserman, OEIS

Saya mempelajari ini hari ini dengan cara manual, sebelum saya melakukan penelitian, ketika program saya melewatkan angka dengan angka genap (kecuali 11) ketika menghitung bilangan prima palindrom. Tugas Anda: buat program atau fungsi yang ketika diberi input integer N, mengeluarkan istilah ke-N di Stephen's Palindromic Sequence ™.

Stephen's Palindromic Sequence ™

Stephen's Palindromic Sequence ™ dimulai dengan 11, dan berlanjut dengan semiprimes palindromic yang dapat dibagi oleh 11. Pada dasarnya, semua semiprimes yang akan menjadi bilangan prima jika 11 tidak "dihitung." Sisi baiknya adalah daftar ini berisi angka dengan angka genap! Yay. Dan, banyak angka dengan angka ganjil dilewati, karena mereka sudah prima.

Awal urutan:

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

_{^{* Meskipun 1331 (11 ^ 3) dan serupa sesuai dengan semangat urutan ini, mereka tidak sesuai dengan aturan.}}

Kasus uji yang lebih panjang:

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

Memasukkan

Integer N,> = 1. Anda dapat menggunakan N-diindeks 0 (pastikan untuk menyesuaikan kasus uji) jika Anda menentukannya dalam jawaban Anda. Membuntuti baris baru diizinkan.

Keluaran

Istilah N di Stephen's Palindromic Sequence ™. Membuntuti baris baru diizinkan.

Aturan

• Satu-satunya input yang dapat diambil oleh program / fungsi Anda adalah N. Program Anda tidak dapat, misalnya, mengambil urutan dari OEIS (alias celah standar berlaku ).
• Anda harus dapat mencetak output hingga enam digit (N = 127). Waktu bukanlah faktor - namun, jika program / fungsi Anda menjadi sangat lama sangat cepat, Anda harus membuktikan bahwa algoritme berfungsi. Jika bahasa Anda secara alami memungkinkan hasil yang lebih lama, maka Anda dapat membiarkannya berkembang secara alami hingga batasnya, atau membatasi sepuluh digit, mana saja yang Anda inginkan. Output / terminasi di luar batas Anda tidak masalah, asalkan itu tidak tampak sebagai output yang valid.
• Fungsi program / fungsi pada input yang tidak valid tidak relevan.

Jelly , 18 13 byte

ṬÆẸש11ŒḂµ#ṛ®

Untuk beberapa alasan, ini jauh lebih lambat daripada revisi awal saya, meskipun melakukan hal yang persis sama.

Cobalah online!

N = 127

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

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

Bagaimana itu bekerja

ṬÆẸש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 byte

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

Terima kasih kepada @WheatWizard untuk bermain golf 3 byte!

Terima kasih kepada @ ØrjanJohansen karena bermain golf 1 byte!

Terima kasih kepada @xnor dan @ ØrjanJohansen karena telah membuka jalan ke 68 byte!

Input diindeks 0. Cobalah online! atau verifikasi 31 kasus uji pertama .

Latar Belakang

Ingat bahwa teorema Wilson menyatakan bahwa untuk semua bilangan bulat p> 1 ,

artinya (p - 1)! +1 dapat dibagi secara merata oleh p jika dan hanya jika p prima.

Jika p> 1 adalah tidak prima, itu adalah komposit; misalkan q menjadi pembagi utama terkecil p . Jelas, q ≤ p / q . Ada dua kasus:

• Jika q = p / q , kita memiliki p = q² .

  Jika q = 2 , (p - 1)! = 3! = 6 , jadi (p - 1)! kongruen dengan 2 modulo p .

  Jika p / q = q> 2 , maka 2q <p . Dengan cara ini, q dan 2q keduanya berada di antara 1, ..., p - 1 , yang produknya merupakan faktorial dari p - 1 , jadi 2p = 2q² = q · 2q membagi (p - 1)! rata.

• Jika q <p / q , q dan p / q keduanya di antara 1, ..., p - 1 , maka p = q · p / q membaginya (p - 1)! rata.

Menyimpulkan,

untuk semua bilangan bulat p> 1 .

Sekarang, untuk semua kongruensi integer dan semua integer a , b , dan c , berikut ini berlaku.

Ketika a = -1 , b = 11 , dan c = -1 , kita ikuti itu

dan, karena 21 dan -23 kongruen modulo 44 dan -1 dan 11p-1 kongruen modulo 11p , kita sampai pada kesimpulan berikut.

Untuk semua kemungkinan nilai p , hasil ( 11 , 21 , atau 11p - 1 ) akan jatuh dalam kisaran 0, ..., 11p - 1 , sehingga nilai ini cocok dengan yang akan dikembalikan oleh %operator Python .

Bagaimana itu bekerja

Kami menginisialisasi c , k , dan m hingga 11 setelah menyimpan input dalam n . c akan konstan untuk sisa program. Karena ada tiga kemunculan c pada baris berikut dan menetapkan biaya c hanya dua byte, ini menghemat satu byte. k dapat dianggap 11p menggunakan arti p dari paragraf sebelumnya; awalnya, k = 11 = 11 · 1! . m mengambil tempat 11 · (p - 1)! ; awalnya, m = 11 = 11 · 0! . k dan makan memuaskan hubungan m = 11 · (k / 11)! selalu.

n mewakili jumlah "palindrom Stephen" yang harus kita temukan. Karena k = 11 pada awalnya, kita dapat menampilkan k kata demi kata tanpa perhitungan lebih lanjut. Namun, ketika n positif, kita memasuki loop while. Loop dimulai dengan mengalikan m dengan k / c = p , lalu menambahkan 11 ke k , sehingga menambah p . Jika k adalah anggota urutan, kita kurangi 1 dari n dan mulai lagi. Setelah n mencapai 0 , kami menemukan anggota urutan pada indeks yang diinginkan dan keluar dari loop, lalu mencetak nilai terakhir k.

Ekspresi

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

melakukan tes yang sebenarnya, dan hasilnya ( Benar / 1 untuk anggota urutan, 0 / Salah sebaliknya) dikurangkan dari n . Seperti yang terlihat sebelumnya, ~ m% k = (-m - 1)% k = (-11 · (p - 1)! - 1)% 11p sama dengan 10 jika p adalah prima, 21 jika p = 4 , dan 11p - 1 > 43 jika p> 4 adalah komposit. Dengan demikian, setelah mengurangi c = 11 , kita pergi dengan -1 untuk prime p dan bilangan bulat positif lebih besar dari 9 sebaliknya.

Untuk prime p , ​`k`[::-1]beri kita representasi string k dengan urutan digit terbalik, jadi membandingkannya untuk ​`k`​memeriksa apakah k adalah palindrome. Jika ya, semua kondisi terpenuhi dan k adalah anggota urutan. Namun, jika p tidak prima, langkah rentang besar dan fakta bahwa k akan selalu memiliki lebih dari satu digit berarti yang ​`k`[::-1]tidak dapat memiliki jumlah digit yang sama dengan ​`k`​, apalagi sama dengan itu.

Brachylog , 17 byte

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

Cobalah online!

Ini 1-diindeks.

Penjelasan

: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

Dua realisasi dengan jawaban ini:

• Saya perlu memperbaiki fakta bahwa superscript yang lewat ke metapredicates (with ⁽) tidak berfungsi jika tidak ada input yang harus lewat (itulah sebabnya saya harus menambahkan :I).
• Saya perlu menambahkan metapredicate untuk mendapatkan Nhasil th dari predikat (yang akan menghindari penggunaan ᶠ⁽tdan sebagai gantinya misalnya ⁿ⁽).

Menerapkan kedua perubahan akan membuat jawaban itu 14 byte.

Mathematica, 65 60 byte

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

Ulangi secara langsung melalui bilangan prima menggunakan NextPrimedan memeriksa apakah 11 kali prime adalah palindrome. Berfungsi hingga N = 528 . Hasil 528 dan 529 lebih dari 2 ¹⁶ bilangan prima terpisah, pada titik mana //.akan gagal untuk mencoba jumlah substitusi yang cukup.

Python 2 , 111 107 103 102 101 100 91 90 89 bytes

Dennis telah saya kalahkan di sini , jadi periksa jawabannya.

Jawaban ini nol diindeks

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

Cobalah online!

Satu byte disimpan berkat pecandu matematika

Penjelasan

Pertama kita mengambil input dan mengaturnya agar nkita juga membuat variabel baru r=1. Kami akan menghitung rmencari palindrom yang merupakan produk perdana dan 11. Setiap kali kami menemukan palindrom kami akan menurun nhingga mencapai 0.

Jadi kita memulai perulangan:

while n:

Hal pertama yang kita lakukan adalah kenaikan r

r+=1

Kami juga mendefinisikan variabel csebagai representasi stringr*11

c=`r*11`

Sekarang kami ingin mengurangi njika kami telah menemukan nomor tersebut. Kami hanya akan mengurangi boolean yang mewakili jika r*11cocok dengan pola dari r. Jika ini Falsekita akan mengurangi nol dan jika itu Truemaka akan mengurangi 1.

Untuk menghitung boolean kami lakukan:

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

Bagian pertama allakan menentukan apakah rprima. Kami mengalikan hasilnya dengan cjika rini prima, ini hanya akan menjadi ctetapi jika rkomposit itu akan menjadi "", string kosong. Kami kemudian membandingkan ini c[::-1]yang merupakan kebalikan dari c. Jika rprima dan cpalindrom ini akan menjadi True, jika salah satu gagal semuanya akan dinilai sebagai salah.

Kapan nnol kita cukup print c.

83 byte

Berikut ini adalah solusi rekursif yang lebih pendek tetapi sayangnya tidak memenuhi spesifikasi karena hits rekursi python terlalu cepat.

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

Cobalah online!

05AB1E , 15 byte

Diindeks 0.

11Iµ11N*DÂQNp*½

Cobalah online!

Penjelasan

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 byte

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

Cobalah online! Contoh penggunaan: ([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127.

[0,11..]membangun daftar tak terbatas [0,11,22,33, ...](nol diperlukan untuk membuat urutan 1-diindeks). Untuk masing-masing ndalam daftar ini kita periksa n==(read.reverse.show)n, apakah npalindrom. 3>2#nmemeriksa apakah nmemiliki paling tidak dua pembagi utama. Karena nselalu dapat dibagi oleh 11, kita tidak mendapatkan bilangan prima nyata tetapi hanya semiprimes.

Sunting: Terima kasih kepada Ørjan Johansen karena bermain golf 4 byte!

PHP, 82 Bytes

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

Cobalah online!

Aksioma, 105 byte

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, kode uji dan hasil

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

Di sini g (700) = 92511529 sehingga batasnya akan menjadi> 700; ww (1000) = 703999307 tetapi menggunakan nextPrime ()