|
| |
|
|
A210659
|
|
The smallest possible depth of an arithmetic expression for n using only +, *, parentheses and the minimum number of 1's.
|
|
2
|
|
|
|
0, 1, 1, 1, 1, 2, 3, 2, 2, 2, 3, 2, 3, 4, 2, 2, 3, 2, 3, 2, 4, 4, 5, 2, 2, 4, 2, 3, 3, 2, 3, 2, 3, 4, 4, 2, 3, 4, 4, 2, 3, 4, 5, 4, 2, 3, 3, 2, 3, 2, 4, 4, 5, 2, 3, 4, 4, 4, 5, 2, 3, 4, 4, 2, 3, 4, 5, 4, 5, 4, 5, 2, 3, 4, 2, 4, 4, 4, 5, 2, 2, 3, 3, 4, 4, 6, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
COMMENTS
|
The minimum number of leaves is A005245(n).
The tree of an arithmetic expression for n is a rooted tree with the number 1 in leaves and addition or multiplication in inner nodes such that the inner nodes correspond to operations in the expression and its children are the operands of said operation. Adjacent additions (and multiplications) are allowed to be merged and typically give smaller depth.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
4 can be written as (1+1)*(1+1) or 1+1+1+1 with a minimum number of ones, but the depth of the tree of the latter expression is smaller - 1 compared to 2 - so a(4)=1.
|
|
|
PROG
|
(C)
int a(int* rank, int N) { // output rank in the array for values up to N
rank[1]=0;
for(int n=2; n<=N; i++){
int r=n;
for(int a=1; a<=N/2; a++)
if(c(a)+c(n-a)==c(n)){ // c(n) -- the complexity function A005245(n)
int ro=max(rank[a], rank[n-a]);
r=min(r, ro%2==0?ro+1:ro);
}
for(int a=1; a*a<=N; a++)
if(n%a==0&&c(a)+c(n/a)==c(n)){
int ro=max(rank[a], rank[n/a]);
r=min(r, ro%2==0?ro:ro+1);
}
rank[n]=r;
}
return rank[N];
}
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
