I recently read up on graph theory, especially hypercubes and thought about interesting ways to construct paths on them. Here's what I came up with.
As you might know, you can construct an n-dimensional hypercube by taking all n-tuples consisting of 1
and 0
as vertices and connect them, iff they differ in one digit. If you interpret these binary digits as an integer number, you end up with a graph with nicely numerated vertices. For example for n=3
:
Let's say you want to take a walk on this hypercube and start at the vertex 0
. Now, how do you determine which vertex you want to visit next? The rule I came up with is to take the number a
of the vertex you are on, flip its mod(a,n)
s bit (zero-based indexing) and go to the resulting vertex.
Formally this rule can be recursively defined as
a[m+1] = xor(a[m], 2^mod(a[m],n)).
By following this rule, you will always stay on the cube and travel along the edges. The resulting path looks like this
As you can see, you will walk in a circle! In fact, in all dimensions and for all starting points your path will end up in a loop. For example for n=14
and a[0]=0
it looks like this
For the avid ambler, the length of his planned route is quite a crucial information. So, your job is to write a function or a program that takes the hypercube dimension n
an the starting vertex a[0]
as inputs and output the number of vertices in the resulting loop.
Test cases
n a[0] Output
-----------------
3 0 6
14 0 50
5 6 8
17 3 346
Rules
- Standard loopholes are forbidden
- Output/Input may be in any suitable format
- You may assume
a[0]
to be a valid vertex
Scoring
Shortest code in bytes wins.
If you have any additional information on this topic, I'd be glad to hear!
a[m+1] = xor(a[m], 2^mod(a[m],n))
, it's irrelevant if the vertices belong to a hypercube, right? \$\endgroup\$a[m]
was on the hypercube,a[m+1]
will be too. And as you can assumea[0]
to be a valid vertex, you pretty much don't need to care about any hypercube stuff and just follow the rule. \$\endgroup\$