cp's OEIS Frontend

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

%I A168650 #53 Feb 16 2025 08:33:11
%S A168650 1000,2000,3000,4000,5000,6000,7000,8000,9000,10000,11000,12000,13000,
%T A168650 14000,15000,16000,17000,18000,19000,20000,21000,22000,23000,24000,
%U A168650 25000,26000,27000,28000,29000,30000,31000,32000,33000,34000,35000
%N A168650 Integers that can be generated with a C/C++ expression that is shorter than their decimal representation.
%C A168650 From _Dmitry Kamenetsky_, Jul 24 2015: (Start)
%C A168650 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.
%C A168650 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.
%C A168650 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.
%C A168650 We assume that there are no rounding errors or integer overflow during the evaluation of the expression.(End)
%H A168650 Dmitry Kamenetsky, <a href="/A168650/b168650.txt">Table of n, a(n) for n = 1..14238</a>
%H A168650 Dmitry Kamenetsky, <a href="/A168650/a168650.png">Plot showing the length of the shortest C/C++ expression that generates integers from 1 to 2000000.</a>
%H A168650 Ed Pegg, Jr., <a href="http://www.mathpuzzle.com/MAA/17-Integer%20Complexity/mathgames_04_12_04.html">Integer Complexity</a>, 2004.
%H A168650 L. Staiger, <a href="http://dx.doi.org/10.1016/S0304-3975(01)00102-5">The Kolmogorov complexity of real numbers</a>, Theoretical Computer Science, pp. 455-466, 2002.
%H A168650 E. Weisstein, <a href="https://mathworld.wolfram.com/IntegerComplexity.html">Integer Complexity</a>
%H A168650 Wikipedia, <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity">Kolmogorov Complexity</a>
%H A168650 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A168650 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.
%Y A168650 Cf. A005245, A117607, A118121, A168651, A168652.
%K A168650 nonn,base
%O A168650 1,1
%A A168650 _Dmitry Kamenetsky_, Dec 01 2009
%E A168650 Name clarified by _Dmitry Kamenetsky_, Jul 24 2015