OFFSET
2,6
COMMENTS
The meaning of * is: multiply.
Let's abbreviate: "form of n" = "well-formed arithmetic expression exclusively made of symbols { 2, 3, +, * } that evaluates to n".
Any n superior or equal to 2 has forms. Proof: by recursion.
Let P(n) be the predicate "there exists at least one form of n".
- 2 is a form of 2, hence P(2);
- 3 is a form of 3, hence P(3);
- For n >= 4, write n = m+2. Substitute m, which satisfies P(m), with one of its forms. This provides one form for n.
All forms of the same length, L, are equivalent with regard to the number of operator symbols (+ or *): their well-formed nature implies the respect of the ([23][\+\*])*[23] regular expression. The number of operators is (L - 1) / 2.
By definition a(n) is the number of operators in any shortest form of n.
EXAMPLE
a(2) = 0; // 2 = 2
a(3) = 0; // 3 = 3
a(4) = 1; // 4 = 2+2
a(5) = 1; // 5 = 2+3
a(6) = 1; // 6 = 2*3
a(7) = 2; // 7 = 2+2+3
a(8) = 2; // 8 = 2+2*3
a(9) = 1; // 9 = 3*3
a(10) = 3; // 10 = 2+2+2*3
MATHEMATICA
a[2]=a[3]=0; a[n_] := a[n] = Block[{f = FactorInteger[n]}, If[Max[First /@ f] <= 3, Total[Last /@ f]-1, Min@ Table[a[j] + a[n-j] + 1, {j, 2, n/2}]]]; Array[a, 104, 2] (* Giovanni Resta, May 16 2017 *)
PROG
(Prolog)
main :-
Depth = 7, retractall(a(_, _)), forall(valid(X, Depth), side_effect(X)),
display_results(2).
valid('2', _). valid('3', _).
valid(X, RemainingDepth) :-
RemainingDepth > 0, NewRemainingDepth is RemainingDepth - 1,
valid(B, NewRemainingDepth), member(O, ['+', '*']), member(A, ['2', '3']),
atomic_list_concat([A, O, B], X).
side_effect(X) :-
read_term_from_atom(X, Y, []), Result is Y,
(a(Result, _) -> true ; (Term =.. [a, Result, X], assertz(Term))).
display_results(M) :-
a(M, Am) -> (
atom_length(Am, L), LL is (L - 1) / 2,
checklist(write, ['a(', M, ') = ', LL, ' // ', M = Am, '\n']),
N is M + 1, display_results(N)
) ; true.
CROSSREFS
KEYWORD
nonn
AUTHOR
Luc Rousseau, May 12 2017
STATUS
approved