The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A168650 Integers that can be generated with a C/C++ expression that is shorter than their decimal representation. 3
1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000, 15000, 16000, 17000, 18000, 19000, 20000, 21000, 22000, 23000, 24000, 25000, 26000, 27000, 28000, 29000, 30000, 31000, 32000, 33000, 34000, 35000 (list; graph; refs; listen; history; text; internal format)



From Dmitry Kamenetsky, Jul 24 2015: (Start)

By "expression" we mean a string representing a piece of code in C/C++ that evaluates to a positive integer, where we assume for simplicity that the result is converted to an integer using the floor operation. An expression can use the binary operators available in those languages and the digits '0' to '9', and we also allow "AeB" for A*10^B.

For example: "A+B" evaluates to A plus B, "A*B" evaluates to A multiplied by B, "A/B" is floor(A/B), "A<<B" is A*2^B.

This sequence lists every integer n having an expression whose length is strictly less than the decimal length of n; of course every integer n has an expression whose length is the same as the decimal length of n, namely "n". In some sense the numbers in this sequence can be considered simple, since they have a low Kolmogorov complexity.

We assume that there are no rounding errors or integer overflow during the evaluation of the expression.(End)


Dmitry Kamenetsky, Table of n, a(n) for n = 1..14238

Dmitry Kamenetsky, Plot showing the length of the shortest C/C++ expression that generates integers from 1 to 2000000.

Ed Pegg, Jr., Integer Complexity, 2004.

L. Staiger, The Kolmogorov complexity of real numbers, Theoretical Computer Science, pp. 455-466, 2002.

E. Weisstein, Integer Complexity

Wikipedia, Kolmogorov Complexity

Index to sequences related to the complexity of n


1000 has 4 digits, but it can be generated with a 3-digit expression "1e3". The integers 43000, 116666, 114688, 199997 are also in the sequence, since they can be generated using the expressions "43e3", "7e5/6", "7<<14", "2e5-3" respectively.


Cf. A005245, A117607, A118121, A168651, A168652.

Sequence in context: A004267 A319441 A202456 * A043491 A100988 A195163

Adjacent sequences:  A168647 A168648 A168649 * A168651 A168652 A168653




Dmitry Kamenetsky, Dec 01 2009


Name clarified by Dmitry Kamenetsky, Jul 24 2015



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 14 09:06 EDT 2021. Contains 345018 sequences. (Running on oeis4.)