cp's OEIS Frontend

A192099 Least number of parts in a partition of n into signed terms of the form 2^k-1.

%I A192099 #25 Aug 14 2018 09:00:58
%S A192099 1,2,1,2,3,2,1,2,3,2,3,2,3,2,1,2,3,2,3,4,3,2,3,2,3,4,3,2,3,2,1,2,3,2,
%T A192099 3,4,3,2,3,4,3,4,3,4,3,2,3,2,3,4,3,4,3,4,3,2,3,4,3,2,3,2,1,2,3,2,3,4,
%U A192099 3,2,3,4,3,4,3,4,3,2,3,4,3,4,5,4,3,4,3,4
%N A192099 Least number of parts in a partition of n into signed terms of the form 2^k-1.
%C A192099 Another interpretation: Let T be the infinite binary tree with all leaves at the same level. Then a(n) is the least number of edges in any cut (X,Y) where |X| = n.
%H A192099 G. C. Greubel, <a href="/A192099/b192099.txt">Table of n, a(n) for n = 1..10000</a>
%H A192099 Frank Ruskey, Sunil Chandran, and Anita Das, <a href="http://www.crm.umontreal.ca/CanaDAM2009/pdf/ruskey.pdf">Isoperimetric sequences for infinite complete binary trees and their relation to meta-Fibonacci sequences and signed almost binary partitions</a>, talk at CANADAM, 2009.
%F A192099 Let d(n) = floor(log(n)/log(2)). Then a(n) = 1 + min{ a(n-(2^d(n)-1)), a((2^(d(n)+1)-1)-n) } with a(0)=0 and a(1)=1.
%e A192099 a(43) = 3 since 43 = 31+15-3 and there is no way to write 43 using fewer terms of the form 2^k-1.
%e A192099 The smallest value of n for which a(n) = 5 is 83 = 31+15+7-3+1.
%t A192099 a[n_]:= If[n < 2, Boole[n == 1], With[{m = IntegerLength[ n, 2] - 1}, a[n] = 1 + Min[ a[n - (2^m - 1)], a[(2^(m + 1) - 1) - n]]]] (* _Michael Somos_, Jul 28 2011 *)
%o A192099 (PARI) a(n)={ local(d); if ( n<=1, return(n) ); d = #binary(n)-1; return(1 + min( a(n-(2^d-1)), a((2^(d+1)-1)-n)) ); }
%K A192099 nonn
%O A192099 1,2
%A A192099 _Frank Ruskey_ and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 28 2011