|
| |
|
|
A286528
|
|
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
|
|
|
|
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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
