La complexité de Kolmogorov d'une chaîne s est définie comme la longueur du programme P le plus court qui génère s. Si la longueur de P est plus courte que la longueur de s, alors s est dit compressible , sinon s est incompressible . La plupart des cordes sont incompressibles ...

Écrivez le programme le plus court qui génère cette chaîne (sans espaces et sans retours à la ligne):

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 

La sortie devrait ressembler à:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4e...7294

Remarque: aucune entrée utilisateur n'est autorisée, ni accès Web, ni bibliothèques (sauf celle requise pour l'impression de la sortie).

Edit I: la séquence semble aléatoire ... mais elle s'avère être très compressible en manipulant un peu de nombres premiers ...

Edit II: Bravo! Je vais revoir les réponses dans les prochaines heures, puis attribuer la prime. Voici mon idée sur la façon dont cela pourrait être résolu:

1. Si vous essayez de compresser les données, vous n'allez pas loin ...
2. Sur Internet, vous pouvez trouver l' Encyclopédie en ligne (bien connue?) Des séquences entières (OEIS);
3. essayer les premiers chiffres hexadécimaux d9, a6, b6, 33, ...(ou leur représentation décimale) ne donne aucun résultat;
4. mais si vous convertissez les nombres en binary ( 1,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0) et les recherchez sur OEIS, vous obtenez ce résultat .
5. Comme l'a noté Claudiu, j'ai également donné un petit indice dans la question (Edit I ci-dessus) ... :-)

Le gagnant est : Peter Taylor (GolfScript, 50), avec une mention spéciale pour Claudiu (Python, 92), le premier qui l'a "résolu".

GolfScript (50 octets)

$ 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

Étant donné que tout le monde révèle maintenant son code, je vais également anticiper la demande d'OP de désobscurcir:

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

Vue d'ensemble de la dissection

• Calculer des nombres premiers inférieurs à N avec N = 38200: cela donne les premiers 4032 nombres premiers:38200,{:x,{)x\%!},,2=},
• Nous voulons un bit par prime, avec une conversion hexadécimale, alors divisez-les en groupes de 4: 4/
• Pour chaque groupe, chaque carte de choix ppour p&2 != 0, et faire une base-2 à la conversion de base-16: {3\{2&!!1$++}/.57>39*+}%(c'est là que les astuces intéressantes sont)
• Nous avons maintenant un tableau de valeurs ASCII, plus la chaîne vide de stdin; les concaténer pour obtenir une seule chaîne de sortie:+

Dissection plus détaillée de la conversion de base

Étant donné une pile contenant une chaîne vide et une liste de nombres premiers, nous devons effectuer deux conversions:

1. Convertir chaque nombre premier en un bit indiquant s'il est égal à 2 ou 3 (mod 4)
2. Convertissez les bits en chiffres hexadécimaux

Il existe de nombreuses façons tout aussi longues de faire 1; par exemple

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

ou même

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

Pour 2, l'approche évidente est

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

Mais base est un long mot, et comme 16 = 2 ^4, nous pouvons facilement enregistrer quelques caractères avec

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

Maintenant, le gaspillage le plus évident est les 18 caractères consacrés à cette chaîne. Nous voulons juste une fonction du chiffre au code ASCII. Nous voulons mapper 0sur '0' = 48, ..., 9sur '9' = 57, 10sur 'a' = 97, ... 15sur 'f' = 102.

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

Mais maintenant, jetez dans le mélange une interdiction base. Nous devons le mettre en œuvre nous-mêmes. La mise en œuvre évidente (dans ce sens, la plus simple) est qu'il k bases'agit d'un pli {\k*+}*. L'alternative un peu plus longue est une itération simple, qui a besoin d' un cas de base: 0\{\k*+}/. La base 2 est légèrement spéciale: 1$++équivaut à \2*+pour la même longueur, et j'ai adopté cette approche.

Les deux sont plus longs que les 5 caractères 2base, mais comme nous parcourons maintenant les valeurs, nous pouvons tirer dans la partie 1 pour avoir une seule boucle. Nous remplaçons

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

avec

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

pour une belle économie de 1 caractère, ou

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

pour une perte de 1 caractère.

Mais bien que cette perte de 1 caractère ressemble à un pas en arrière, considérez ce qui arrive à ce 0. Il est multiplié par 16 et ajouté à la sortie de conversion de base. Et la dernière chose que nous faisons est d'ajouter un multiple de 16 à la sortie. Nous pouvons donc combiner les deux comme

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

Le joint le plus court et l'intelligence bonus le rendent plus intéressant.

Python, 92 caractères

Ici, c'est mesdames et messieurs, le code lui-même!

>>> 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 a laissé un indice intelligent en disant que "il se révèle être très compressible peu de nombres premiers". J'étais sûr que le "petit" n'était pas en italique par accident, alors j'ai converti la chaîne hexadécimale en bits et j'ai essayé de trouver des modèles. Je pensais qu'au début, il représentait tous les nombres premiers sous forme de bits et les concaténait ensemble, mais cela n'a pas fonctionné. Alors peut-être en ne prenant que quelques chiffres, ou en supprimant tous les zéros dans la chaîne de bits - toujours non. C'est peut-être une chaîne de bits du bit le moins significatif des premiers nombres premiers? Pas assez. Mais finalement, j'ai trouvé celui qui a fonctionné - c'est une chaîne de bits du deuxième bit le moins significatif des premiers nombres premiers cependant nombreux.

Donc, mon code fait exactement cela: générer juste assez de nombres premiers, prendre le deuxième bit de each ( i/2%2), les concaténer comme une chaîne binaire, puis le convertir en base-10 ( int(..., 2)) puis en base-16 ( hex(...)).

Haskell, 105

Hachage SHA1: a24bb0f4f8538c911eee59dfc2d459194ccb969c

Sortie:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba4

Modifier: Code:

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)""

J'ai raté la règle de ne pas utiliser de fonctions de bibliothèque, sauf pour l'impression (putStr). Je suppose que les opérateurs mathématiques, bien qu'ils soient techniquement des fonctions, sont autorisés.

C, 136 116 109 109 103 caractères

OK alors, voici mon effort:

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

si nous considérons cette chaîne comme base64, nous pouvons avoir une version plus petite en utilisant la version non-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")

Mais je pense que l'auteur veut plutôt que nous trouvions la logique derrière cette chaîne non aléatoire.

Mathetmatica - 56

Le mystère est déjà résolu, il suffit donc de mettre en œuvre l'idée

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

J - 46 car

Ne me dérange pas, je connecte juste le J golf ici pour la postérité. Ce n'était pas assez intelligent pour comprendre l'astuce.

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

A expliqué:

• p:i.1007 4- Créez une matrice de 1007 lignes et 4 colonnes des nombres entiers à partir de 0, puis prenez les nombres premiers correspondant à ces nombres entiers. Oui, p:est un J intégré. Oui, nous manquons de quatre nombres premiers.

• 2|<.-:- Divisez par deux chaque nombre ( -:), posez-le au sol ( <.) et prenez ce module 2 ( 2|). C'est la même chose que de prendre le bit significatif suivant.

• #.- Convertissez chaque ligne du résultat de la base 2 en un entier. Cela nous donne 1007 numéros de 0 à 15 inclus.

• '0123456789abcdef'{~#.- Prenez chaque ligne de cette matrice de bits comme binaire pour un nombre, et utilisez ce nombre pour sélectionner dans la liste des chiffres hexadécimaux. Cela convertit tous les quatre bits en hexadécimal.

• 1!:2&4- L'interpréteur J a un problème avec la sortie de chaînes de plus de 256 caractères, nous devons donc envoyer ces données directement à stdout. Vous en gagnez un peu, vous en perdez un peu.

• 4[- Enfin, jetez le résultat de 1!:2et à la place, sortez les 4 manquants de la sortie. Nous faisons cela parce que c'est plus court que d'inclure ces quatre derniers nombres premiers et de retourner un résultat vide ici.

JS, 503

Suivant l'idée de @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

Testé sur Mathematica 8. Cela fait appel à deux observations:

• Mathematica FromDigitsne vérifie pas réellement la plage des chiffres donnés, donc si vous l'appliquez à une liste du formulaire, {2,0,2,2,0,...}vous obtenez simplement deux fois le résultat comme si vous vous y étiez appliqué {1,0,1,1,0,...}. Mais c'est exactement la forme générée parBitAnd ing les nombres premiers avec 2.
• Le dernier bit du nombre dont nous voulons la représentation hexadécimale se trouve être zéro (comme en témoigne la chaîne se terminant par un chiffre pair), c'est donc seulement deux fois le nombre que vous obtiendriez avec un nombre premier de moins. Mais un facteur de deux est exactement ce que nous obtenons en utilisant l'observation précédente, donc tout s'accorde parfaitement.