|
| |
|
|
A192099
|
|
Least number of parts in a partition of n into signed terms of the form 2^k-1.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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.
|
|
|
EXAMPLE
|
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.
|
|
|
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 *)
|
|
|
PROG
|
(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)) ); }
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Frank Ruskey and Yuji Yamauchi (eugene.uti(AT)gmail.com), Jul 28 2011
|
|
|
STATUS
|
approved
|
| |
|
|
