Walking on the Hypercube

Question

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!

Answer 1

Jelly, 9 bytes

%⁴2*^µÐḶL

Takes two command-line arguments.

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

Try it here.

Answer 2

Haskell, 124

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).

Answer 3

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).

Answer 4

MATL, 38 37 28 bytes

xi`vt0)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

Answer 5

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.