We define the sequence of natural numbers by defining a first element, called "zero", and a successor-function *S _{1}* defined for any natural number -- this is the set-theoretic definition of the natural numbers with focus on algebra (choose zero as the first element because it is the neutral element of addition).

Normally you are allowed to generate any natural number by evaluation of *S _{1}* on any already defined natural number; which means simply iterating this function

But in our model we are restricted to iterate any function only one time. On the other hand we get granted to define as many new functions as wanted. Of course we can only define new functions

How many functions *S _{i} are needed AT LEAST to get a certain natural number n, if explicit evaluation is only allowed for not nested functions on the first element?
*

*
Let us answer this question constructively for these first small numbers:
*

- If
*n=0*then we need none, because*0*is already given. - If
*n=1*then we need only one, the already given function, because*S*_{1}(0)=1 - If
*n=2*then we need two functions. From the given S_{1}define*S*and then evalute_{2}= S_{1}(S_{1})*S*._{2}(0) - If
*n=3*then we need three functions. From the given*S*define_{1}*S*and then_{2}= S_{1}(S_{1})*S*. Finally evaluate_{3}= S_{2}(S_{1})*S*._{3}(0) - If
*n=4*then we need three functions. From the given*S*define_{1}*S*and then_{2}= S_{1}(S_{1})*S*. Finally evaluate_{4}= S_{2}(S_{2})*S*._{4}(0) - If
*n=5*then we need four functions: The given*S*and then define canonically e.g._{1}*S*. Finally evaluate_{2}, S_{4}, S_{5}*S*._{5}(0) - If
*n=6*then we need four functions: The given*S*and then define canonically e.g._{1}*S*. Finally evaluate_{2}, S_{3}, S_{6}*S*._{6}(0) - If
*n=7*then we need five functions: The given*S*and then define canonically e.g._{1}*S*. Finally evaluate_{2}, S_{3}, S_{4}, S_{7}*S*._{7}(0) - If
*n=8*then we need four functions: The given*S*and then define canonically e.g._{1}*S*. Finally evaluate_{2}, S_{4}, S_{8}*S*._{8}(0)

Remark: If we use the classic set-theoretic definition of the natural numbers (first element is "1") which is founded on truthness of logical statements with free variables
-- if and only if the cardinality of a set is positive then an element exists in the set --,
then we must ask for the number of NEWLY defined functions *S _{i}*
in the above question. In this case we would/will define

There is a famous conjecture of K.B. Stolarsky and D.E. Knuth (firstly stated in 1969) that always holds
** l(n) >= floor( log2(n) ) + ceil( log2( ν(n) ) )**
which connects sharply the additive complexity of

^{+}We are forced to set *l(0) = -1*.

Further reading for complexity measures on the natural numbers: H. Altman, "Integer Complexity, Addition Chains, and Well-Ordering", Ph.D. Thesis, University of Michigan, 2014

Then holds

Achim Flammenkamp

Last update: 2016-09-28 12:37:59 UTC+2