Kolmogorov-mania

Question

The Kolmogorov complexity of a string s is defined as the length of the shortest program P that outputs s. If the length of P is shorter than the length of s, then s is said to be compressible, otherwise s is incompressible. Most strings are incompressible ...

Write the shortest program that outputs this string (without spaces and without newlines):

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 

The output should look like:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4e...7294

Note: no user input is allowed, nor web access, nor libraries (except the one required for printing the output).

Edit I: the sequence seems random ... but it turns out to be highly compressible handling a little bit of prime numbers ...

Edit II: Well done! I'll review the answers in the next hours, then assign the bounty. This is my idea on how it could be solved:

1. If you try to compress the data you don't go far away ...
2. In internet you can find the (well-known?) On-Line Encyclopedia of Integer Sequences (OEIS) ;
3. trying the first hexadecimal digits d9, a6, b6, 33, ... (or their decimal representation) give no result;
4. but if you convert the numbers to binary (1,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0) and searching them on OEIS, you get this result.
5. As noted by Claudiu, I also gave a little hint in the question (Edit I above) ... :-)

The winner is: Peter Taylor (GolfScript, 50), with a special mention for Claudiu (Python, 92), the first who "solved" it.

Answer 1

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

Since everyone else is now revealing their code, I will also pre-empt OP's request to unobfuscate:

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

Overview dissection

• Compute primes smaller than N with N=38200: this gives the first 4032 primes: 38200,{:x,{)x\%!},,2=},
• We want one bit per prime, with a hex conversion, so split them into groups of 4: 4/
• For each group, map each prime p to p&2 != 0, and do a base-2 to base-16 conversion: {3\{2&!!1$++}/.57>39*+}% (this is where the interesting tricks are)
• We now have an array of ASCII values, plus the empty string from stdin; concatenate them to get a single string for output: +

More detailed dissection of the base conversion

Given a stack holding an empty string and a list of primes, we need to do two conversions:

1. Convert each prime to a bit indicating whether it's equal to 2 or 3 (mod 4)
2. Convert the bits into hex digits

There are lots of equally long ways to do 1; e.g.

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

or even

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

For 2, the obvious approach is

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

But base is a long word, and since 16 = 2⁴ we can easily save a few chars with

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

Now the most obvious waste is the 18 chars devoted to that string. We just want a function from digit to ASCII code. We want to map 0 to '0' = 48, ..., 9 to '9' = 57, 10 to 'a' = 97, ... 15 to 'f' = 102.

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

But now throw into the mix a ban on base. We need to implement it ourselves. The obvious implementation (in this direction, the easy one) is that k base is a fold {\k*+}*. The slightly longer alternative is a straightforward iteration, which needs a base case: 0\{\k*+}/. Base 2 is slightly special: 1$++ is equivalent to \2*+ for the same length, and I've taken that approach.

Both of those are longer than the 5-char 2base, but since we're now iterating over the values we can pull in part 1 to have a single loop. We replace

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

with

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

for a nice 1-char saving, or

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

for a 1-char loss.

But although that 1-char loss looks like a step backwards, consider what happens to that 0. It's multiplied by 16 and added to the base-conversion output. And the final thing we do is to add a multiple of 16 to the output. So we can combine the two as

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

Joint shortest and the bonus cleverness makes it more interesting.

Answer 2

Python, 92 characters

Here it is ladies and gentlemen, the code itself!

>>> 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 left a clever hint by saying that "it turns out to be highly compressible handling a little bit of prime numbers". I was sure the "little bit" wasn't italicized by accident, so I converted the hex string to bits and tried to find patterns. I thought that at first he was representing all the primes as bits and concatenating them together, but that didn't work out. Then maybe taking only a few digits, or dropping all the zeroes in the bit string - still no. Maybe it's a bitstring of the least-significant-bit of the first few primes? Not quite. But eventually I found the one that worked - it's a bitstring of the second-least-significant bit from the first however-many primes.

So, my code does just that: generate just enough primes, take the second bit of each (i/2%2), concatenate them as a binary string, then convert it to base-10 (int(..., 2)) and then to base-16 (hex(...)).

Answer 3

C, 136 116 109 103 characters

OK then, here's my 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

Answer 4

Haskell, 105

SHA1 hash: a24bb0f4f8538c911eee59dfc2d459194ccb969c

Output:

d9a6b63356a7954b29b0ac7f2aaa6d19b84b4cf8b62aac95a14b4ea59db3e7c94c4959ec94b3aa6c938f115a4d397582ecea24ccd32dc393384eb7a60dd2b5372354ad1b79aa6e495552945aa73a6ae9e452cd2d79adc612b5995bb47651174e94f39aa2e7156a55144d4e4aa35c2fab63ccb5a6a492968a2ec3d8889b8ca916f533225ba2e2cc1b27d4e8db17a43985caaa5b4f3624d3c6f694add70f7124e1b1c5ef65356c8dd71a871e25df5dc013b26f5a572898bd416604eda252c9ac83b36c567ed1c6cc534a62c559a9b2d4af22a5a9f4b2992332f8fbae486a8a9ab5467a36599f92d325b519bd8a4a4962a5e459fbe5baa235dda9361da9c96989776ab2342d1d2261c5c2661ce2767452a5d984b98aa6b514ec2958b2bc96161648f5c5bd2f321b3d4f4b2eb26b9ad932a44b5cbc92b7b32639fa422d64ed1a79494ca3b785b2a6e28cd95590e1a8874b60a6e1bac4bbec32397690a6b4c665796191aa3d54b7183d154b06db308a4d4aa135755d3bd998ac555b10ddb3e2ccf15eb32b5390b6ee2bac8f888d955a75df592d1c5a4ce8f4ea48b956dea09291a9154c55d5e93a768e04bae7b2aae9ab2ad62333453dc4e952e36a4750baafe4e591a314639526b38b4cbcaa5a927aabada6db532e97066dba3a66494d95d765c2aac31a92933fcac26c2b375513c9884a5c626ba6aeccde7294

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

I missed the rule about not using any library functions except for printing (putStr). I would assume that mathematical operators, while they're technically functions, are allowed.

Answer 5

JS, 764

if we consider this string as base64, we can have a smaller version using the un-base-64-ed version:

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

But I think that the author wants us to find the logic behind this non-random string instead.

Answer 6

Mathetmatica - 56

The mystery is already solved, so just implementing the idea

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

Answer 7

J - 46 char

Don't mind me, just logging the J golf here for posterity. Wasn't clever enough to figure out the trick.

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

Explained:

• p:i.1007 4 - Create a 1007-row, 4-column matrix of the integers from 0, then take the prime numbers corresponding to those integers. Yes, p: is a J builtin. Yes, we're four primes short.

• 2|<.-: - Halve each number (-:), floor it (<.), and take that modulo 2 (2|). This is the same as taking the next-to-lease significant bit.

• #. - Convert each row of the result from base 2 into an integer. This gives us 1007 numbers from 0 to 15 inclusive.

• '0123456789abcdef'{~#. - Take each row of this matrix of bits as the binary for a number, and use that number to select from the list of hex digits. This converts every four bits into the hex.

• 1!:2&4 - The J interpreter has a problem with outputting strings longer than 256 chars, so we have to send this data directly to stdout. You win some, you lose some.

• 4[ - Finally, discard the result from 1!:2 and instead output the missing 4 from the output. We do this because it's shorter than including those last four primes and returning an empty result here.

Answer 8

JS, 503

Following @xem idea:

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)

Answer 9

Mathematica, 55

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

Tested on Mathematica 8. This makes use of two observations:

• Mathematica's FromDigits doesn't actually check the range of the digits given, so if you apply it to a list of the form {2,0,2,2,0,...} you just get twice the result as if applying to {1,0,1,1,0,...}. But that's exactly the form generated by BitAnding the primes with 2.
• The last bit of the number whose hexadecimal representation we want happens to be zero (as evidenced by the string ending in an even digit), so it is just two times the number you'd get with one prime less. But a factor of two is exactly what we get from using the previous observation, so everything perfectly fits together.