Mark Gritter avatar

Integers with low Kolmogorov complexity

markgritter

Published: 28 Oct 2018 › Updated: 28 Oct 2018Integers with low Kolmogorov complexity

Integers with low Kolmogorov complexity

I found this cute sequence in the Online Encyclopedia of Integer Sequences:

A168650: Integers that can be generated with a C/C++ expression that is shorter than their decimal representation.

The "Kolmogorov complexity" of a string is the length of the minimal program which generates that string. In general, this is uncomputable, but we can find small examples through exhaustive search. The sequence A168650 attempts a practical measurement using a real programming language, C. (I don't think any C++ feature will change the results for small examples--- but, because they are different languages, the definition should be precise, particularly as to which version.)

Most of the short examples are not very interesting, because they use the floating-point notation.

NumberShortest C representation
10001e3
20002e3
30003e3
40004e3
50005e3
60006e3
70007e3
80008e3
90009e3
......
1000001e5
1000011e5+1
......
285000285e3
2857142e6/7 (hey, a nontrivial example!)
286000286e3

However, the submitter did provide this cool graph:

Sources

The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, October 27, 2018.

Inspired by this question on Quora: https://www.quora.com/Is-there-a-list-of-integer-numbers-with-a-low-Kolmogorov-complexity (and I wrote an answer there.)

Kolmogorov Complexity -- Wikipedia

Leave Integers with low Kolmogorov complexity to:

Written by

Vault Advisor at Hashicorp | founder, Tintri | CS PhD dropout | 3x startup nerd | math geek

Read more #mathematics posts


Best Posts From Mark Gritter

We have not curated any of markgritter's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.

More Posts From Mark Gritter