%I #29 Jan 16 2024 12:10:57
%S 0,0,1,1,1,2,2,1,3,2,2,3,3,3,3,4,2,4,3,3,4,4,3,5,4,2,5,3,3,4,4,4,5,5,
%T 3,6,4,4,5,5,5,6,6,5,7,6,4,7,5,5,6,6,3,7,4,4,5,5,5,6,6,5,5,6,6,6,7,7,
%U 7,8,4,7,5,5,6,6,6,7,7,3,8,4,4,5,5,5,6,6,5,7,6,6,7,7,5,7,6,6,7,7,7,8,8,7
%N a(n) is the number of operator symbols in any shortest well-formed arithmetic expression exclusively made of symbols { 2, 3, +, * } that evaluates to n.
%C The meaning of * is: multiply.
%C Let's abbreviate: "form of n" = "well-formed arithmetic expression exclusively made of symbols { 2, 3, +, * } that evaluates to n".
%C Any n superior or equal to 2 has forms. Proof: by recursion.
%C Let P(n) be the predicate "there exists at least one form of n".
%C - 2 is a form of 2, hence P(2);
%C - 3 is a form of 3, hence P(3);
%C - For n >= 4, write n = m+2. Substitute m, which satisfies P(m), with one of its forms. This provides one form for n.
%C 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.
%C By definition a(n) is the number of operators in any shortest form of n.
%e a(2) = 0; // 2 = 2
%e a(3) = 0; // 3 = 3
%e a(4) = 1; // 4 = 2+2
%e a(5) = 1; // 5 = 2+3
%e a(6) = 1; // 6 = 2*3
%e a(7) = 2; // 7 = 2+2+3
%e a(8) = 2; // 8 = 2+2*3
%e a(9) = 1; // 9 = 3*3
%e a(10) = 3; // 10 = 2+2+2*3
%t 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 *)
%o (Prolog)
%o main :-
%o Depth = 7, retractall(a(_, _)), forall(valid(X, Depth), side_effect(X)),
%o display_results(2).
%o valid('2', _). valid('3', _).
%o valid(X, RemainingDepth) :-
%o RemainingDepth > 0, NewRemainingDepth is RemainingDepth - 1,
%o valid(B, NewRemainingDepth), member(O, ['+', '*']), member(A, ['2', '3']),
%o atomic_list_concat([A, O, B], X).
%o side_effect(X) :-
%o read_term_from_atom(X, Y, []), Result is Y,
%o (a(Result, _) -> true ; (Term =.. [a, Result, X], assertz(Term))).
%o display_results(M) :-
%o a(M, Am) -> (
%o atom_length(Am, L), LL is (L - 1) / 2,
%o checklist(write, ['a(', M, ') = ', LL, ' // ', M = Am, '\n']),
%o N is M + 1, display_results(N)
%o ) ; true.
%K nonn
%O 2,6
%A _Luc Rousseau_, May 12 2017