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
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
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
a=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 as inputs and output the number of vertices in the resulting loop.
n a Output ----------------- 3 0 6 14 0 50 5 6 8 17 3 346
- Standard loopholes are forbidden
- Output/Input may be in any suitable format
- You may assume
ato be a valid vertex
Shortest code in bytes wins.
If you have any additional information on this topic, I'd be glad to hear!