A213923 Minimal lengths of formulas representing n only using addition, multiplication and the constant 1.

1, 3, 5, 7, 9, 9, 11, 11, 11, 13, 15, 13, 15, 15, 15, 15, 17, 15, 17, 17, 17, 19, 21, 17, 19, 19, 17, 19, 21, 19, 21, 19, 21, 21, 21, 19, 21, 21, 21, 21, 23, 21, 23, 23, 21, 23, 25, 21, 23, 23, 23, 23, 25, 21, 23, 23, 23, 25, 27, 23, 25, 25, 23, 23, 25, 25, 27, 25, 27, 25, 27, 23, 25, 25, 25, 25, 27, 25

Offset: 1

Author

Jonathan Vos Post, Mar 06 2013

Keywords

• nonn

Examples

			a(3) = 5 because for n = 3, the minimum is length = 5, formula = "11+1+" or "111++".
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• Shalosh B. Ekhad, Everything About Formulas Representing Integers Using Additions and Multiplication for integers from 1 to 8000.
• Edinah K. Ghang, Doron Zeilberger, Zeroless Arithmetic: Representing Integers ONLY using ONE, arXiv:1303.0885 [math.CO], 2013

Crossrefs

Cf. A005245, A214833.

Programs

Maple

with(numtheory):
a:= proc(n) option remember;
       1+ `if`(n=1, 0, min(seq(a(i)+a(n-i), i=1..n/2),
       seq(a(d)+a(n/d), d=divisors(n) minus {1, n})))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Mar 07 2013

Mathematica

a[n_] := a[n] = 1 + If[n == 1, 0, Min[Join[Table[a[i] + a[n-i], {i, 1, n/2}], Table[a[d] + a[n/d], {d, Divisors[n] ~Complement~ {1, n}}]]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 01 2017, after Alois P. Heinz *)

Formula

a(n) = 2*A005245(n)-1.