Math::NumSeq::BalancedBinary -- balanced 1,0 bits
use Math::NumSeq::BalancedBinary; my $seq = Math::NumSeq::BalancedBinary->new; my ($i, $value) = $seq->next;
This sequence is integers with 1-bits and 0-bits balanced like parentheses,
starting i=1 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, ...
Written in binary it's as if a 1-bit is an opening "(" and a 0-bit is a closing ")".
i binary parens --- -------- ---------- 1 10 () 2 1010 () () 3 1100 (()) 4 101010 () () () 5 101100 () (()) 6 110010 (()) () 7 110100 (() ()) 8 111000 ((())) 9 10101010 () () () () 10 10101100 () () (())
Balanced means the total number of 1s and 0s are the same, and reading from high to low has count 1s >= count 0s at all times, ie. no closing ")" without a preceding matching open "(".
Because the number of 1s and 0s are equal the width is always an even 2*n. The number of values with a given width is the Catalan number (2n)!/(n!*(n+1)!). For example as shown above there are 5 values with 6 bits, per Catalan(6/2)=5.
These values correspond to binary trees where each node may have a left and/or right child. Such a tree can be encoded by writing
0 if no node (empty tree) 1,left,right at a node
The "left" and "right" parts are the left and right legs from the node written out recursively. If those legs are both empty (the node is a leaf) then they're empty and are "0" each, otherwise more 1s and 0s. For example, going depth-first,
d / b c => 11001010[0] \ / ab cd ^-final zero of encoding omitted a
At "a" write 1 and recurse to write its left and right legs. The left leg is "b" so write 1 and its two legs are empty so write 0,0. That completes the "b" sub-tree so resume at the right leg of "a" which is 1 for "c" and descend to the left and right of "c". The left of "c" is empty so write 0. The right of "c" is "d" so write 1 and the two empty legs of "d" are 0,0. The very final 0 is dropped.
This encoding can be applied breadth-first too by pushing the left and right descents onto a queue of pending work, instead of onto a stack by recursing. In both cases there's an extra final 0 which is dropped. This 0 arises because in any binary tree with K nodes there are K+1 empty legs, which would give K many 1-bits and K+1 many 0-bits.
In this encoding the balanced binary condition "count 1s >= count 0s" corresponds to there being at least one unfinished node at any time in the traversal (by whatever node order).
The code here acts on values as numbers but encodings like this are probably better handled as a list or string of bits.
A cute interpretation of the opens and closes is as up and down slopes of a mountain range. 1-bit for up, 0-bit for down. For example,
/\ / \ /\ / \/ \ / \/\ ---------------- 11110001100010
The mountain range must end at its starting level, and cannot descend below the starting level. Numerical order of the values means wider mountain ranges are after narrower ones, and that two ranges of equal width and the same for some initial distance are ordered by down-slope preceding up-slope.
See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.
$seq = Math::NumSeq::BalancedBinary->new ()
Create and return a new sequence object.
$value = $seq->ith($i)
Return the $i'th balanced binary number.
$i
$i = $seq->value_to_i($value)
If $value is balanced binary then return its index i. If $value is not balanced binary then return undef.
$value
undef
$i = $seq->value_to_i_ceil($value)
$i = $seq->value_to_i_floor($value)
Return the index i of $value or if $value is not a balanced binary integer then return the i of the next higher or lower value, respectively.
$bool = $seq->pred($value)
Return true if $value is balanced binary.
When stepping to the next value the number of 1s and 0s does not change, within a width 2*w block, only the 1s move to make a numerically higher value. The simplest is an isolated low 1-bit. It must move up one place. For example,
11100100 -> 11101000
If the low 1 has a 1 above it then that bit must move up and the lower one goes to the end of the value. For example
1110011000 -> 1110100010
In general the lowest run of 1-bits is changed to have the highest of them move up one place and the rest move down to be a 1010..10 pattern at the low end. For example a low run of 3 bits
1111100111000000 -> 1111101000001010 ^ ^ ^ up end
The final value in a 2*w block is all 1s at the top. It becomes an alternating 1010..10 with an extra 1-bit and 0-bit as the first of the next bigger block. For example
111000 last 6-bit value -> 10101010 first 8-bit value
As described above there are Catalan(w) many values with 2*w bits. The width of the i'th value can be found by successively subtracting C(1), C(2), etc until reaching a remainder i < C(w), giving width 2*w with w many "1"s and w many "0"s.
After outputting some bits there will be some number z many "0"s and n many "1"s yet to be output. The choice is then to output either 0 or 1 and reduce z or n accordingly.
numvalues(z,n) = number of sequences of z "0"s and n "1"s with remaining 1s >= remaining 0s at all points output 0 if i < numvalues(z-1,n) 1 if i >= numvalues(z-1,n) and subtract numvalues(z-1,n) for the "0..." combinations skipped
numvalues() is the "Catalan table" constructed by
for z=1 upwards numvalues(z,0) = 1 for n = 1 to z numvalues(z,n) = numvalues(z-1,n) # the 0... forms + numvalues(z,n-1) # the 1... forms
Each numvalues(z,n-1) is the previous value calculated, so
for z=1 upwards t = numvalues(z,0) = 1 for n = 1 to z t += numvalues(z-1,n) numvalues(z,n) = t
The last entry numvalues(w,w) in each row is Catalan(w), so that can be used for the initial i subtractions seeking the width w. If building or extending a table each time then stop the table at that point.
Catalan(w) grows as a little less than a power 4^w so the table has a little more than log4(i) many rows.
Math::NumSeq, Math::NumSeq::Catalan, Math::NumSeq::Fibbinary
http://user42.tuxfamily.org/math-numseq/index.html
Copyright 2012 Kevin Ryde
Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.
To install Math::NumSeq, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::NumSeq
CPAN shell
perl -MCPAN -e shell install Math::NumSeq
For more information on module installation, please visit the detailed CPAN module installation guide.