A370829 Minimum number of (-1)'s needed to write n, using +, *, ^ and parentheses, disallowing noninteger intermediate values.

2, 3, 4, 4, 6, 5, 7, 6, 6, 7, 8, 7, 9, 8, 7, 6, 8, 9, 10, 9, 10, 11, 10, 9, 8, 9, 8, 9, 10, 10, 10, 9, 10, 10, 9, 8, 10, 11, 11, 11, 13, 12, 13, 12, 11, 12, 11, 10, 10, 11, 11, 11, 10, 9, 11, 10, 12, 11, 12, 11, 10, 9, 8, 7, 9, 10, 11, 11, 13, 12, 12, 11, 12, 12, 12, 12, 11, 10, 9, 8, 7

Offset

1,1

Comments

a(n) is bounded by a(n-1)-1 <= a(n) <= a(n-1)+2 since:

An expression for n-1 can be increased to n by " + (-1)*(-1)" which is 2 more (-1)'s so that a(n) <= a(n-1)+2.

An expression for n can be decreased to n-1 by "+ (-1)" which is 1 more (-1) so that a(n-1) <= a(n)+1.

Links

Table of n, a(n) for n=1..81.

Edgar Deshayes, Java program

Example

Let m = -1. Then, n = 1..9 can be expressed using a(n) m's as follows:
a(1)=2: 1 = (-1)*(-1) = m*m.
a(2)=3: 2 = (-2)*(-1) = (m+m)*m.
a(3)=4: 3 = (-3)*(-1) = (m+m+m)*m.
a(4)=4: 4 = (-2)*(-2) = (m+m)*(m+m).
a(5)=6: 5 = (-5)*(-1) = (m+m+m+m+m)*m.
a(6)=5: 6 = (-2)*(-3) = (m+m)*(m+m+m).
a(7)=7: 7 =   8 +(-1) = (m+m+m+m)*(m+m)+m.
a(8)=6: 8 = (-4)*(-2) = (m+m+m+m)*(m+m).
a(9)=6: 9 = (-3)^  2  = (m+m+m)^((m+m)*m).

Prog

(Java) // see linked program

Crossrefs

Cf. A025280 (same with +1).

Sequence in context: A301764 A181833 A202650 * A228286 A158973 A071323

Adjacent sequences: A370826 A370827 A370828 * A370830 A370831 A370832

Keyword

nonn

Author

Edgar Deshayes, Mar 02 2024

Status

approved