17
\$\begingroup\$

The goal of this challenge is to check and extend the OEIS sequence A334248: Number of distinct acyclic orientations of the edges of an n-dimensional cube.

Take an n-dimensional cube (if n=1, this is a line; if n=2, a square; if n=3, a cube; if n=4, a hypercube/tesseract; etc), and give a direction to all of its edges so that no cycles are formed. The terms of the sequence are the number of (rotationally and reflectively) distinct orientations that can be obtained.

Example

For n=2, there are 14 ways to assign directions to the edges of a square with no cycles formed:

Acyclic orientations of a cube

However, only three of these are distinct if they are rotated and reflected:

Three distinct acyclic orientations

So when n=2, the answer is 3.


The winner of this challenge will be the program that calculates the most terms when run on my computer (Ubuntu, 64GB RAM) in one hour. If there is a tie, the program that computes the terms in the shortest time will be the winner.

\$\endgroup\$
  • 2
    \$\begingroup\$ You should consider extending the challenge to include n=5. Or make the winning criterion the number of terms that can be computed in under an hour. \$\endgroup\$ – Peter Kagey Apr 22 at 7:44
  • \$\begingroup\$ This is a better criterion, I'll adjust it \$\endgroup\$ – mscroggs Apr 22 at 7:53
  • 5
    \$\begingroup\$ Oh gosh, this is counting among the exponentially many orientations of graphs that are themselves exponential in size, which likely gives doubly exponential growth. Finding more terms for OEIS will be hard. \$\endgroup\$ – xnor Apr 22 at 8:11
  • \$\begingroup\$ I'm afraid running time goes up so quickly that any stupid program works 4 out quickly but quite optimized one can't do with 5 \$\endgroup\$ – l4m2 Apr 22 at 13:56
  • \$\begingroup\$ The OEIS sequence has been updated to reflect that A334248(5) = 12284402192625939. Any hope of computing the next term? Obviously this isn’t something that can be brute forced. \$\endgroup\$ – Peter Kagey Apr 25 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.