Menemukan Program di Primes

9

Mari kita berikan angka 0 hingga 94 ke 95 karakter ASCII yang dapat dicetak :

 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

Spasi adalah 0, !adalah 1, dan seterusnya hingga ~94. Kami juga akan menetapkan 95 ke tab ( \t) dan 96 ke baris baru ( \n).

Sekarang perhatikan string tanpa batas yang karakter N-nya adalah karakter di atas yang telah ditentukan oleh bilangan prima N , modulo 97. Kami akan memanggil string ini S.

Sebagai contoh, bilangan prima pertama adalah 2, dan 2 mod 97 adalah 2, dan 2 ditugaskan ", sehingga karakter pertama S adalah ". Demikian pula, bilangan prima 30 adalah 113, dan 113 mod 97 adalah 16, dan 16 ditugaskan untuk 0, sehingga karakter 30 S adalah 0.

1000 karakter S pertama adalah sebagai berikut:

"#%'+-137=?EIKOU[]cgiosy $&*,0>BHJTV\bflrt~
#%1=ACGMOY_ekmswy"046:HNXZ^dlrx|!)-5?AKMSW]eiko{"&.28DFX^hntv|%+139?CEQ[]agmo{  $,6>HPV\`hnrz~+5ACMOSU_mqsw$(*.BFNX`djp~!'-5;GKQS]_eoq{}"48:>DJRX^tv
'17=EQU[aciu    026<>DHJNZ\b#)/7ISaegkqy}   $0:<@BFLXdlx~!'/3;?MQWY]ceku(.24LPR\hjt|!'-?EIKWamu$28<>BDNZ`fxz)+AGOUY[_gmwy"0:@LNRT^jl|~#')3;Meiow&(,4DFJRX^bnp%+-37=KQUW]agsy    ,06BJPTn
)15;=CYegw  ".<FHLTZ`dfjpx|~#-/9AES]ikquw&48>FLPbjtz
'1=KOU[]y{$,0>BJV\hlr%/1A[_amsw"(04<RTXZf!#)/59?AMQ]_ik{},2FV^bdhj
'39CEIOQWacoy{$28<BJPVfrtx%+/7AIOUkqs}*.4FHR`dfp~!);?EGKQS_cw,8:>DJLRhjp
%139EUW[aosu&>HNPZ\fhrxz#%/5=[egqy  (:@LXZlrv|!35?MSWY]uw"(8@FL^nptz|!'17COacim &>BDHNP\`n+5;GU[eqsw}$*46:HNTX^`jl|'/AEKWY_ek&,:>FPXdvz|
7CIK[agu    ,0NTZ`hnrt
%)+1GMOSegkwy   "<BHLT^~-/59;?AKY_cku{.24:X\dntz!'37=?EIOQ[]ms&*6D`fz~/7=AGU[akmw"*46@HT^vx|#)-5GQW]_eo{}&,28@FPVX^djt|39OQcgoy6>PTV`fhnr#+7IY_ams} (*0:HLdfvx!#-AEGKScioq},48>\^hjptz
'-1=CKW[iu  6<HNPfn
)/=ACIS[aek(6@BNXZjl~5GM]ouw(,24>FPV\dhnpz|'+179EIWims&*28<DHV\`nz~
=AY_eq}*046:LR^

Stack Exchange mengubah tab menjadi spasi, jadi inilah PasteBin dengan tab yang utuh.

Tantangan

Temukan substring S yang merupakan program yang valid dalam bahasa pilihan Anda yang menampilkan bilangan prima M pertama, satu per baris, secara berurutan , untuk beberapa bilangan bulat positif M.

Misalnya, 2adalah substring S (terjadi di beberapa tempat tetapi ada yang akan melakukannya), dan 2merupakan program CJam yang valid yang outputnya adalah

2

yang merupakan M pertama = 1 bilangan prima, satu per baris, secara berurutan.

Demikian pula, string 2N3N5dapat berupa substring S di suatu tempat, dan 2N3N5merupakan program CJam yang valid yang menghasilkan

2
3
5

yang merupakan M pertama = 3 bilangan prima, satu per baris, secara berurutan.

Mencetak gol

Pengajuan dengan M tertinggi menang. Tie breaker pergi ke kiriman yang diposting terlebih dahulu.

Detail

  • Seharusnya tidak ada output tambahan selain bilangan prima tunggal pada setiap baris, kecuali untuk baris tambahan opsional setelah baris terakhir. Tidak ada input.

  • Substring mungkin panjangnya sepanjang itu terbatas.

  • Substring dapat terjadi di mana saja di dalam S. (Dan S dapat memuatnya di banyak tempat.)

  • Program harus merupakan program yang lengkap. Anda mungkin tidak menganggap itu dijalankan di lingkungan REPL.

  • Program harus dijalankan dan diakhiri dalam jumlah waktu terbatas tanpa kesalahan.

  • "Baris baru" dapat diartikan sebagai representasi baris baru umum yang diperlukan untuk sistem Anda / juru bahasa / dll. Perlakukan saja sebagai satu karakter.

Anda harus memberikan indeks S di mana substring Anda mulai, serta panjang substring jika bukan substring itu sendiri. Anda mungkin tidak hanya menunjukkan bahwa substring harus ada.

Terkait: Mencari program di papan Boggle besar

Hobi Calvin
sumber
1
Bisakah Anda memberikan kode untuk menghasilkan string besar hingga sejumlah karakter? (Saya kira Anda sudah memilikinya)
Pengoptimal
Jika ada 95 karakter ASCII yang dapat dicetak, mengapa Anda melakukan modulo 97? Ah tidak apa-apa, Anda juga menggunakan tab dan baris baru.
Aditsu berhenti karena SE adalah JAHAT
Menimbang bahwa 0 mod 97 hanya dapat terjadi sekali, kurangnya ruang benar-benar menyakitkan ...
Sp3000
@ Sp3000 Tembak, itu tidak terjadi pada saya. : /
Calvin Hobbies

Jawaban:

18

Bahasa , M = ∞

Semua program dimulai pada awal string. Program Python yang ditulis dengan buruk ini menghitung berapa banyak karakter yang diperlukan untuk M. yang diberikan

def program_length(n):
    PLUS, MINUS, DOT = '000', '001', '100'
    i = 1
    s = ''
    while n > 0:
        i += 1
        if all(i%f for f in range(2,i)): 
            s += str(i) + '\n'
            n -= 1
    out = '110111'
    ch = 0
    for c in s:
        dif = ord(c) - ch
        if dif > 0: out += PLUS * dif
        else: out += MINUS * -dif
        out += DOT
        ch = ord(c)
    return int(out, 2)

Sebagai contoh, untuk M = 5, program ini adalah yang pertama 2458595061728800486379873255763299470031450306332287344758771914371767127738856987726323081746207100511846413417615836995266879023298634729597739072625027450872641123623948113460334798483696686473335593598924642330139401455349473945729379748942060643508071340354553446024108199659348217846094898762753583206697609445347611002385321978831186831089882700897165873209445730704069057276108988230177356 karakter.

feersum
sumber
Jika ragu, ada varian BF yang akan melakukannya untuk Anda.
ymbirtt
3
Lucu bagaimana bahasa terinspirasi oleh tantangan saya yang lain. Sepertinya saya membawa kejatuhan saya sendiri.
Calvin Hobi
3

CJam, M = 2

Pendek dan manis:

2NZ

Urutan ini dimulai pada posisi 54398, menggunakan 1-indexing dari string. Anda dapat mengujinya secara online di sini .

Saya mencoba mencari beberapa variasi yang mungkin, tetapi ini adalah solusi pertama yang saya temukan.

Saat ini saya mencoba untuk menemukan versi M = 3, tetapi saya tidak berharap untuk menemukannya dalam jangka waktu yang wajar. Jika urutannya adalah acak acak (perkiraan), maka indeks awal untuk urutan panjang 5 bisa berada di urutan 10 ^ 9.

PhiNotPi
sumber
Terverifikasi: 1e6{mp},97f%' f+"2NZ"# tautan (butuh waktu: p)
aditsu berhenti karena SE adalah JAHAT