[seqfan] Re: A045310 as partitions

hv at crypt.org hv at crypt.org
Wed Nov 30 09:35:13 CET 2016


Thanks Neil, I've done that.

On my computer, the C program takes 12 CPU-minutes to calculate a(6),
using a cache of 2^16 ints (256KB) for the 4-d fragments to minimize
recursion.

Simply extending the existing code for a(7) would in principle require
2^32 as much work, using a cache of 2^32 longs (32GB) - but except for
the preparation of the cache, the work is eminently distributable, so
it's possible that just one or two additional insights might bring that
within practical reach.

If anyone has suggestions in that respect, please do let me know.

Hugo

Neil Sloane <njasloane at gmail.com> wrote:
:Hugo, Maybe you could add a comment or two
:to A045310 saying something like: Equivalently, this is the number of
:decompositions of an n-dimensional cube of size 2 into unit cubes
:(1X1X...X1) and "dominoes" (2X1X1X...X1).", if that is what you are saying
:(I'm not sure what a polycube is either)!
:
:And by all means add your two programs.
:
:Best regards
:Neil
:
:Neil J. A. Sloane, President, OEIS Foundation.
:11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
:Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
:Phone: 732 828 6098; home page: http://NeilSloane.com
:Email: njasloane at gmail.com
:
:
:On Mon, Nov 28, 2016 at 5:43 AM, <hv at crypt.org> wrote:
:
:> I've recently been considering partitions of n-cubes into n-dimensional
:> analogues of polyominoes, and stumbled on A045310 as the number of
:> partitions of an n-cube of side 2 into polyominoes of size at most 2.
:>
:> The identity became obvious once I understood what the Hosoya index
:> represented, but I feel it's worth a comment; however I don't know
:> the terminology for n-dimensional polyominoes, so I'm not sure how
:> to phrase such a comment - Wikipedia has brief mentions of "polycubes"
:> and "polyhypercubes", while Mathworld confusingly defines polycube as
:> "Three-dimensional generalization of the polyominoes to n dimensions".
:>
:> The code I wrote may also be useful - it verifies the existing values,
:> though it would struggle to extend to n=7. Proof of concept is in Perl,
:> and a version fast enough to be useful is in C:
:>   https://github.com/hvds/seq/blob/master/part/find2
:>   https://github.com/hvds/seq/blob/master/part/find2c.c
:>
:> Hugo
:>
:> --
:> Seqfan Mailing list - http://list.seqfan.eu/
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list