A complexidade Kolmogorov de uma sequência s é definida como o comprimento do programa mais curto P que gera s. Se o comprimento de P for menor que o comprimento de s, então se diz que s é compressível , caso contrário s é incompressível . A maioria das strings é incompressível ...

Escreva o programa mais curto que produz essa string (sem espaços e sem novas linhas):

d9 a6 b6 33 56 a7 95 4b 29 b0 ac 7f 2a aa 6d 19 b8 4b 4c f8 b6 2a ac 95 
a1 4b 4e a5 9d b3 e7 c9 4c 49 59 ec 94 b3 aa 6c 93 8f 11 5a 4d 39 75 82 
ec ea 24 cc d3 2d c3 93 38 4e b7 a6 0d d2 b5 37 23 54 ad 1b 79 aa 6e 49 
55 52 94 5a a7 3a 6a e9 e4 52 cd 2d 79 ad c6 12 b5 99 5b b4 76 51 17 4e 
94 f3 9a a2 e7 15 6a 55 14 4d 4e 4a a3 5c 2f ab 63 cc b5 a6 a4 92 96 8a 
2e c3 d8 88 9b 8c a9 16 f5 33 22 5b a2 e2 cc 1b 27 d4 e8 db 17 a4 39 85 
ca aa 5b 4f 36 24 d3 c6 f6 94 ad d7 0f 71 24 e1 b1 c5 ef 65 35 6c 8d d7 
1a 87 1e 25 df 5d c0 13 b2 6f 5a 57 28 98 bd 41 66 04 ed a2 52 c9 ac 83 
b3 6c 56 7e d1 c6 cc 53 4a 62 c5 59 a9 b2 d4 af 22 a5 a9 f4 b2 99 23 32 
f8 fb ae 48 6a 8a 9a b5 46 7a 36 59 9f 92 d3 25 b5 19 bd 8a 4a 49 62 a5 
e4 59 fb e5 ba a2 35 dd a9 36 1d a9 c9 69 89 77 6a b2 34 2d 1d 22 61 c5 
c2 66 1c e2 76 74 52 a5 d9 84 b9 8a a6 b5 14 ec 29 58 b2 bc 96 16 16 48 
f5 c5 bd 2f 32 1b 3d 4f 4b 2e b2 6b 9a d9 32 a4 4b 5c bc 92 b7 b3 26 39 
fa 42 2d 64 ed 1a 79 49 4c a3 b7 85 b2 a6 e2 8c d9 55 90 e1 a8 87 4b 60 
a6 e1 ba c4 bb ec 32 39 76 90 a6 b4 c6 65 79 61 91 aa 3d 54 b7 18 3d 15 
4b 06 db 30 8a 4d 4a a1 35 75 5d 3b d9 98 ac 55 5b 10 dd b3 e2 cc f1 5e 
b3 2b 53 90 b6 ee 2b ac 8f 88 8d 95 5a 75 df 59 2d 1c 5a 4c e8 f4 ea 48 
b9 56 de a0 92 91 a9 15 4c 55 d5 e9 3a 76 8e 04 ba e7 b2 aa e9 ab 2a d6 
23 33 45 3d c4 e9 52 e3 6a 47 50 ba af e4 e5 91 a3 14 63 95 26 b3 8b 4c 
bc aa 5a 92 7a ab ad a6 db 53 2e 97 06 6d ba 3a 66 49 4d 95 d7 65 c2 aa 
c3 1a 92 93 3f ca c2 6c 2b 37 55 13 c9 88 4a 5c 62 6b a6 ae cc de 72 94 

A saída deve se parecer com:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4e...7294

Nota: nenhuma entrada do usuário é permitida, nem acesso à Web, nem bibliotecas (exceto a necessária para imprimir a saída).

Edit I: a sequência parece aleatória ... mas acaba sendo altamente compressível, manipulando um pouco de números primos ...

Edit II: Muito bem! Analisarei as respostas nas próximas horas e depois atribuirei a recompensa. Esta é a minha ideia de como isso pode ser resolvido:

1. Se você tentar compactar os dados, não vai muito longe ...
2. Na internet, você encontra a (bem conhecida?) Enciclopédia On-Line de Sequências Inteiras (OEIS);
3. tentar os primeiros dígitos hexadecimais d9, a6, b6, 33, ...(ou sua representação decimal) não dá resultado;
4. mas se você converter os números em binário ( 1,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0) e pesquisá-los no OEIS, obterá esse resultado .
5. Como observado por Claudiu, também dei uma pequena dica na pergunta (Editar I acima) ... :-)

O vencedor é : Peter Taylor (GolfScript, 50), com uma menção especial para Claudiu (Python, 92), o primeiro que "resolveu".

GolfScript (50 bytes)

$ wc -c codegolf24909.min.gs 
50 codegolf24909.min.gs
$ md5sum codegolf24909.min.gs 
ce652060039fba071d17333a1199fd72  codegolf24909.min.gs
$ time golfscript.rb codegolf24909.min.gs 
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294

real    365m11.938s
user    364m45.620s
sys     0m6.520s

Como todo mundo agora está revelando seu código, eu também anteciparei a solicitação do OP para ocultar:

38200,{:x,{)x\%!},,2=},4/{3\{2&!!1$++}/.57>39*+}%+

Visão geral dissecção

• Calcule números primos menores que N com N = 38200: isso fornece os primeiros 4032 números primos:38200,{:x,{)x\%!},,2=},
• Queremos um bit por primo, com uma conversão hexadecimal, então divida-os em grupos de 4: 4/
• Para cada grupo, mapeie cada primo ppara p&2 != 0e faça uma conversão de base 2 em base 16: {3\{2&!!1$++}/.57>39*+}%(é aqui que estão os truques interessantes)
• Agora temos uma matriz de valores ASCII, além da string vazia de stdin; concatená-los para obter uma única sequência de saída:+

Dissecção mais detalhada da conversão de base

Dada uma pilha contendo uma string vazia e uma lista de primos, precisamos fazer duas conversões:

1. Converta cada primo em um bit indicando se é igual a 2 ou 3 (mod 4)
2. Converta os bits em dígitos hexadecimais

Existem muitas maneiras igualmente longas de fazer 1; por exemplo

{4%1>}%
{4%2/}%
{2/1&}%
{2/2%}%
{2&!!}%

ou mesmo

{2&}% followed by a 2/ after the base conversion

Para 2, a abordagem óbvia é

2base 16base{'0123456789abcdef'=}%+

Mas base é uma palavra longa e, desde 16 = 2 ⁴ , podemos salvar facilmente alguns caracteres com

4/{2base'0123456789abcdef'=}%+

Agora, o desperdício mais óbvio são os 18 caracteres dedicados a essa sequência. Nós apenas queremos uma função de dígito para código ASCII. Queremos mapear 0para '0' = 48, ..., 9para '9' = 57, 10para 'a' = 97, ... 15para 'f' = 102.

4/{2base.9>39*+48+}%+

Mas agora jogue na mistura uma proibição base. Precisamos implementá-lo nós mesmos. A implementação óbvia (nessa direção, a mais fácil) é que k baseé uma dobra {\k*+}*. A alternativa ligeiramente mais longo é uma iteração simples, que precisa de um cenário base: 0\{\k*+}/. A base 2 é um pouco especial: 1$++é equivalente ao \2*+mesmo comprimento, e eu adotei essa abordagem.

Ambos são mais longos que o 5-char 2base, mas como agora estamos iterando sobre os valores, podemos extrair a parte 1 para ter um único loop. Nós substituímos

{2&!!}%4/{2base.9>39*+48+}%+

com

4/{{2&!!1$++}*.9>39*+48+}%+

para uma boa economia de 1 caractere ou

4/{0\{2&!!1$++}/.9>39*+48+}%+

para uma perda de 1 caractere.

Mas, embora essa perda de 1 caractere pareça um passo atrás, considere o que acontece com esse 0. Ele é multiplicado por 16 e adicionado à saída de conversão base. E a última coisa que fazemos é adicionar um múltiplo de 16 à saída. Para que possamos combinar os dois como

4/{3\{2&!!1$++}/.57>39*+}%+

A menor articulação e a esperteza do bônus a tornam mais interessante.

Python, 92 caracteres

Aqui estão senhoras e senhores, o próprio código!

>>> code = "R=range;print hex(int(''.join(`i/2%2`for i in R(38198)if all(i%x for x in R(2,i))),2))[2:-1]"
>>> len(code)
92
>>> exec code
d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294
>>> import hashlib; hashlib.sha256(code).hexdigest()
'60fa293bbe895f752dfe208b7b9e56cae4b0c8e4cdf7c5cf82bf7bab60af3db6'

Marzio deixou uma dica inteligente dizendo que "é altamente compressível manipular um pouco dos números primos". Eu tinha certeza de que o "pouco" não estava em itálico por acidente, então converti a sequência hexadecimal em bits e tentei encontrar padrões. Eu pensei que no começo ele estava representando todos os números primos como bits e concatenando-os juntos, mas isso não deu certo. Então talvez pegue apenas alguns dígitos ou solte todos os zeros na cadeia de bits - ainda não. Talvez seja uma sequência de bits do bit menos significativo dos primeiros primos? Não é bem assim. Mas, eventualmente, encontrei o que funcionava - é uma sequência de bits do segundo bit menos significativo dos primeiros números primos.

Portanto, meu código faz exatamente isso: gerar números primos suficientes, pegar o segundo bit de cada ( i/2%2), concatená-los como uma sequência binária, depois convertê-lo em base-10 ( int(..., 2)) e depois em base-16 ( hex(...)).

Haskell, 105

Hash SHA1: a24bb0f4f8538c911eee59dfc2d459194ccb969c

Saída:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c26b275513c9884a

Editar: Código:

import Numeric;f(x:z)s=f[y|y<-z,0/=mod y x]$s*2+quot(mod x 4)2;f[]s=s;main=putStr$showHex(f[2..38198]0)""

Eu errei a regra de não usar nenhuma função da biblioteca, exceto a impressão (putStr). Eu diria que operadores matemáticos, embora tecnicamente funcionem, são permitidos.

C, 136 116 109 103 caracteres

OK, então, aqui está o meu esforço:

i;p;q;main(n){for(;n++,q<4032;){for(i=1;++i<n&&n%i;);if(i==n)p+=p+(n&2)/2,p=++q&3?p:printf("%x",p)*0;}}

MD5 hash = f638552ef987ca302d1b6ecbf0b50e66

JS, 764

se considerarmos essa sequência como base64, podemos ter uma versão menor usando a versão un-base-64-ed:

btoa("wÖºo­÷离÷ÛÖôiÎßÙ¦éÝ}oÎáÇüo­iÏyk^áæ¹õÖ÷{·=áÎ=ç×÷÷i®÷×^ZáÝýï6yÇÛw}swßÎo¶ºÑ×voûÛ~xiÝ[ïÖéî=çv÷Zk½Ú駽{vqÝïÖs­vo}å¶øï®u×¾÷÷õ¦¶{½yé®y×áîk~\Ùöëwoºkv÷¯Ùç7wÏ<õ¿kÝz÷Ûn[kg¶qÍ[Û·x{Ç[׶¸ßß9q¦å¾ß­¸ww:¯xi×{ÑþõÛµoW9yþ¹ßñ×{Õ¯;Õí¹uþ]sMwonå®{ÛÏ|mÞ5ë­8yÖ¶çg=iÏ7o~ç®ÞwW:qÎw᮶s}kÖöwÛf¹k×øoo}Û}öÇÛiî<é¯õ¦ùã®Úß®}õÿvw}¹o}mßá®=ëf¹{}}·¹m¦¶ß]kÝúÕÖ½sÞ½óÞûé¦ößÕݶëW9snºÕǶï®øçf¹wß8oßk¦ù×ÛÞ|ofÜ÷­z×®<9mÝßm[ÝÞá½onõ§}ßf¸á¾\mÏvo¶÷Û­ý}®6ÙÞ¸yÝZïÞ=áÆ·o¿9ofº{owÞy÷GµkÏ;á¾´k§µm§8m·ßmýï¯tk¦øs®¹ïÞµ÷VÝÞxo½|ÝÝyá½:u½ôñ®á¦µßùåÝÛwß|iÎyå½tuÖ÷{g^^o}çto§Ù¶ñÿ<ñßyå®ùuþ}ÙÝ\å®{Çøy®<oÞzuæ´÷oukÝyáÎyw½Ý®úñí8m§»of{ÖÙ§zÛ}÷ãÝs½çg·é®;çFÚi÷¸{uk}xëyÛ¦÷ñ¾mÆå¯ví¦iÖºu¾wÙï{Ó®m­Úë®=áßyw¾¹sfs}Z÷owÝ÷snÙ½ûçwsß<á®\ënk¦qÇ^ïox")

Mas acho que o autor quer que encontremos a lógica por trás dessa sequência não aleatória.

Mathetmatica - 56

O mistério já está resolvido, então apenas implemente a ideia

⌊.5Prime@Range@4032⌋~Mod~2~FromDigits~2~IntegerString~16

J - 46 char

Não se importe comigo, basta registrar o J golf aqui para posteridade. Não foi inteligente o suficiente para descobrir o truque.

4[1!:2&4'0123456789abcdef'{~#.2|<.-:p:i.1007 4

Explicado:

• p:i.1007 4- Crie uma matriz de 1007 linhas e 4 colunas com números inteiros a partir de 0 e, em seguida, pegue os números primos correspondentes a esses números inteiros. Sim, p:é um J embutido. Sim, somos quatro primos curtos.

• 2|<.-:- Divida pela metade cada número ( -:), coloque-o no chão ( <.) e pegue o módulo 2 ( 2|). É o mesmo que pegar o bit significativo do próximo arrendamento.

• #.- Converta cada linha do resultado da base 2 em um número inteiro. Isso nos dá 1007 números de 0 a 15, inclusive.

• '0123456789abcdef'{~#.- Pegue cada linha dessa matriz de bits como o binário de um número e use esse número para selecionar na lista de dígitos hexadecimais. Isso converte a cada quatro bits no hexadecimal.

• 1!:2&4- O intérprete J tem um problema com a saída de strings com mais de 256 caracteres, portanto, temos que enviar esses dados diretamente para o stdout. Você ganha um pouco, perde um pouco.

• 4[- Finalmente, descarte o resultado 1!:2e, em vez disso, produza os 4 ausentes da saída. Fazemos isso porque é mais curto do que incluir os últimos quatro números primos e retornar um resultado vazio aqui.

JS, 503

Seguindo a ideia @xem:

s='Ù¦¶3V§K)°¬*ªm¸KLø¶*¬¡KN¥³çÉLIY쳪lZM9uìê$ÌÓ-Ã8N·¦\nÒµ7#T­yªnIURZ§:jéäRÍ-y­Æµ[´vQNó¢çjUMNJ£\/«c̵¦¤.ÃØ©õ3"[¢âÌ'+"'"+'ÔèÛ¤9ʪ[O6$ÓÆö­×q$á±Åïe5l×%ß]À²oZW(½Afí¢Rɬ³lV~ÑÆÌSJbÅY©²Ô¯"¥©ô²#2øû®HjµFz6YÓ%µ½JIb¥äYûåº\n5Ý©6©Éiwj²4-"aÅÂfâvtR¥Ù¹¦µì)X²¼HõŽ/2=OK.²kÙ2¤K\¼·³&9úB-díyIL£·²¦âÙUá¨K`¦áºÄ»ì29v¦´Æeyaª=T·=KÛ0MJ¡5u];Ù¬U[ݳâÌñ^³+S¶î+¬ZußY-ZLèôêH¹VÞ ©LUÕé:vºç²ªé«*Ö#3E=ÄéRãjGPº¯äå£c&³L¼ªZz«­¦ÛS.mº:fIM×eªÃ?ÊÂl+7UÉJ\bk¦®ÌÞr'
r=''
for(var i=0;i<s.length;i++) r+=s.charCodeAt(i).toString(16);
console.log(r)

Mathematica, 55

Prime~Array~4031~BitAnd~2~FromDigits~2~IntegerString~16

Testado no Mathematica 8. Isso faz uso de duas observações:

• O Mathematica FromDigitsnão verifica realmente o intervalo de dígitos fornecido, portanto, se você o aplicar a uma lista do formulário, {2,0,2,2,0,...}obterá o dobro do resultado como se estivesse aplicando {1,0,1,1,0,...}. Mas essa é exatamente a forma gerada peloBitAnd números primos com 2.
• O último bit do número cuja representação hexadecimal queremos é zero (como evidenciado pela sequência que termina em um dígito par), então é apenas duas vezes o número que você obteria com um primo a menos. Mas um fator de dois é exatamente o que obtemos ao usar a observação anterior, para que tudo se encaixe perfeitamente.