Integers with low Kolmogorov complexity
I found this cute sequence in the Online Encyclopedia of Integer Sequences:
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.
| Number | Shortest C representation |
|---|---|
| 1000 | 1e3 |
| 2000 | 2e3 |
| 3000 | 3e3 |
| 4000 | 4e3 |
| 5000 | 5e3 |
| 6000 | 6e3 |
| 7000 | 7e3 |
| 8000 | 8e3 |
| 9000 | 9e3 |
| ... | ... |
| 100000 | 1e5 |
| 100001 | 1e5+1 |
| ... | ... |
| 285000 | 285e3 |
| 285714 | 2e6/7 (hey, a nontrivial example!) |
| 286000 | 286e3 |
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.)
Leave Integers with low Kolmogorov complexity to:
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
- Week 3 at Hashicorp
- Existence properties for first-order number theory are all finitely checkable
- Job search notes
- Leaving Tintri
- Onigiri
- Is your coin flip irrational?
- Partitioning a set into lists
- Math is more than plugging in a formula, dammit
- Why are email pitches so bad?
- Steem account setup latency: 40 days