Irreducible parity vectors

General
1

Consider the set of parity vectors of size n such that:

  • None is a rotation of any other one (also known as necklace problem)
  • None is a power of a smaller one

These parity vectors, which for a like of a better term I call “prime” parity vectors (don’t hesitate if you have a better name!) are interesting because they are a restricted family which is enough to enumerate if you’re looking for a nontrivial cycle.

Here’s their number starting at n=0:

1,2,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710

Here is a Python function to enumerate them:

def divisors(n):
    result = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            result.add(i)
            result.add(n // i)
    return sorted(result)

def is_power(pv):
    for d in divisors(len(pv)):
        if d == len(pv):
            continue
        if pv == pv[:d]*(len(pv)//d):
            return True
    return False

def enumerate_pv_without_rotation_and_without_powers(len_pv):
    seen = {}
    for pv in itertools.product([0,1], repeat=len_pv):
        pv_c = coreli.ParityVector(pv)
        rot_seen = False
        for i in range(len(pv)):
            pv_c_r = pv_c.rotate(i)
            if tuple(pv_c_r.parity_vector) in seen:
                rot_seen = True
                break
        if rot_seen:
            continue

        seen[pv] = True

        if is_power(pv):
            continue
        
        yield pv

Here are all of them up to size 7:

 [()],
 [(0,), (1,)],
 [(0, 1)],
 [(0, 0, 1), (0, 1, 1)],
 [(0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 1, 1)],
 [(0, 0, 0, 0, 1),
  (0, 0, 0, 1, 1),
  (0, 0, 1, 0, 1),
  (0, 0, 1, 1, 1),
  (0, 1, 0, 1, 1),
  (0, 1, 1, 1, 1)],
 [(0, 0, 0, 0, 0, 1),
  (0, 0, 0, 0, 1, 1),
  (0, 0, 0, 1, 0, 1),
  (0, 0, 0, 1, 1, 1),
  (0, 0, 1, 0, 1, 1),
  (0, 0, 1, 1, 0, 1),
  (0, 0, 1, 1, 1, 1),
  (0, 1, 0, 1, 1, 1),
  (0, 1, 1, 1, 1, 1)],
 [(0, 0, 0, 0, 0, 0, 1),
  (0, 0, 0, 0, 0, 1, 1),
  (0, 0, 0, 0, 1, 0, 1),
  (0, 0, 0, 0, 1, 1, 1),
  (0, 0, 0, 1, 0, 0, 1),
  (0, 0, 0, 1, 0, 1, 1),
  (0, 0, 0, 1, 1, 0, 1),
  (0, 0, 0, 1, 1, 1, 1),
  (0, 0, 1, 0, 0, 1, 1),
  (0, 0, 1, 0, 1, 0, 1),
  (0, 0, 1, 0, 1, 1, 1),
  (0, 0, 1, 1, 0, 1, 1),
  (0, 0, 1, 1, 1, 0, 1),
  (0, 0, 1, 1, 1, 1, 1),
  (0, 1, 0, 1, 0, 1, 1),
  (0, 1, 0, 1, 1, 1, 1),
  (0, 1, 1, 0, 1, 1, 1),
  (0, 1, 1, 1, 1, 1, 1)]
2

This is more or less the same as Lagarias’ irreducible cycles (arising naturally in the rational/2-adic extension of the Collatz function). See Tables 2.1 and 2.2 in The set of rational cycles for the 3x+1 problem.

1 Like
3

Ah!! Great to know, thank you for the pointer :slight_smile:

4

Right on.

I think there’s this many with length k and weight x:

\cfrac{1}{k} \sum_{j \mid \gcd(k,x)} \binom{k/j}{x/j} \mu(j)

Moebius “mu”.

As k and x get bigger, this gets pretty close to \binom{k}{x} / k, since so few vectors are periodic like that.

(Math Kook book p. 56)

1 Like