Prime Terkecil dengan Twist (A068103)

33

Tugas yang dihadapi adalah, diberi nomor n, menemukan bilangan prima terkecil yang dimulai dengan SETIDAKNYA n angka 2di awal bilangan. Ini adalah urutan yang saya temukan di OEIS ( A068103 ).

17 angka pertama dalam urutan diberikan di bawah ini, jika Anda ingin lebih, saya harus benar-benar pergi mengimplementasikan urutan, yang saya tidak keberatan lakukan.

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

Hanya berpikir ini akan menjadi kombinasi yang keren dari manipulasi string, deteksi prima dan urutan. Ini adalah , jumlah byte terendah akan dinyatakan sebagai pemenang mungkin di akhir bulan.

Guci Gurita Ajaib
sumber
5
Apakah ada batas bawah seberapa tinggi input yang harus kita dukung?
ETHproduk
1
Apakah ada batasan waktu?
Brad Gilbert b2gills
@ ETHProduk maaf, pergi agak cepat setelah menulis yang ini. Jika Anda harus membatasi input Anda, batasan harus didukung dengan argumen logis mengapa bahasa tidak mendukung angka lebih tinggi dari x. Misalnya jika bahasa Anda hanya mendukung bilangan bulat 32-bit, Anda dapat menjelaskannya.
Magic Gurita Guci

Jawaban:

12

Brachylog , 12 11 byte

:2rj:Acb#p=

Cobalah online!

Ini secara mengejutkan diterjemahkan ke dalam Brachylog. Ini adalah fungsi, bukan program penuh (walaupun memberikan penerjemah Zsebagai argumen baris perintah menyebabkannya menambahkan pembungkus yang sesuai untuk membuat fungsi menjadi program; itulah yang saya lakukan untuk membuat tautan TIO berfungsi). Sangat disayangkan bahwa jtampaknya -1-diindeks dan perlu koreksi untuk memungkinkannya.

Anda dapat membuat argumen yang masuk akal bahwa hal =itu tidak perlu, tetapi saya berpikir bahwa mengingat bagaimana masalahnya, itu adalah; tanpa, fungsi menggambarkan himpunan semua bilangan prima yang dimulai dengan angka 2s yang diberikan , dan tanpa beberapa pernyataan eksplisit bahwa program harus melakukan sesuatu dengan deskripsi ini (dalam hal ini, menghasilkan nilai pertama), mungkin tidak mematuhi spesifikasi.

Penjelasan

: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

Ketika digunakan sebagai fungsi yang mengembalikan integer, tidak ada yang pernah meminta nilai melewati yang pertama, jadi yang pertama adalah yang harus kita khawatirkan.

Satu kehalusan (ditunjukkan dalam komentar): :Acbdan b:Acsecara matematis setara (karena satu menghapus dari awal dan yang lain menambah akhirnya, dengan wilayah di antaranya tidak pernah tumpang tindih); Saya sebelumnya punya b:Ac, yang lebih alami, tetapi rusak pada input 0 (yang saya duga adalah karena cmenolak untuk menyatukan daftar kosong untuk apa pun; banyak Brin bawaan bawaan cenderung untuk memecah daftar kosong untuk beberapa alasan). :Acbmemastikan bahwa ctidak perlu melihat daftar kosong, yang berarti bahwa kasus input 0 sekarang dapat berfungsi juga.


sumber
@uddyfish: Ya. Namun, itu tidak berhasil 0, tanpa alasan yang jelas (Brachylog tampaknya alergi terhadap nol karena beberapa alasan; saya menduga yang cbertanggung jawab). Yang mengatakan, itu cukup mudah untuk diperbaiki, jadi saya akan memperbaikinya sekarang.
b:Actidak berfungsi karena untuk input 0Anda mendapatkan 2b:Ac: 2bmemberi 0dan Anda tidak dapat menggunakan cdengan nol di depan. Alasan untuk ini adalah untuk menghindari loop tak terbatas dalam kasus umum di mana Anda selalu bisa menambahkan nol dan memiliki hasil yang sama.
Fatalkan
Juga, Anda dapat mempersingkat ini dengan satu byte dengan menulis :2rjalih-alih,2:?j
Fatalize
Saya lupa tentang r; itu hanya perbaikan biasa. Saya mengerti apa yang terjadi c(Anda tidak ingin banyak hasil ketika dijalankan mundur); namun, peningkatan yang mungkin terjadi adalah untuk tidak mengizinkan input yang merosot hanya jika mereka tidak terikat, sementara memungkinkan mereka ketika input sudah terikat pada nilai yang merosot.
Ini pasti bisa dilakukan dan saya akan menambahkannya di pelacak Github. Meskipun implementasi concatenate sudah hampir 100 baris panjang yang banyak untuk predikat Prolog.
Fatalkan
15

Java (OpenJDK 8) , 164 110 byte

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

Terima kasih kepada @FryAmTheEggman untuk banyak byte!

Cobalah online!

Pavel
sumber
2
Bisakah Anda menjelaskan bagaimana regex pengecekan bekerja?
J. Antonio Perez
Saya tidak punya ide. Itu bukan milikku, dan aku tidak tahu siapa pencipta aslinya. Aku barusan butuh string dengan panjang n dan cocok jika n tidak prima.
Pavel
Apakah Anda tahu apa sumber aslinya? Di mana Anda belajar tentang itu? Sudahkah Anda menguji kode Anda?
J. Antonio Perez
3
@Pavel Regex pengecekan keutamaan membuat jawaban ini luar biasa, bahkan jika Anda tidak berhasil. Anda harus menambahkannya ke utas "Kiat Golf di Jawa".
Magic Gurita Guci
3
Saya tidak dapat menguji kode sekarang tapi saya cukup yakin regex bekerja seperti ini: new String(new char[i]))membuat string panjang unary sama dengan angka. Kemudian regex cocok dengan angka gabungan dengan memeriksa apakah pengulangan satu set angka cocok dengan seluruh string (pada dasarnya divisi percobaan). Jika saya benar, itu berarti Anda harus bisa bermain golf bagian kedua untuk tidak memilikinya ?, saya akan memberi tahu Anda dengan pasti ketika saya sampai di komputer.
FryAmTheEggman
5

Pyth, 12 byte

f&!x`T*Q\2P_

Dalam pseudocode:

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

Ulangi lambdamulai dari T=1, bertambah 1 hingga kondisi terpenuhi. String 2s harus berupa substring dari awal string, yaitu metode indeks harus kembali 0. Jika substring tidak ditemukan maka ia akan kembali -1yang dengan nyaman juga benar, sehingga tidak ada kasus luar biasa.

Anda dapat mencobanya secara online di sini , tetapi server hanya mengizinkan input 4.

busukxuan
sumber
4

Perl, 50 byte

49 byte kode + -pbendera.

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

Masukkan input tanpa baris akhir final. Contohnya:

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

Ini membutuhkan waktu beberapa saat untuk menjalankan angka yang lebih besar dari 4 karena menguji setiap angka (ada 2 tes: yang pertama /^2{$_}/memeriksa apakah ada cukup 2 di awal, dan yang kedua (1x$\)!~/^1?$|^(11+)\1+$/menguji primality (dengan kinerja yang sangat buruk)).

Dada
sumber
3

Haskell, 73 byte

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

Contoh penggunaan: f 3-> 2221.

Paksaan. [1..n]>>"2"membuat daftar n 2s yang dibandingkan dengan nkarakter pertama dalam representasi string dari prime saat ini.

nimi
sumber
3

Mathematica, 103 byte

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

Fungsi tanpa nama mengambil argumen integer non-negatif #dan mengembalikan integer. Ini benar-benar menguji semua bilangan bulat positif pada gilirannya sampai ia menemukan satu yang keduanya dimulai dengan #2s dan prima. Sangat lambat untuk input di atas 5.

hasil sebelumnya: Mathematica, 155 byte

Mathematica akan lebih baik untuk bermain golf jika tidak diketik dengan kuat; kita harus secara eksplisit beralih antara tipe 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&

Algoritma ini beroperasi pada daftar digit , anehnya, dimulai dengan {2,...,2,1}. Selama itu bukan digit dari bilangan prima itu menambahkan satu ke digit terakhir, menggunakan aturan {j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}... dan kemudian secara manual mengimplementasikan membawa-satu-ke-the-digit berikutnya selama salah satu digit sama dengan 10, menggunakan aturan {a__,b_,10,c___}->{a,b+1,0,c}... dan kemudian, jika kita sudah sejauh ini sehingga yang terakhir dari yang 2s telah berubah menjadi 3, mulai lagi dengan digit lain di ujungnya, menggunakan aturan {a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}. Pada /. 23->2akhirnya hanya memperbaiki kasus khusus di mana inputnya adalah 1: kebanyakan bilangan prima tidak dapat berakhir 2, tetapi 2bisa. (Beberapa kesalahan diludahkan pada input 0dan 1, tetapi fungsi menemukan jalannya ke jawaban yang benar.)

Algoritma ini cukup cepat: sebagai contoh, pada laptop saya dibutuhkan kurang dari 3 detik untuk menghitung bahwa prime pertama dimulai dengan 1.000 2s 22...220521.

Greg Martin
sumber
2

Pyth, 17 byte

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

Tampaknya tidak dapat menyelesaikannya n = 4secara daring, tetapi secara teori memang benar.

Penjelasan

               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.
PurkkaKoodari
sumber
2

Perl 6 , 53 byte

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

Cobalah

Diperluas:

{
  ( $/ = 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..*
}
Brad Gilbert b2gills
sumber
2

Pyke, 14 byte

.fj`Q\2*.^j_P&

Coba di sini!

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

12 byte setelah perbaikan bug dan fitur baru

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

Coba di sini!

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

Sage, 69 68 byte

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

Menggunakan generator untuk menemukan yang pertama (dari yang terkecil) dari banyak istilah yang tak terhingga.

busukxuan
sumber
2

Japt, 20 byte

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

Uji secara online! Ini selesai dalam dua detik pada mesin saya untuk semua input hingga 14, dan setelah itu secara alami kehilangan presisi (JavaScript hanya memiliki presisi integer hingga 2 53 ).

Banyak terima kasih kepada @obarakon untuk mengerjakan ini :-)

Penjelasan

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

Dalam versi terbaru Japt, ini bisa 12 byte:

_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

Uji secara online! Selesai dalam setengah detik pada mesin saya untuk semua input hingga 14.

Produksi ETH
sumber
Solusi hebat!
Oliver
Ini gagal pada input 5, karena Anda tidak pernah menguji 2222203, hanya 222223dan segera sesudahnya 2222210. Ini juga gagal pada input apa pun yang membutuhkan tiga atau lebih digit tambahan setelah string 2s, seperti input 15.
Greg Martin
@GregMartin Darn, kau benar. Diperbaiki dengan biaya 5 byte.
ETHproduksi
Ini memperbaiki kasus uji, tetapi algoritme masih mengasumsikan bahwa seseorang tidak perlu menambahkan lebih dari tiga digit untuk menemukan yang prima, yang bisa salah untuk input yang lebih besar.
Greg Martin
@GregMartin Ini berfungsi untuk semua kasus uji hingga 14, dan JS mengalami masalah presisi bilangan bulat pada kasus 15. Saya tidak berpikir algoritme harus secara teori benar melewati 2 ^ 53, tapi mungkin saya salah ...
ETHproduksi
2

PHP, 76 byte

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

mengambil input dari argumen baris perintah. Jalankan dengan -r.

kerusakan

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)
Titus
sumber
1

Bash (+ coreutils), 53 byte

Bekerja hingga 2 ^ 63-1 (9223372036854775807) , membutuhkan banyak waktu untuk menyelesaikan untuk N> 8.

Golf

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

Uji

>seq 0 7|xargs -L1 ./twist

2
2
223
2221
22229
2222203
22222223
22222223
zeppelin
sumber
1

Python 3, 406 byte

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

kode uji

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

hasil tes

 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

Saya memutuskan untuk mencari kecepatan pada rentang yang cukup besar, daripada ukuran byte. :) Saya menggunakan tes primality Miller-Rabin deterministik yang dijamin hingga 3317044064679887385961981 dengan set saksi ini. Bilangan prima yang lebih besar akan selalu berhasil lulus tes, tetapi beberapa komposit juga dapat lulus, meskipun kemungkinannya sangat rendah. Namun, saya juga menguji angka output untuk i> 22 menggunakan pyecm sebuah program faktorisasi Kurva Elliptic, dan mereka tampaknya prima.

PM 2Ring
sumber
1
Pertama: pengajuan harus memiliki peluang 1 peluang untuk mendapatkan hasil yang benar. kedua, ini codegolf, jadi Anda benar-benar harus pergi untuk ukuran byte. Selain itu, bagus
Destructible Lemon
1
@DestructibleWatermelon Terima kasih! Poin wajar tentang pergi untuk ukuran byte. Saya kira saya bisa sebaris p()panggilan ... OTOH, akan sulit untuk menulis program yang secara signifikan lebih kecil yang dapat memberikan hasil yang benar untuk i> 20 dalam waktu kurang dari satu detik (yang tidak "menipu" dengan memanggil built-in pemeriksa primality). :)
PM 2Ring
Banyak program tidak dapat menangani angka 33 digit (n: = 30). Mengingat standar emas OP naik menjadi 18 digit saja dan tidak ada batasan yang ditentukan olehnya, masuk akal untuk mengasumsikan bahwa n: = 30 adalah IMO yang cukup baik.
user3819867
@ PM2Ring Tidak perlu berada di "di bawah satu detik". Buat kodenya sesingkat mungkin, dan abaikan kecepatannya sama sekali. Itulah semangat [kode-golf]. Saya akan mengubah downvote saya menjadi upvote setelah di-golf.
mbomb007
sebenarnya, jika memang menghasilkan output yang benar hingga batas, maka jawabannya bekerja dengan probabilitas satu.
Lemon Destructible
1

Python 3, 132 byte

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

Setiap harapan kinerja telah dikorbankan untuk jumlah byte yang lebih kecil.

cdlane
sumber
-1

Java, 163 byte

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

kode uji

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

keluaran:

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 milidetik

Penjelasan: loop atas bilangan bulat dan menambahkannya sebagai string ke string root, yang merupakan string "2's" yang diberikan, dan memverifikasi apakah itu prima atau tidak.

SamCle88
sumber
3
isProbablePrimememiliki positif palsu sesekali . Itu akan membatalkan jawaban, karena ada keadaan di mana ia mengembalikan nilai yang salah.
Probabilitas kesalahan kurang dari 2 ^ -99 (lihat dokumentasi ).
SamCle88
@ SamCle88 probabilitas kecil atau tidak, ini salah pada masalah teknis. isProbablePrime tidak dapat diterima untuk verifikasi prima dan telah ditolak karena tantangan lain.
Guci Gurita Ajaib