A210659 The smallest possible depth of an arithmetic expression for n using only +, *, parentheses and the minimum number of 1's.

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

Offset: 1

Author

Janis Iraids, Mar 28 2012

Keywords

• nonn

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.

This sequence was discovered by Martins Opmanis and Jānis Iraids.

Examples

			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.
		

Links

• Janis Iraids, Table of n, a(n) for n = 1..10000
• Index to sequences related to the complexity of n

Crossrefs

Cf. A005245, A210660.

Programs

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];
}