Unique connections of N circularly-spaced points

[cnoocy]

This is written up pretty informally. It's based on some doodling at work, which turned into a morning of coding a few weeks ago.

The problem is this: How many unique ways are there to connect N evenly spaced points? By "unique" I mean not having any rotations or reflections in the set. Here's the full sets for order 1 to 4:




The code I wrote uses python's long integer and bit arithmetic code to figure out the sequence up to order 8:
1:1
2:2
3:4
4:19
5:136
6:3036
7:151848
8:16814116

Essentially, I represent each possible connection of N points as a binary number, then determine whether any of its reflections or rotations has a lower value. If any do, it's not the "canonical" version of that set, and it gets discarded. The problem with this approach, though I think it's the fastest, is that the time taken goes up very quickly. 8 took 6 hours or so to run, and checked 2²⁸ configurations. 9 would check 2³⁶ configurations and would therefore take about 64 days.

So that's as far as I'm likely to take this investigation. I'm writing it up here for general interest, and for other people to pick it up if they like.

PDF including Order 5

Python code

Comments

[cnoocy]

I didn't mean to shut you down earlier. That's actually very useful, and has some similarities to an approach I discussed with someone on IM this afternoon, but I don't want to steal his thunder if he posts more about his approach later.

[rhu]

I didn't take it as a shut-down. No worries.