25
\$\begingroup\$

If you visit Code Golf often, you may have heard of Kolmogorov complexity. It's usually defined as the amount of bytes required to express some string in a programming language.

Here the Kolmogorov-complexity of a natural number is defined similarly: the number of bytes required to represent it in a programming language.

A number is Kolmogorov-simple if it's more space-efficient to represent it with the programming language, then with simply storing it in binary (base-256). In other words, if \$b\$ is the Kolmogorov-complexity of a number \$n\$, \$n\$ is Kolmogorov-simple iff \$b\lt\log_{256}(n+1)\$. Every Turing-complete language has infinitely many Kolmogorov-simple numbers.

Your task is to find the smallest Kolmogorov-simple number. In other words, output the smallest number \$n\$ in \$b\$ bytes, such that \$b<\log_{256}(n+1)\$.

Rules

  • If you express the number \$n\$, your program has to be at most \$\lceil \log_{256}(n+1)\rceil-1\$ bytes long.
  • The number has to be a positive whole number
  • Use a reasonable IO format. These may include: printing to stdout, expressions, functions, storing the number to a variable, pushing the number to stack or taking a number as input and comparing it the represented number. Try to stick to the convention. Floating point numbers, complex numbers and fractions are allowed, as long as it's exactly an integer.
  • If you use a text-based format, your output should match this regex: ((\d+(\.\d*)?)|(\d*\.\d+))(e[+-]?\d+)?. That is, it should be a decimal number. Trailing newlines etc. are allowed.

Smallest number outputted (i.e. the value \$n\$) per language wins!

\$\endgroup\$
13
  • 1
    \$\begingroup\$ To clarify, the winning criterion is smallest number? If so, this should be tagged code-challenge, since code-golf is strictly for when the winning criterion is just "shortest code". \$\endgroup\$
    – hyper-neutrino
    Dec 18, 2021 at 16:52
  • 1
    \$\begingroup\$ Since caird's Retina answer can't be beaten, maybe you should make this "smallest number per language wins" \$\endgroup\$
    – tjjfvi
    Dec 18, 2021 at 16:55
  • 1
    \$\begingroup\$ @AnttiP - surely accepting an answer (especially <2h after posting the challenge) contradicts the "smallest number per language wins" scoring...? \$\endgroup\$ Dec 18, 2021 at 18:53
  • 2
    \$\begingroup\$ IMO allowing snippets for this challenge makes sense, as it’s about the size of the number, not the size of the code. By forcing IO requirements to be included, it’s no longer about “the smallest number that can be generated more compactly than its size in bytes”, but about “the smallest number that can be generated and printed more compactly than its size in bytes”. The latter, IMO, is a lot less interesting and seems less in the spirit of the challenge. \$\endgroup\$
    – tjjfvi
    Dec 18, 2021 at 20:01
  • 2
    \$\begingroup\$ Doesn't ceil(log256(n+1))-1 equal floor(log256(n))? \$\endgroup\$
    – xigoi
    Dec 19, 2021 at 9:59

20 Answers 20

10
\$\begingroup\$

Retina, 0 bytes, outputs 1

Try it online!

Outputs 1, and \$\log_{256} 2 = 0.125 > 0\$

\$\endgroup\$
7
\$\begingroup\$

Jelly, 1 byte, outputs 256

Try it online!

This outputs 256 in one byte, and \$\log_{256} (257) \approx 1.0007 > 1\$

\$\endgroup\$
6
  • \$\begingroup\$ Well, guess that's as good as it gets, huh :P \$\endgroup\$
    – hyper-neutrino
    Dec 18, 2021 at 16:51
  • \$\begingroup\$ @hyper-neutrino Unless you can find a language where the empty program outputs a number between 1 and 255, it can't be beaten \$\endgroup\$
    – AnttiP
    Dec 18, 2021 at 16:52
  • \$\begingroup\$ (something something MetaGolfScript) \$\endgroup\$
    – tjjfvi
    Dec 18, 2021 at 16:54
  • \$\begingroup\$ How is 1 byte?? Looks like 3 to me. Jelly clearly specifies the encoding at UTF-8 and I'm not even aware of encodings that offer this character in a 1-byte form. \$\endgroup\$ Dec 19, 2021 at 14:57
  • \$\begingroup\$ @R..GitHubSTOPHELPINGICE Jelly uses a custom code page to display its commands, so that they aren't just the random characters shown as UTF-8. is byte 0x89 in hex, so I could encode this program as ``, but its a lot nicer to use Jelly's code page instead \$\endgroup\$ Dec 19, 2021 at 15:01
6
\$\begingroup\$

R (& likely polyglot), 3 bytes, outputs 16777216 = 256\$^3\$

8^8

Try it online!

\$\endgroup\$
4
\$\begingroup\$

1+, 20 bytes, outputs \$2^{160}\$

Reduced from \$2^{2^8}\$ due to @null

11+"*"*"+"*"*"*"*"*:

Try it online!

The fastest way to get big numbers in 1+ (of which I am its creator) is to repeatedly square. \$\lceil\log_{256}(2^{160}+1)\rceil-1=20\$.

\$\endgroup\$
2
  • \$\begingroup\$ 11+1+"*"*"*"*"*"*"*: is smaller. \$\endgroup\$ Feb 4 at 14:02
  • \$\begingroup\$ 11+"*"*"+"*"*"*"*"*: is smaller. \$\endgroup\$ Feb 8 at 16:43
3
\$\begingroup\$

Batch, 38 bytes, outputs ≈2³⁰⁴

@for /l %%a in (1,1,92)do @cmd/cset/a3

log₂₅₆(33...33) ≈ 38.004

\$\endgroup\$
3
\$\begingroup\$

brainfuck, 24 bytes, outputs (1063-1)/3

+[+++++>+<]++++[++++>.<]

Try it online!

This creates 51, the ASCII value of 3, as 255/5, and then outputs it 63=252/4 times.

+[+++++>+>+<<]>[->.<] falls just short of working: in 21 bytes, it outputs 3 51 times for ≈3.33×1050, while 25621≈3.74×1050.

\$\endgroup\$
2
\$\begingroup\$

BQN, 3 bytes, outputs 16777216

8⋆8

Run online!

$$\log_{256}\left(8^8+1\right) > \log_{256}\left(8^8\right) = 3$$

\$\endgroup\$
2
\$\begingroup\$

Husk, 2 bytes, outputs 9! = 362880 = 256^2.3

Π9

Try it online!

\$\endgroup\$
7
  • \$\begingroup\$ Π9 is 3 bytes, not 2. \$\endgroup\$ Dec 19, 2021 at 15:00
  • 2
    \$\begingroup\$ @R..GitHubSTOPHELPINGICE Husk uses a custom codepage, so while it is 3 bytes when encoded in UTF-8 in Husk's custom code page it's 2 bytes. It's just displayed this way for the convenience of the reader. \$\endgroup\$
    – Wheat Wizard
    Dec 19, 2021 at 17:18
  • \$\begingroup\$ @R..GitHubSTOPHELPINGICE - here is the Husk codepage of 256 characters \$\endgroup\$ Dec 19, 2021 at 17:28
  • 1
    \$\begingroup\$ @R..GitHubSTOPHELPINGICE it isn't cheating, the alternative would be to have a bunch of unreadable junk chars. The bytes are the same, this is just way easier to read. \$\endgroup\$ Dec 27, 2021 at 14:10
  • 2
    \$\begingroup\$ @R..GitHubSTOPHELPINGICE a byte is a byte, it doesn't have to correspond to any character encoding at all, we could just type raw bits into a file, it's just much less convenient than allowing character encodings for readability. No unfair advantage is gained by giving a custom set of symbols to each byte \$\endgroup\$ Dec 27, 2021 at 17:10
2
\$\begingroup\$

JavaScript (ES7), 8 bytes, 27368747340080914432

(displayed as 27368747340080914000)

_=>7**23

Try it online!

The actual value of \$7^{23}\$ is \$27368747340080916343\$ but we get \$27368747340080914432\$ because of IEEE-754 loss of precision.

We have \$\log_{256}(27368747340080914432+1)\approx 8.07\$

\$\endgroup\$
5
  • \$\begingroup\$ Looks like not just loss of precision but also inaccurate conversion to decimal... :-( Values resulting from loss of precision should never end in 0s. \$\endgroup\$ Dec 19, 2021 at 15:02
  • 1
    \$\begingroup\$ And an interesting question is whether the number here is actually 27368747340080914432 (the value the program produces) or 27368747340080914000 (the value shown if you print that number as a decimal string in js). \$\endgroup\$ Dec 19, 2021 at 18:45
  • \$\begingroup\$ I believe this is 27368747340080914432. It may be verified by BigInt(7**23) \$\endgroup\$
    – tsh
    Dec 23, 2021 at 5:53
  • \$\begingroup\$ I've updated it to the internal value. My guess is that there's an intermediate conversion to 2.7368747340080914e+19 (like Python does) before eventually displaying it without the scientific notation. \$\endgroup\$
    – Arnauld
    Dec 23, 2021 at 12:08
  • \$\begingroup\$ Don't _=>8e16 work? \$\endgroup\$
    – l4m2
    Jan 27 at 19:05
2
\$\begingroup\$

x86-64 machine code, 7 bytes, outputs \$2^{56}\$

6A 01 58 48 0F C8 C3

Try it online!

Returns a value in RAX, as is standard.

In assembly:

.global f
f:  push 1      # (2 bytes) Push 1 onto the stack.
    pop rax     # (1 byte)  Pop it out into RAX.
    bswap rax   # (3 bytes) Reverse the order of the bytes in RAX.
    ret         # (1 byte)  Return.
\$\endgroup\$
2
\$\begingroup\$

Vyxal H, 0 bytes


The H flag pre-sets the stack to 100.

$$log_{256}\;101 = 0.83227643534397 > 0$$

Try it Online!

For a program without flags, you can use to output 256, similar to caird coinheringaahing's Jelly answer.

\$\endgroup\$
2
\$\begingroup\$

Stax, 3 bytes, outputs 100000000

8|A

Run and debug it

$$\left \lceil{\log_{256}\left(10^8+1\right)}\right\rceil - 1= 3$$

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 3 bytes, outputs 22222222.

×⁸2

Try it online! Link is to verbose version of code. log₂₅₆(22222222) ≈ 3.05 Explanation: Charcoal only prints strings by default, so something like φ (Print(f);) prints 1000 -s instead of 1000; casting to string costs a byte, meaning we now need a value of at least 65536, however no predefined variable now holds a suitable value. This means we now need to look for a 3-byte answer that prints at least 16777216, which can most easily be achieved in a number of ways by repeating the character 2.

\$\endgroup\$
1
\$\begingroup\$

Python 2, 11 bytes, outputs 5704427701027032306735164424192

print 9<<99

Try it online!

$$\log_{256}(5704427701027032306735164424192+1)-1 = 11.77$$

\$\endgroup\$
2
  • \$\begingroup\$ 5**38 would give a smaller number (with a log256 of 11.029). \$\endgroup\$
    – Arnauld
    Dec 18, 2021 at 17:25
  • 5
    \$\begingroup\$ 4**44 is even better with log(4**44)= 11 so log(4**44+1)>11 \$\endgroup\$
    – Jakque
    Dec 18, 2021 at 21:10
1
\$\begingroup\$

Python 3, 13 bytes, outputs 20282409603651670423947251286016

print(16**26)

Try it online!

From what I can understand, this is the absolute minimum for a 13 byte program - it prints 256**13, the minimum number that needs 13 bytes to store. Good luck getting anything below this in Python 3.

Bonuses I found:

print(18**25) # 19% bigger than the actual answer
print(27**22) # 52% bigger than the actual answer
print(15**27) # 2.8x as big as the actual answer
\$\endgroup\$
0
1
\$\begingroup\$

GolfScript, 5 bytes, outputs 2565 = 420 = 1099511627776

4 20?

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 3, 12 bytes, outputs 79228162514264337593543950336

print(4**48)

Inspired by this answer.

Explanation:

4**48 == 16**24 == 256**12

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 7 bytes, outputs 150094635296999121

p 3**36

Similar to other answers, uses p to debug print the number. Fortunately for numbers the debug print value is the same as the normal output would be.

$$\left \lceil{\log_{256}\left(3^{36}+1\right)}\right\rceil - 1= 7$$

\$\endgroup\$
0
\$\begingroup\$

Excel, 5 bytes, outputs 1,09951E+21 ≈ 240 = 2565

=2^40
\$\endgroup\$
0
\$\begingroup\$

APL, 2 bytes

!9

The program prints factorial of 9 = 362880. Validation of allowed length:

      1-⍨⌈256⍟1+!9
2
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.