June 13, 2017: fixed an overflow error when calculating the total in the C# version; some minor typos fixed.
The code in these projects counts sum free sets.
"A sum-free set S is a set for which the intersection of S and the
sumset S+S is empty."
http://mathworld.wolfram.com/Sum-FreeSet.html
For example, the set of all odd numbers is sum free. {1, 2} is not sum
free because 1+1=2.
The novel aspect of this application is avoiding sums on
individual elements of sets. Instead, the set is represented by its
characteristic identity (each bit is one element); the associated sums
of a set are also stored in a characteristic identity. Determining
whether an element can be added to a set is then equivalent to testing
if a bit is set. Adding an element to a set is slightly more involved,
but still much faster than computing sums on every combination of elements.
-----
Why does this work? Consider the characteristic identity of a set.
sfs = 00000101011010101101011 ...
If one is a member, then a fast check for inconsistency is
((sfs | (sfs >> 1)) > 0)
That is, elements that differ by one.
If two is a member, then a fast check for inconsistency is
((sfs | (sfs >> 2)) > 0)
That is, elements that differ by two.
etc.
In fact, when adding an element to a set these potential inconsistencies
are calculated (based on set membership). This is referred to as the "cover"
as it covers any bit positions that can not be added. It turns out adding
a new member is as easy as 1) testing whether the bit is unset in the cover
then 2) extending the existing cover.
The entire catalog of known sum free sets is stored in memory. Extending
"out" to a higher number is equivalent to adding an extra bit (based on the
algorithm above) to every known set. Erdős proved that the number
of sum free sets is
2^(1/2 + o(1))n
and in fact, extending two extra numbers (bits) approximately doubles
the amount of memory used.
-----
I had hoped to extend the known values a bit higher, but resource
use is rather high. A007865(52) uses approximately 30 GB of RAM (C# version).
I was, perhaps, rather optimistic and forked the C# version to a c++
version. The C# version uses UInt64 as the data type to store characteristic
identities (can compute sets 1..64). The c++ version uses a
custom 128 bit data type, which is simply two uint64_t's. (I did consider
an arbitrary precision implementation such as with GMP but decided on
simplicity, but perhaps that would have been better optimized ... ). The c++
version is a small amount faster but uses much more memory.
Once RAM is exhausted, higher counts can be achieved by computing
set membership sequentially (see EXTEND_MAX_NUMBER_BY). This is
expensive, and grows at a factor of 2^n.
Other than the differences in primary data type the C# version and c++
version should yield the same results, and the code is identical
where possible. I have used a traditional c naming convention
across both files for the sake of consistency...
The C# program, at least when compiled with Visual Studio 2017,
requires an x64 target and large objects. Make sure this is
in the app.config:
<runtime>
<gcAllowVeryLargeObjects enabled="true" />
</runtime>
-----
The last thing worth mentioning is a minor detour I explored while it was
convenient: Count the number of ways elements in the interval [1,m] can
be partitioned into k sum free sets. This is commented out in the
main loop (CalculatePartitionNumber). The counts will yield the
Schur numbers (http://mathworld.wolfram.com/SchurNumber.html) but
getting there is achieved via recursion, and becomes
intractable very quickly.
-----
gmail me at benjaminaburns
Download: