cp's OEIS Frontend

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

%I A213923 #29 Oct 05 2021 15:32:53
%S A213923 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,
%T A213923 19,17,19,21,19,21,19,21,21,21,19,21,21,21,21,23,21,23,23,21,23,25,21,
%U A213923 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
%N A213923 Minimal lengths of formulas representing n only using addition, multiplication and the constant 1.
%H A213923 Alois P. Heinz, <a href="/A213923/b213923.txt">Table of n, a(n) for n = 1..10000</a>
%H A213923 Shalosh B. Ekhad, <a href="http://www.math.rutgers.edu/~zeilberg/tokhniot/oArithFormulas1">Everything About Formulas Representing Integers Using Additions and Multiplication for integers from 1 to 8000</a>.
%H A213923 Edinah K. Ghang, Doron Zeilberger, <a href="http://arxiv.org/abs/1303.0885">Zeroless Arithmetic: Representing Integers ONLY using ONE</a>, arXiv:1303.0885 [math.CO], 2013
%F A213923 a(n) = 2*A005245(n)-1.
%e A213923 a(3) = 5 because for n = 3, the minimum is length = 5, formula = "11+1+" or "111++".
%p A213923 with(numtheory):
%p A213923 a:= proc(n) option remember;
%p A213923        1+ `if`(n=1, 0, min(seq(a(i)+a(n-i), i=1..n/2),
%p A213923        seq(a(d)+a(n/d), d=divisors(n) minus {1, n})))
%p A213923     end:
%p A213923 seq(a(n), n=1..100);  # _Alois P. Heinz_, Mar 07 2013
%t A213923 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_ *)
%Y A213923 Cf. A005245, A214833.
%K A213923 nonn
%O A213923 1,2
%A A213923 _Jonathan Vos Post_, Mar 06 2013