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,2

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

Formula

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

Example

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

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

Crossrefs

Cf. A005245, A214833.

Sequence in context: A265509 A265527 A217250 * A218452 A007731 A306590

Adjacent sequences: A213920 A213921 A213922 * A213924 A213925 A213926

Keyword

nonn

Author

Jonathan Vos Post, Mar 06 2013

Status

approved