# Walking on the Hypercube

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!

• Given the rule a[m+1] = xor(a[m], 2^mod(a[m],n)), it's irrelevant if the vertices belong to a hypercube, right? Mar 19, 2016 at 16:21
• Right. If a[m] was on the hypercube, a[m+1] will be too. And as you can assume a[0] to be a valid vertex, you pretty much don't need to care about any hypercube stuff and just follow the rule. Mar 19, 2016 at 16:27
• Where are the hyper ants? Mar 21, 2016 at 10:35

# Jelly, 9 bytes

%⁴2*^µÐḶL


Takes two command-line arguments.

%⁴2*^µÐḶL        A monadic link. Inputs: a_0. b also taken from command line.
%⁴                   a modulo b. ⁴ is second input, b.
2*                 Get 2 to that power
^                and bitwise xor with a.
ÐḶ             All elements of the cycle created when the preceding link
is applied repeatedly, starting with a_0.
L            Length.


Try it here.

import Data.Bits
(y:z:w)%(x:s)|x==y||x==z=[i|(i,r)<-zip[1..]s,r==x]!!0|0<1=w%s
g n=(tail>>=(%)).iterate(\a->xor a$2^mod a n)  This finds the circle by the two-pointers-going-around-in-different-speeds algorithm, and heavily uses/abuses Haskell's approach to lists (for example, the two pointers are actually lists). g is the function that computes the answer. give it n and then a[0] and it will return the number to you (note that n should be defined to be of type Int to avoid type ambiguity). ## JavaScript (ES6), 69 bytes (n,a)=>{g=m=>m^1<<m%n;for(c=1,b=a;(b=g(g(b)))!=(a=g(a));)c++;return c}  Returns 18812 for (23, 10). # MATL, 3837 28 bytes xivt0)2y1G\^Z~yywP=fn~]2M1$


This works in current version(15.0.0) of the language.

Try it online!

### Explanation

x       % take first input: n. Delete (gets copied into clipboard G)
i       % take second input: initial value of a
% do...while loop
v     %   concatenate all stack contents vertically
t0)   %   duplicate. Get last element of that array: current a
2     %   push 2
y     %   duplicate second-top element in stack: current a
1G    %   push first input (n)
\     %   a modulo n
^     %   2 raised to that
Z~    %   xor of that with current a
yy    %   duplicate top two elements in stack: array of old a's and new a
w     %   swap: move array of old a's to top
P     %   reverse that array. So first entry is most recent a (before current)
=f    %   indices of old values that equal current value. There may be 0 or 1
n~    %   is it empty?
]       % if so, continue with a new iteration
2M      % push array of indices. It contains exactly 1 index
1\$      % set 1 input for implicit display function, so it only displays the index


## Pyth, 22 17 bytes

Lx^2%bQbl.uyNuyGE


Explanation:

Lx^2%bQbl.uyNuyGE     Implicit: Q=first line n. E=second line a[0].
Lx^2%bQb              y = lambda b: do one iteration
Then
uyGE     Apply y until a previous result is found.
This makes sure we're in the cycle.
.uyN         Then apply y again until a previous result is found.
Keep all intermediate values but not the repeat.
l             Get the length; i.e. the length of the cycle.


Try it here.