Kolmogorov-simple numbers

Question

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!

Answer 1

Retina, 0 bytes, outputs 1

Try it online!

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

Answer 2

Jelly, 1 byte, outputs 256

⁹

Try it online!

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

Answer 3

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

8^8

Try it online!

Answer 4

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\$.

Answer 5

Batch, 38 bytes, outputs ≈2³⁰⁴

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

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

Answer 6

brainfuck, 24 bytes, outputs (10⁶³-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×10⁵⁰, while 256²¹≈3.74×10⁵⁰.

Answer 7

BQN, 3 bytes, outputs 16777216

8⋆8

Run online!

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

Answer 8

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

Π9

Try it online!

Answer 9

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\$

Answer 10

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.

Answer 11

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.

Answer 12

Stax, 3 bytes, outputs 100000000

8|A

Run and debug it

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

Answer 13

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.

Answer 14

Python 2, 11 bytes, outputs 5704427701027032306735164424192

print 9<<99

Try it online!

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

Answer 15

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

Answer 16

GolfScript, 5 bytes, outputs 256⁵ = 4²⁰ = 1099511627776

4 20?

Try it online!

Answer 17

Python 3, 12 bytes, outputs 79228162514264337593543950336

print(4**48)

Inspired by this answer.

Explanation:

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

Try it online!

Answer 18

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$$

Answer 19

Excel, 5 bytes, outputs 1,09951E+21 ≈ 2⁴⁰ = 256⁵

=2^40

Answer 20

APL, 2 bytes

!9

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

      1-⍨⌈256⍟1+!9
2