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

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, 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, 3, 2, 3, 4, 3, 4, 3, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 4, 3, 4

Offset: 1

Author

Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 28 2011

Keywords

• nonn

Comments

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.

Examples

			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.
The smallest value of n for which a(n) = 5 is 83 = 31+15+7-3+1.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..10000
• Frank Ruskey, Sunil Chandran, and Anita Das, Isoperimetric sequences for infinite complete binary trees and their relation to meta-Fibonacci sequences and signed almost binary partitions, talk at CANADAM, 2009.

Programs

Mathematica

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 *)

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

Formula

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.