Partition Functions via Bit List Operations

Java applet BitList


For a given strictly increasing infinite sequence f = (f1,f2,...) of positive integers
we determine the largest integer which is not representable as a sum of distinct members of the sequence f.
If it exists, this integer is called the threshold of completeness t(f) of the sequence f. For example

t(f) = -1 for the sequence f of all powers of 2,
t(f) = -1 for the sequence f of all positive integers,
t(f) = 128 for the sequence f of all squares,
t(f) = 12758 for the sequence f of all cubes [1,2,3],
t(f) = 5134240 for the sequence f of all 4th powers [3], without knowledge of [1],
t(f) = 67898771 for the sequence f of all 5th powers
(discovered March, 01, 2009, proved May, 23, 2009, without knowledge of [4]),
t(f) = infinity for the sequence f of all powers of 3.

The present Java applet is designed for sequences of powers,
either with fixed exponent n >= 1 and variable basis x >= 1, i.e., f = (xn,(x+1)n,...) (check box Exponential disabled).
or with fixed basis a >= 2 and variable exponent x >= 0, i.e., f = (ax,ax+1,...) (check box Exponential activated).
The check box Function should only be activated for a modest Number of Recursion Steps.

Insider Know How:
Instead of storing the characteristic function of representable integers in a file of bytes [3] on the hard disk
we make use of the Java class java.math.BigInteger as an infinitely extensible bit list in the main memory.
In each recursion step, the method shiftLeft() is used for a translation and the method or() for a superposition of characteristic functions.

Warning. For the sequence of 5th powers, we expect a storage capacity of more than 10MB for the bit lists.
Latest Result (May, 23, 2009): For the sequence of 5th powers, the Java Virtual Machine (VM) has to be tuned at least by the option -Xmx512m.


[1] S. Lin,
Computer experiments on sequences which form integral bases,
pp. 365-370 of J. Leech, editor, Computational Problems in Abstract Algebra. Pergamon, Oxford, 1970.
[2] R. E. Dressler and T. Parker,
Math. Comp., 28 (1974), 313 - 314.
[3] Daniel C. Mayer,
Sharp bounds for the partition function of integer sequences,
BIT 27 (1987), 98 - 110.
[4] Harry L. Nelson,
The Partition Problem,
J. Rec. Math., 20 (1988), 315 - 316.

Back to Algebra.