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:
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.)
