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

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

Offset: 0

Author

Daniel Hill, Oct 13 2015

Keywords

• nonn
• nice

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 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.

For all n > 0, one has 6 * log_4(n) - 1 <= a(n) <= 7 * log_3(n) + 3, with the left inequality being an equality if and only if n is a power of 4 (except for n = 1). One can prove the lower bound by induction, while the upper bound follows from translating the base-3 expansion of n into the language of Peano Arithmetic (using Horner's method and always using 's' symbols rather than additions). - Rémi Peyre, Nov 06 2021

When is addition first used? Specifically: (1) What is the first index n where there is a formula of length a(n) containing the addition operator? and (2) What is the first index n such that all formulas of length a(n) contain at least one addition operator? For n up to 10^5, there are no formulas of length a(n) using addition, only successor, multiplication, and 0. Note that if the answer to (2) is "never", then this sequence is also the minimum number of characters required to express n in Skolem Arithmetic. - Charles R Greathouse IV, Nov 17 2021

Examples

			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.)
		

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

Crossrefs

Cf. A005245.

Programs

PARI

first(n)=my(v=vector(n+1)); v[1]=1; for(k=1,n, my(r=v[k],t); for(i=12,k\2, t=v[i+1]+v[k+1-i]; if(tk, break); t=v[d+1]+v[k/d+1]; if(tCharles R Greathouse IV, Nov 11 2021

Python

from functools import cache
@cache
def a(n):
    if n == 0: return 1
    cs = a(n-1)
    ca = min((a(i) + a(n-i) for i in range(1, n)), default=cs)
    cm = min((a(j) + a(n//j) for j in range(2, n) if n%j == 0), default=cs)
    return 1 + min(cs, ca, cm)
print([a(n) for n in range(68)])  # Michael S. Branicky, Nov 05 2021

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

Extensions

More terms from Charlie Neder, Jul 09 2018

More terms from Alois P. Heinz, Jul 09 2018