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,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.

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

Links

Janis Iraids, Table of n, a(n) for n = 1..10000

Index to sequences related to the complexity of n

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

Cf. A005245, A210660.

Sequence in context: A186181 A324983 A147561 * A103266 A185150 A299229

Adjacent sequences: A210656 A210657 A210658 * A210660 A210661 A210662

Keyword

nonn

Author

Janis Iraids, Mar 28 2012

Status

approved