cp's OEIS Frontend

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

%I A210659 #31 Dec 27 2012 11:39:29
%S A210659 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,
%T A210659 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,
%U A210659 5,4,5,2,3,4,2,4,4,4,5,2,2,3,3,4,4,6,4
%N A210659 The smallest possible depth of an arithmetic expression for n using only +, *, parentheses and the minimum number of 1's.
%C A210659 The minimum number of leaves is A005245(n).
%C A210659 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.
%C A210659 This sequence was discovered by _Martins Opmanis_ and Jānis Iraids.
%H A210659 Janis Iraids, <a href="/A210659/b210659.txt">Table of n, a(n) for n = 1..10000</a>
%H A210659 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A210659 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.
%o A210659 (C)
%o A210659 int a(int* rank, int N) { // output rank in the array for values up to N
%o A210659   rank[1]=0;
%o A210659   for(int n=2;n<=N;i++){
%o A210659     int r=n;
%o A210659     for(int a=1;a<=N/2;a++)
%o A210659       if(c(a)+c(n-a)==c(n)){ // c(n) -- the complexity function A005245(n)
%o A210659         int ro=max(rank[a],rank[n-a]);
%o A210659         r=min(r,ro%2==0?ro+1:ro);
%o A210659       }
%o A210659     for(int a=1;a*a<=N;a++)
%o A210659       if(n%a==0&&c(a)+c(n/a)==c(n)){
%o A210659         int ro=max(rank[a],rank[n/a]);
%o A210659         r=min(r,ro%2==0?ro:ro+1);
%o A210659       }
%o A210659     rank[n]=r;
%o A210659   }
%o A210659   return rank[N];
%o A210659 }
%Y A210659 Cf. A005245, A210660.
%K A210659 nonn
%O A210659 1,6
%A A210659 _Janis Iraids_, Mar 28 2012