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.)
Congratulations @markgritter! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :
Click here to view your Board of Honor
If you no longer want to receive notifications, reply to this comment with the word
STOPDo not miss the last post from @steemitboard:
Downvoting a post can decrease pending rewards and make it less visible. Common reasons:
Submit
This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @curie.
If you appreciate the work we are doing then consider voting both projects for witness by selecting stem.witness and curie!
For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!
Downvoting a post can decrease pending rewards and make it less visible. Common reasons:
Submit
Congratulations @markgritter! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :
Click here to view your Board of Honor
If you no longer want to receive notifications, reply to this comment with the word
STOPDo not miss the last post from @steemitboard:
Downvoting a post can decrease pending rewards and make it less visible. Common reasons:
Submit