To use:
make #Compile the programs
brute 4 #Find vdw(2,4) by brute force
findmax 0010010 #Find the longest chain in 0010010
percent 3 8 100 #Approximate how many length 8 bitstrings are 3-chain free over 100 trials
Format:
brute <chain length (k)>
Finds the longest bitstrings that are k-chain free,
effectively calculating vdw(2, k) by brute force.
Only for small numbers.
|
chain length
| = |
how long a chain to avoid when doing the search
|
findmax <bitstring>
Finds the longest chain in the given bitstring.
Runs in quadratic time.
|
bitstring
| = |
the bitstring to be searched
|
percent <chain length (k)> <length (n)> <# trials (t)>
Approximates how many bitstrings of length n are k-chain free
by pseudorandomly generating t of them and checking.
|
chain length
| = |
what length chain counts
|
|
length
| = |
the length of the bitstrings to use
|
|
# trials
| = |
how many trials to run
|
Technical:
The algorithm for finding the longest chain
is based on the case where distance
is restricted to 1 (ordinary sequential).
To find the longest, you just need to count
and restart whenever the value changes.
So, to do this for multiple distances,
just iterate through the possible distances (d).
Each d will make the bitstring approximate n/d
in length, but you have to also go through the
d starting positions (the modulus). These cancel,
leaving a O(n²) time algorithm. For the
case of a k-chain, you know that the maximum
distance possible is n/(k-1) (k-1 because the positions
start at 0, so for example (0,11) with k=4 gives
0,11,22,33, not 44). So this takes O(n²/k) time.
The brute force program takes advantage of the fact
that a k-chain free bitstring has a k-chain free prefix.
This allows us to eliminate large regions from being
searched fruitlessly. Everytime it finds a bitstring
of length greater than or equal to the current best,
it prints it. This means that you ultimately get
the longest k-chain free bitstrings. Finding one
k-chain free bitstring establishes a lower bound
on the possible value of vdw(2,k). Finding all
of them establishes the exact value.
Observation:
Running "brute 4" shows an interesting pattern. The optimum
bitstrings are about identical except for every 11th bit.
Having structures like this might allow for an easy way
to get large k-chain free bitstrings, and in the case of
k=4, optimum ones. "brute 3" also seems to have 11 spacing.
Note that there is also a suffix and prefix.
Is there something special about 11 spacing?
Downloads: