Kołmogorow złożony z łańcucha S jest zdefiniowana jako długość najkrótszego programu P, a wyjścia. Jeśli długość P jest mniejsza niż długość s, wówczas mówi się , że s jest ściśliwy , w przeciwnym razie s jest nieściśliwy . Większość ciągów jest nieściśliwa ...

Napisz najkrótszy program, który wypisuje ten ciąg (bez spacji i bez nowego wiersza):

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 

Dane wyjściowe powinny wyglądać następująco:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4e...7294

Uwaga: wprowadzanie danych przez użytkownika jest zabronione, nie ma dostępu do sieci ani bibliotek (z wyjątkiem tych wymaganych do drukowania danych wyjściowych).

Edycja I: sekwencja wydaje się losowa ... ale okazuje się, że jest bardzo ściśliwa, obsługując trochę liczb pierwszych ...

Edycja II: Dobra robota! Przejrzę odpowiedzi w ciągu najbliższych godzin, a następnie przydzielę nagrodę. Oto mój pomysł, jak to rozwiązać:

1. Jeśli spróbujesz skompresować dane, nie odejdziesz daleko ...
2. W Internecie można znaleźć (dobrze znaną?) Encyklopedię sekwencji całkowitych (OEIS);
3. próba pierwszych cyfr szesnastkowych d9, a6, b6, 33, ...(lub ich reprezentacja dziesiętna) nie daje rezultatu;
4. ale jeśli przekonwertujesz liczby na binarne ( 1,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0) i przeszukasz je w OEIS, otrzymasz ten wynik .
5. Jak zauważył Claudiu, podałem również małą wskazówkę w pytaniu (Edytuj I powyżej) ... :-)

Zwycięzcą jest : Peter Taylor (GolfScript, 50), ze specjalnym wyróżnieniem dla Claudiu (Python, 92), który jako pierwszy „rozwiązał” ten problem.

GolfScript (50 bajtów)

$ 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

Ponieważ wszyscy inni ujawniają teraz swój kod, uprzedzę również prośbę OP o cofnięcie kopii:

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

Przegląd sekcji

• Oblicz liczby pierwsze mniejsze niż N przy N = 38200: daje to pierwsze 4032 liczb pierwszych:38200,{:x,{)x\%!},,2=},
• Chcemy jednego bitu na liczbę pierwszą z konwersją szesnastkową, więc podziel je na grupy po 4: 4/
• Dla każdej grupy, mapa każdy prime pdo p&2 != 0i zrobić bazę-2-16 do podstawy konwersji: {3\{2&!!1$++}/.57>39*+}%(to gdzie są ciekawe sztuczki)
• Mamy teraz tablicę wartości ASCII plus pusty ciąg ze stdin; połącz je, aby uzyskać pojedynczy ciąg wyjściowy:+

Bardziej szczegółowy przegląd konwersji podstawowej

Biorąc pod uwagę stos zawierający pusty ciąg i listę liczb pierwszych, musimy wykonać dwie konwersje:

1. Zamień każdą liczbę pierwszą na bit wskazującą, czy jest ona równa 2 czy 3 (mod 4)
2. Konwertuj bity na cyfry szesnastkowe

Istnieje wiele równie długich sposobów na zrobienie 1; na przykład

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

lub nawet

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

Dla 2 oczywiste jest podejście

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

Ale baza jest długim słowem, a ponieważ 16 = 2 ⁴ , możemy z łatwością zapisać kilka znaków

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

Najbardziej oczywistym marnotrawstwem jest 18 znaków poświęconych temu ciągowi. Chcemy tylko funkcji od cyfry do kodu ASCII. Chcemy zmapować 0do '0' = 48, ..., 9do '9' = 57, 10do 'a' = 97, ... 15do 'f' = 102.

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

Ale teraz wrzuć do miksu zakaz base. Musimy to sami wdrożyć. Oczywistą implementacją (w tym łatwym kierunku) jest k basefałdowanie {\k*+}*. Nieco dłużej alternatywą jest prosta iteracja, która potrzebuje sprawę podstawową: 0\{\k*+}/. Baza 2 jest nieco wyjątkowa: 1$++odpowiada \2*+tej samej długości i podjąłem takie podejście.

Oba są dłuższe niż 5-char 2base, ale ponieważ teraz iterujemy nad wartościami, możemy pobrać część 1, aby uzyskać pojedynczą pętlę. Zastępujemy

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

z

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

dla miłego oszczędzania 1 znaku, lub

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

za stratę 1 char.

Ale chociaż utrata 1 znaku wygląda jak krok wstecz, zastanów się, co stanie się z tym 0. Jest pomnożona przez 16 i dodana do wyjściowego wyniku konwersji. Ostatnią rzeczą, jaką robimy, jest dodanie wielokrotności 16 do wyniku. Możemy więc połączyć oba jako

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

Najkrótsza stawka i sprytna premia sprawiają, że jest bardziej interesująca.

Python, 92 znaki

Oto panie i panowie, sam kod!

>>> 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 zostawił sprytną wskazówkę, mówiąc, że „okazuje się, że jest bardzo ściśliwy, obsługując trochę liczb pierwszych”. Byłem pewien, że „trochę” nie zostało przypadkowo napisane kursywą, więc przekonwertowałem łańcuch szesnastkowy na kawałki i próbowałem znaleźć wzory. Myślałem, że na początku reprezentuje wszystkie liczby pierwsze jako kawałki i łączy je razem, ale to nie wyszło. Potem może wziąć tylko kilka cyfr lub upuścić wszystkie zera w ciągu bitów - wciąż nie. Może to ciąg bitów najmniej znaczącego z pierwszych kilku liczb pierwszych? Nie do końca. Ale w końcu znalazłem ten, który zadziałał - jest to ciąg bitów drugiego najmniej znaczącego bitu z pierwszych jednak wielu liczb pierwszych.

Mój kod właśnie to robi: generuje wystarczającą liczbę liczb pierwszych, bierze drugi bit każdego ( i/2%2), konkatenuje je jako ciąg binarny, a następnie przekształca na base-10 ( int(..., 2)), a następnie na base-16 ( hex(...)).

Haskell, 105

Skrót SHA1: a24bb0f4f8538c911eee59dfc2d459194ccb969c

Wydajność:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c67629

Edycja: Kod:

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

Przegapiłem zasadę o nieużywaniu żadnych funkcji bibliotecznych oprócz drukowania (putStr). Zakładam, że operatory matematyczne, chociaż są technicznie funkcjami, są dozwolone.

C, 136 116 109 103 znaków

OK, oto mój wysiłek:

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

jeśli weźmiemy ten ciąg za base64, możemy mieć mniejszą wersję przy użyciu wersji innej niż base-64:

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

Myślę jednak, że autor chce, abyśmy zamiast tego znaleźli logikę tego nieprzypadkowego ciągu.

Mathetmatica - 56

Tajemnica jest już rozwiązana, więc wystarczy wdrożyć ten pomysł

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

J - 46 znaków

Nie przejmuj się mną, po prostu loguję tutaj J golfa dla potomności. Nie był wystarczająco sprytny, aby wymyślić sztuczkę.

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

Wyjaśnił:

• p:i.1007 4- Stwórz 1007-rzędową, 4-kolumnową macierz liczb całkowitych od 0, a następnie weź liczby pierwsze odpowiadające tym liczbom całkowitym. Tak, p:jest wbudowany w J. Tak, brakuje nam czterech liczb pierwszych.

• 2|<.-:- Przekrój każdą liczbę ( -:), wstaw ją ( <.) i weź ten moduł 2 ( 2|). Jest to to samo, co znaczące zwiększenie wartości umowy najmu.

• #.- Konwertuj każdy wiersz wyniku z podstawy 2 na liczbę całkowitą. To daje nam 1007 liczb od 0 do 15 włącznie.

• '0123456789abcdef'{~#.- Weź każdy wiersz tej macierzy bitów jako binarny dla liczby i użyj tej liczby, aby wybrać z listy cyfr szesnastkowych. Konwertuje to co cztery bity na heks.

• 1!:2&4- Interpreter J ma problem z wyprowadzaniem ciągów dłuższych niż 256 znaków, więc musimy wysłać te dane bezpośrednio na standardowe wyjście. Niektóre wygrywasz, niektóre tracisz.

• 4[- Na koniec odrzuć wynik 1!:2i zamiast tego wypisz brakujące 4 z wyjścia. Robimy to, ponieważ jest krótszy niż uwzględnienie ostatnich czterech liczb pierwszych i zwrócenie tutaj pustego wyniku.

JS, 503

Zgodnie z pomysłem @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

Testowane na Mathematica 8. Wykorzystuje to dwie obserwacje:

• Mathematica FromDigitstak naprawdę nie sprawdza zakresu podanych cyfr, więc jeśli zastosujesz go do listy formularza, {2,0,2,2,0,...}otrzymasz tylko dwa razy wynik, jakbyś się o to ubiegał {1,0,1,1,0,...}. Ale to jest dokładnie forma wygenerowana przez BitAndpołączenie liczb pierwszych z 2.
• Ostatni bit liczby, której reprezentacja szesnastkowa, której chcemy, jest akurat zero (o czym świadczy ciąg kończący się cyfrą parzystą), więc jest to tylko dwukrotność liczby, którą uzyskasz z jedną liczbą pierwszą mniejszą. Ale współczynnik dwa jest dokładnie tym, co otrzymujemy z poprzedniej obserwacji, więc wszystko idealnie pasuje do siebie.