

A263283


Minimum number of characters required to express n in Peano Arithmetic.


1



1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 11, 10, 11, 12, 11, 11, 12, 12, 13, 12, 13, 14, 15, 13, 13, 14, 14, 14, 15, 14, 15, 15, 16, 16, 15, 15, 16, 17, 16, 16, 17, 16, 17, 17, 16, 17, 18, 16, 17, 17, 17, 17, 18, 17, 18, 18, 18, 19, 20, 17, 18, 19, 18, 17, 18, 19, 20
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

This sequence is the minimum number of characters needed in Peano Arithmetic to represent the number, where the characters are (i) '0' naming 0, (ii) 's' expressing the successor operation, (iii) '+' expressing the operation of addition, and (iv) 'x' expressing the operation of multiplication. Brackets are not used; Polish notation is employed instead, in which the operator is written before the terms rather than between them. Although in some cases there are different formulas of the same minimal length that represent the same number, the construction of the formulas is not arbitrary. It is not arbitrary that we start from 0, and it is not arbitrary that the only operations allowed are succession, addition, and multiplication. Finally, it is not arbitrary to use Polish notation to ensure shortness of formulas.
Another way of thinking of it would be: the minimum number of uses of operations necessary to give the number in Peano Arithmetic, where (i) 0 is considered to be a 0ary operation, (ii) succession is a singulary/unary operation, (iii) addition is a binary operation, and (iv) multiplication is a binary operation. This way of thinking has the advantage that it doesn't look fishy not to mention brackets.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..20000
Daniel Hill, Spreadsheet of first 27 terms
Index to sequences related to the complexity of n


FORMULA

a(n) = 1 + min {a(n1), a(i)+a(ni), a(j)+a(n/j)} where 0 <= i <= n and jn.  Charlie Neder, Jul 09 2018


EXAMPLE

So the name for 0 is simply '0', a formula of length 1. (Equivalently, 0 is formed by one use of the 0ary operation, 0.)
The name for 1 is 's0', a formula of length 2. (Equivalently, 1 is formed by two uses of operations: the 0ary operation, 0, and succession applied once to it.)
The name for 2 is 'ss0', a formula of length 3. (Equivalently, 2 is formed by three uses of operations: the 0ary operation, 0, and succession applied twice to it.)
The name for 3 is 'sss0', a formula of length 4. (Equivalently, 3 is formed by four uses of operations: the 0ary operation, 0, and succession applied thrice to it.)
The name for 9 is 'xsss0sss0', a formula of length 9. (Equivalently, 9 is formed by nine uses of operations: the 0ary operation, 0, twice, succession applied thrice to each value of these operations, and multiplication applied to these two new values.)
The name for 10 is 'sxsss0sss0', a formula of length 10. (Equivalently, 10 is formed by ten uses of operations: the 0ary operation, 0, twice, succession applied thrice to each value of these operations, multiplication applied to these two new values, and then succession applied to this last value.)
The name for 12 is 'xsss0ssss0', a formula of length 10. (Equivalently, 12 is formed by ten uses of operations: the 0ary operation, 0, twice, succession applied thrice to one value of these operations and four times to the other, and then multiplication applied to these two new values.)
The name for 14 is 'xss0sssssss0', a formula of length 12. (Equivalently, 14 is formed by twelve uses of operations: the 0ary operation, 0, twice, succession applied twice to one value of these operations and seven times to the other, and then multiplication applied to these two new values.)


CROSSREFS

Cf. A005245.
Sequence in context: A185137 A137180 A258632 * A128635 A100637 A081063
Adjacent sequences: A263280 A263281 A263282 * A263284 A263285 A263286


KEYWORD

easy,nonn


AUTHOR

Daniel Hill, Oct 13 2015


EXTENSIONS

More terms from Charlie Neder, Jul 09 2018
More terms from Alois P. Heinz, Jul 09 2018


STATUS

approved



