Vamos atribuir os números de 0 a 94 aos 95 caracteres ASCII imprimíveis :

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

O espaço é 0, !é 1 e assim ~sucessivamente até 94. Também atribuiremos 95 à tab ( \t) e 96 à nova linha ( \n).

Agora considere a seqüência infinita cujo enésimo caractere é o caractere acima ao qual o enésimo número primo , módulo 97, foi atribuído. Vamos chamar essa string S.

Por exemplo, o primeiro número primo é 2 e 2 mod 97 é 2 e 2 é atribuído a ", então o primeiro caractere de S é ". Da mesma forma, o 30º número primo é 113 e 113 mod 97 é 16, e 16 é atribuído a 0, então o 30º caractere de S é 0.

Os primeiros 1000 caracteres de S são os seguintes:

"#%'+-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^

O Stack Exchange transforma guias em espaços, então aqui está um PasteBin com as guias intactas.

Desafio

Encontre uma substring de S que seja um programa válido no idioma de sua escolha que emita os primeiros números primos M, um por linha, em ordem , para algum número inteiro positivo M.

Por exemplo, 2é uma subcadeia de S (ocorre em vários lugares, mas qualquer 2um serve ) e é um programa CJam válido cuja saída é

2

que é o primeiro M = 1 números primos, um por linha, em ordem.

Da mesma forma, a string 2N3N5pode ser uma substring de S em algum lugar e 2N3N5é um programa CJam válido que gera

2
3
5

que é o primeiro M = 3 números primos, um por linha, em ordem.

Pontuação

A finalização com o maior M vence. O desempatador vai para a submissão postada primeiro.

Detalhes

• Não deve haver saída adicional além dos números primos em cada linha, exceto por uma nova linha à direita opcional após a última linha. Não há entrada.

• A substring pode ter qualquer comprimento, desde que finita.

• A substring pode ocorrer em qualquer lugar dentro de S. (E S pode contê-lo em vários locais).

• O programa deve ser um programa completo. Você não pode assumir que ele é executado em um ambiente REPL.

• O programa deve ser executado e finalizado em uma quantidade finita de tempo, sem erros.

• "Nova linha" pode ser interpretada como qualquer representação comum de nova linha necessária ao seu sistema / intérprete / etc. Apenas trate-o como um personagem.

Você deve fornecer o índice de S onde sua substring inicia, bem como o comprimento da substring, se não a própria substring. Você pode não apenas mostrar que a substring deve existir.

^{Relacionados: Procurando programas em uma enorme placa Boggle}

Linguagem , M = ∞

Todos os programas iniciam no início da string. O seguinte programa Python mal escrito calcula quantos caracteres são necessários para um dado M.

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)

Por exemplo, para M = 5, o programa é os primeiros 2458595061728800486379873255763299470031450306332287344758771914371767127738856987726323081746207100511846413417615836995266879023298634729597739072625027450872641123623948113460334798483696686473335593598924642330139401455349473945729379748942060643508071340354553446024108199659348217846094898762753583206697609445347611002385321978831186831089882700897165873209445730704069057276108988230177356 caracteres.

CJam, M = 2

Curto e grosso:

2NZ

Essa sequência começa na posição 54398, usando a indexação 1 da sequência. Você pode testá-lo online aqui .

Tentei procurar algumas variações possíveis, mas essa foi a primeira solução que encontrei.

Atualmente, estou tentando encontrar uma versão M = 3, mas não espero encontrar uma dentro de um período de tempo razoável. Se a sequência for uniformemente aleatória (uma aproximação), o índice inicial de uma sequência de comprimento 5 poderá ser da ordem de 10 ^ 9.