login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Index to sequences related to the complexity of n

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.

License Agreements, Terms of Use, Privacy Policy. .

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