login
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.
0

%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