This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 0-ary 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 FORMULA a(n) = 1 + min {a(n-1), a(i)+a(n-i), a(j)+a(n/j)} where 0 <= i <= n and j|n. - 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 0-ary operation, 0.) The name for 1 is 's0', a formula of length 2. (Equivalently, 1 is formed by two uses of operations: the 0-ary 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 0-ary 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 0-ary 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 0-ary 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 0-ary 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 0-ary 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 0-ary 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

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.

Last modified April 20 08:32 EDT 2019. Contains 322306 sequences. (Running on oeis4.)