El periodde una cadena es el desplazamiento más corto distinto de cero, de modo que la cadena coincide con sí misma, ignorando cualquier parte que sobresalga. Entonces, por ejemplo, abcabcabtiene punto 3. Por convención, decimos que si no existe tal cambio, entonces una cadena tiene un período igual a su longitud. Entonces, el período de abcdees 5y el período de aes 1.

En términos más formales, el período de una cadena Ses el mínimo i > 0para que S[1,n-i] == S[i+1,n](indexando desde 1).

Para una cadena S dada de potencia de dos longitudes, calcularemos el período de todos sus prefijos de potencia de dos longitudes. Por ejemplo, considere S = abcabcab. Los períodos que calcularemos son:

'a', 1
'ab', 2
'abca', 3
'abcabcab', 3

De hecho, solo mostraremos el conjunto de períodos, es decir [1, 2, 3, 3].

Para una potencia positiva dada de dos n, considere todas las cadenas binarias posibles S. Recuerde que una cadena binaria es simplemente una cadena de 1sys, 0por lo que existen exactamente 2^nesas cadenas (eso es lo que tiene que ver 2con la potencia n). Para cada uno podemos calcular este conjunto de períodos.

El desafío es escribir código que tome n(una potencia de dos) como entrada y calcule cuántas matrices distintas existen.

Las respuestas para n = 1, 2, 4, 8, 16, 32, 64, 128son:

1, 2, 6, 32, 320, 6025, 216854, 15128807

El conjunto completo de matrices de períodos distintos para n = 4es:

1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4

Puntuación

Ejecutaré su código en mi computadora con Ubuntu durante 10 minutos. Su puntaje es el mayor npor el cual su código termina en ese momento. En el caso de un empate, la respuesta que completa la mayor nvictoria conjunta . En el caso de que haya un empate dentro de 1 segundo en los tiempos, la primera respuesta publicada gana.

Idiomas y bibliotecas

Puede usar cualquier idioma y bibliotecas disponibles que desee. Incluya una explicación completa sobre cómo ejecutar / compilar su código en Linux, si es posible.

Su código realmente debería calcular las respuestas y no, por ejemplo, solo generar valores precalculados.

Entradas principales

• 2 minutos y 21 segundos para n = 128 en C # por Peter Taylor
• 9 segundos para n = 32 en óxido por isaacg

C #, n = 128 en aproximadamente 2:40

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox
{
    class PPCG137436
    {
        public static void Main(string[] args)
        {
            if (args.Length == 0) args = new string[] { "1", "2", "4", "8", "16", "32", "64", "128" };

            foreach (string arg in args)
            {
                Console.WriteLine(Count(new int[(int)(0.5 + Math.Log(int.Parse(arg)) / Math.Log(2))], 0));
            }
        }

        static int Count(int[] periods, int idx)
        {
            if (idx == periods.Length)
            {
                //Console.WriteLine(string.Join(", ", periods));
                return 1;
            }

            int count = 0;
            int p = idx == 0 ? 1 : periods[idx - 1];
            for (int q = p; q <= 1 << (idx + 1); q++)
            {
                periods[idx] = q;
                if (q == p || q > 1 << idx || p + q - Gcd(p, q) > 1 << idx && UnificationPasses(periods, idx, q)) count += Count(periods, idx + 1);
            }

            return count;
        }

        private static int Gcd(int a, int b)
        {
            while (a > 0) { int tmp = a; a = b % a; b = tmp; }
            return b;
        }

        private static bool UnificationPasses(int[] periods, int idx, int q)
        {
            UnionSet union = new UnionSet(1 << idx);
            for (int i = 0; i <= idx; i++)
            {
                for (int j = 0; j + periods[i] < Math.Min(2 << i, 1 << idx); j++) union.Unify(j, j + periods[i]);
            }

            IDictionary<int, long> rev = new Dictionary<int, long>();
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] = 0L;
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] |= 1L << k;

            long zeroes = rev[union.Find(0)]; // wlog the value at position 0 is 0

            ISet<int> onesIndex = new HashSet<int>();

            // This can be seen as the special case of the next loop where j == -1.
            for (int i = 0; i < idx; i++)
            {
                if (periods[i] == 2 << i) onesIndex.Add((2 << i) - 1);
            }
            for (int j = 0; j < idx - 1 && periods[j] == 2 << j; j++)
            {
                for (int i = j + 1; i < idx; i++)
                {
                    if (periods[i] == 2 << i)
                    {
                        for (int k = (1 << j) + 1; k <= 2 << j; k++) onesIndex.Add((2 << i) - k);
                    }
                }
            }

            for (int i = 1; i < idx; i++)
            {
                if (periods[i] == 1) continue;

                int d = (2 << i) - periods[i];
                long dmask = (1L << d) - 1;
                if (((zeroes >> 1) & (zeroes >> periods[i]) & dmask) == dmask) onesIndex.Add(periods[i] - 1);
            }

            long ones = 0L;
            foreach (var key in onesIndex) ones |= rev[union.Find(key)];

            if ((zeroes & ones) != 0) return false; // Definite contradiction!

            rev.Remove(union.Find(0));
            foreach (var key in onesIndex) rev.Remove(key);

            long[] masks = System.Linq.Enumerable.ToArray(rev.Values);

            int numFilteredMasks = 0;
            long set = 0;
            long M = 0;
            for (int i = 1; i <= idx; i++)
            {
                if (periods[i - 1] == 1) continue;

                // Sort the relevant masks to the start
                if (i == idx) numFilteredMasks = masks.Length; // Minor optimisation: skip the filter because we know we need all the masks
                long filter = (1L << (1 << i)) - 1;
                for (int j = numFilteredMasks; j < masks.Length; j++)
                {
                    if ((masks[j] & filter) != 0)
                    {
                        var tmp = masks[j];
                        masks[j] = masks[numFilteredMasks];
                        masks[numFilteredMasks++] = tmp;
                    }
                }

                // Search for a successful assignment, using the information from the previous search to skip a few initial values in this one.
                set |= (1L << numFilteredMasks) - 1 - M;
                M = (1L << numFilteredMasks) - 1;
                while (true)
                {
                    if (TestAssignment(periods, i, ones, masks, set)) break;
                    if (set == 0) return false; // No suitable assignment found

                    // Gosper's hack with variant to reduce the number of bits on overflow
                    long c = set & -set;
                    long r = set + c;
                    set = (((r ^ set) >> 2) / c) | (r & M);
                }
            }

            return true;
        }

        private static bool TestAssignment(int[] periods, int idx, long ones, long[] masks, long assignment)
        {
            for (int j = 0; j < masks.Length; j++, assignment >>= 1) ones |= masks[j] & -(assignment & 1);
            for (int i = idx - 1; i > 0; i--) // i == 0 is already handled in the unification process.
            {
                if (Period(ones, 2 << i, periods[i - 1]) < periods[i]) return false;
            }

            return true;
        }

        private static int Period(long arr, int n, int min)
        {
            for (int p = min; p <= n; p++)
            {
                // If the bottom n bits have period p then the bottom (n-p) bits equal the bottom (n-p) bits of the integer shifted right p
                long mask = (1L << (n - p)) - 1L;
                if ((arr & mask) == ((arr >> p) & mask)) return p;
            }

            throw new Exception("Unreachable");
        }

        class UnionSet
        {
            private int[] _Lookup;

            public UnionSet(int size)
            {
                _Lookup = new int[size];
                for (int k = 0; k < size; k++) _Lookup[k] = k;
            }

            public int Find(int key)
            {
                var l = _Lookup[key];
                if (l != key) _Lookup[key] = l = Find(l);
                return l;
            }

            public void Unify(int key1, int key2)
            {
                int root1 = Find(key1);
                int root2 = Find(key2);

                if (root1 < root2) _Lookup[root2] = root1;
                else _Lookup[root1] = root2;
            }
        }
    }
}

Extender a n = 256 requeriría cambiar a BigIntegerlas máscaras, lo que probablemente mata el rendimiento demasiado para que n = 128 pase sin nuevas ideas, y mucho menos n = 256.

En Linux, compila mono-cscy ejecuta con mono.

Explicación básica

No voy a hacer una disección línea por línea, solo una descripción general de los conceptos.

Como regla general, me complace repetir el orden de 2 ⁵⁰ elementos en un programa combinatorio de fuerza bruta. Para llegar a n = 128, por lo tanto, es necesario utilizar un enfoque que no analice todas las cadenas de bits. Entonces, en lugar de trabajar hacia adelante desde cadenas de bits hasta secuencias de períodos, trabajo hacia atrás: dada una secuencia de períodos, ¿hay una cadena de bits que se da cuenta? Para n = 2 ^x hay un límite superior fácil de 2 ^{x (x + 1) / 2} secuencias de período (vs 2 ^{2 x} cadenas de bits).

Algunos de los argumentos usan el lema de periodicidad de cadena :

Dejar py qser dos períodos de una cadena de longitud n. Si p + q ≤ n + gcd(p, q)entonces gcd(p, q)también es un período de la cadena.

Wlog Asumiré que todas las cadenas de bits en consideración comienzan con 0.

Dada una secuencia de períodos donde es el período del prefijo de longitud 2 ⁱ ( siempre), hay algunas observaciones fáciles sobre posibles valores de :[p1 p2 ... pk]pip0 = 1pk+1

• pk+1 ≥ pkdado que un período de una cadena Stambién es un período de cualquier prefijo de S.

• pk+1 = pk siempre es una extensión posible: simplemente repita la misma cadena primitiva para el doble de caracteres.

• 2k < pk+1 ≤ 2k+1Es siempre una posible extensión. Es suficiente mostrar esto porque una cadena aperiódica de longitud se puede extender a una cadena aperiódica de longitud agregando cualquier letra que no sea su primera letra.pk+1 = 2k+1LL+1

  Tome una cadena Sxde longitud 2 ^k cuyo período es y considere la cadena de longitud 2 ^{k + 1} . Claramente tiene un período de 2 ^k +1. Supongamos que su período es más pequeño.pkSxySSxySq

  Entonces, según la periodicidad, el lema también es un período de , y dado que el mayor divisor es menor o igual que sus argumentos y es el período más pequeño, debemos ser un factor propio de 2 ^k +1. Como su cociente no puede ser 2, tenemos .2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)gcd(2k+1, q)SxySqqq ≤ (2k+1)/3

  Ahora, dado que es un período , debe ser un período de . Pero el período de es . Tenemos dos casos:q ≤ 2kSxySSxSxpk

  1. gcd(pk, q) = pk, o equivalentemente se divide exactamente en .pkq
  2. pk + q > 2k + gcd(pk, q) para que el lema de periodicidad no fuerce un período menor.

  Considere primero el segundo caso. , contradiciendo la definición de como el período de . Por lo tanto, nos vemos obligados a llegar a la conclusión de que es un factor de .pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2qpkSxpkq

  Pero dado que qes un período de Sxy es el período de , el prefijo de longitud es solo copias del prefijo de longitud , por lo que vemos que también es un período de .pkSxqq/pkpkpkSxyS

  Por lo tanto, el período de SxySes o 2 ^k +1. ¡Pero tenemos dos opciones para ! Como máximo, una opción de dará período , por lo que al menos uno dará período 2 ^k +1. QEDpkyypk

• El lema de periodicidad nos permite rechazar algunas de las extensiones posibles restantes.

• Cualquier extensión que no haya pasado una prueba de aceptación rápida o de rechazo rápido debe probarse de manera constructiva.

La construcción de una cadena de bits dada una secuencia de períodos es esencialmente un problema de satisfacción, pero tiene mucha estructura. Existen restricciones de igualdad simples implícitas en cada período de prefijo, por lo que utilizo una estructura de datos de conjunto de unión para combinar bits en grupos independientes. Esto fue suficiente para abordar n = 64, pero para n = 128 fue necesario ir más allá. Empleo dos líneas de argumento útiles:2k - pk

1. Si el prefijo de longitud Mes y el prefijo de longitud tiene punto, entonces el prefijo de longitud debe terminar en . Esto es más poderoso precisamente en los casos que de otro modo tendrían grupos más independientes, lo cual es conveniente.01M-1L > MLL1M
2. Si el prefijo de longitud Mes y el prefijo de longitud tiene período con y termina en entonces debe en extremo hecho en . Esto es más poderoso en el extremo opuesto, cuando la secuencia del período comienza con muchos.0ML > ML - dd < M0d10d

Si no obtenemos una contradicción inmediata al obligar al clúster con el primer bit (se supone que es cero) a uno, entonces fuerza bruta (con algunas micro optimizaciones) sobre los posibles valores para los clústeres no forzados. Tenga en cuenta que el orden está en un número descendente de unidades porque si el bit i^th es uno, entonces el período no puede ser iy queremos evitar períodos que sean más cortos que los que ya están aplicados por la agrupación. Bajar aumenta las posibilidades de encontrar una asignación válida antes de tiempo.

Rust, 32, 10s 11s 29s en mi laptop

Llámalo con el tamaño de bits como argumento de línea de comando.

Técnicas inteligentes: represente cadenas de bits directamente como números, use bittwiddling para verificar los ciclos. Solo busque la primera mitad de las cadenas de bits, aquellas que comienzan con 0, porque la matriz de períodos de una cadena de bits y su inverso (0 intercambiados por 1) son idénticos. Si todas las posibilidades para la posición final ya han ocurrido, no la busco.

Cosas más inteligentes:

Para deduplicar cada bloque (cadenas donde la primera mitad de los bits son iguales) utilizo un vector de bits, que es mucho más rápido que un hashset, ya que las longitudes del ciclo final no necesitan hash.

Además, omito los primeros pasos de la verificación del ciclo, porque sé que el ciclo final no puede ser más corto que el penúltimo ciclo.

Después de muchos perfiles, ahora puedo decir que casi todo el tiempo se usa de manera productiva, por lo que creo que se necesitarán mejoras algorítmicas para mejorar desde aquí. También cambié a enteros de 32 bits para ahorrar un poco más de tiempo.

//extern crate cpuprofiler;
//use cpuprofiler::PROFILER;

extern crate bit_vec;
use bit_vec::BitVec;

use std::collections::HashSet;

fn cycle_len(num: u32, mask: u32, skip_steps: usize) -> usize {
    let mut left = num >> skip_steps;
    let mut mask = mask >> skip_steps;
    let mut steps = skip_steps;
    loop {
        left >>= 1;
        if left == (num & mask) {
            return steps;
        }
        mask >>= 1;
        steps += 1;
    }
}

fn all_cycles(size_log: usize) -> HashSet<Vec<usize>> {
    let mut set = HashSet::new();
    if size_log == 0 {
        set.insert(vec![]);
        return set;
    } else if size_log == 1 {
        set.insert(vec![0]);
        set.insert(vec![1]);
        return set;
    }
    let size: usize = 1 << size_log;
    let half_size: usize = 1 << size_log - 1;
    let shift_and_mask: Vec<(usize, u32)> = (1..size_log)
        .map(|subsize_log| {
            let subsize = 1 << subsize_log;
            (size - subsize, (1 << (subsize - 1)) - 1)
        })
        .collect();
    let size_mask = (1 << (size - 1)) - 1;
    for block in 0..(1 << (half_size - 1)) as u32 {
        let start: u32 = block << half_size;
        if block % 1024 == 0 {
            eprintln!(
                "{} ({:.2}%): {}",
                start,
                start as f64 / (1u64 << size - 1) as f64 * 100f64,
                set.len()
            );
        }
        let leader = {
            let mut cycles = Vec::new();
            for &(shift, mask) in &shift_and_mask {
                let subnum = start >> shift;
                cycles.push(cycle_len(subnum, mask, 0));
            }
            cycles
        };
        let &end = leader.last().unwrap();
        if (end..size).all(|count| {
            let mut new = leader.clone();
            new.push(count);
            set.contains(&new)
        })
        {
            continue;
        }
        let mut subset = BitVec::from_elem(size, false);
        for num in start..start + (1 << half_size) {
            subset.set(cycle_len(num, size_mask, end), true);
        }
        for (unique_cycle_len, _) in subset.into_iter().enumerate().filter(|x| x.1) {
            let mut new_l = leader.clone();
            new_l.push(unique_cycle_len);
            set.insert(new_l);
        }
    }
    set
}

fn main() {
    let size: f32 = std::env::args().nth(1).unwrap().parse().unwrap();
    let size_log = size.log2() as usize;
    //PROFILER.lock().unwrap().start("./my-prof.profile").unwrap();
    let cycles = all_cycles(size_log);
    //PROFILER.lock().unwrap().stop().unwrap();
    println!(
        "Number of distinct arrays of periods of bitstrings of length {} is {}",
        1 << size_log,
        cycles.len()
    );
}

Poner bit-vec = "0.4.4"en su Cargo.toml

Si desea ejecutar esto, clone esto: github.com/isaacg1/cycle luego Cargo build --releasepara compilar, luego Cargo run --release 32para ejecutar.

Óxido , 16

use std::collections::HashSet;
use std::io;

fn main() {
	print!("Enter a pow of two:");
	let mut input_text = String::new();
    io::stdin()
        .read_line(&mut input_text)
        .expect("failed to read from stdin");

    let n_as_string = input_text.trim();
	match n_as_string.parse::<usize>() {
		Ok(n) => {
			let log2 = (n as f64).log(2_f64) as usize;
			if n != 1 << log2 {
				panic!("{} is not a power of two", n);
			}
			let count = compute_count_array(log2, n);
			println!("n = {} -> count = {}", n, count);
		}
		Err(_) => { panic!("{} is not a number", n_as_string); }
	}
}

fn compute_count_array(log2:usize, n: usize) -> usize {
	let mut z = HashSet::new();

	let mut s:Vec<bool> = vec!(false; n);
	loop {
		let mut y:Vec<usize> = vec!();
		for j in 0..log2+1 {
			let p = find_period(&s[0..1<<j]);
			y.push(p);
		}		
		z.insert(y);
		if !next(&mut s) {
			break;
		}
	}
	z.len()
}

#[inline]
fn find_period(s: &[bool]) -> usize {
	let n=s.len();
	let mut j=1;
	while j<n {
		if s[0..n-j] == s[j..n] {
			return j;
		}
		j+=1;
    }
	n
}	

#[inline]
fn next(s:&mut Vec<bool>) -> bool {
	if s[0] {
		s[0] = false;
		for i in 1..s.len() {
			if s[i] {
				s[i] = false;
			} else {
				s[i] = true;
				return true;
			}
		}
		return false
	} else {
		s[0] = true;
	}
	true
}

Pruébalo en línea!

Compilacion: rustc -O <name>.rs

La cadena se implementa como un vector Bool.

• La nextfunción itera a través de las combinaciones;

• El find_periodtoma una rebanada de Bool y devuelve el punto;

• El compute_count_arrayhace el trabajo para cada una "potencia de dos" subsecuencia de cada una de las combinaciones Bools.

Teóricamente, no se espera un desbordamiento hasta que 2^nexceda el valor máximo de u64, es decir n > 64. Este límite podría ampliarse con una prueba costosa en s = [verdadero, verdadero, ..., verdadero].

La mala noticia es: devuelve 317 para n = 16, pero no sé por qué. Tampoco sé si lo hará en diez minutos para n = 32, ya Vec<bool>que no está optimizado para este tipo de cálculo.

EDITAR

1. He logrado eliminar el límite de 64 para n. Ahora, no se bloqueará hasta que nsea ​​mayor que el entero máximo usize.

2. Encontré por qué el código anterior devolvió 317 para n=32. Estaba contando conjuntos de períodos y no conjuntos de períodos. Había tres matrices con los mismos elementos:

   [1, 2, 3, 3, 8] -> {1, 2, 3, 8}
   [1, 2, 3, 8, 8] -> {1, 2, 3, 8}
   [1, 1, 3, 3, 7] -> {1, 3, 7}
   [1, 1, 3, 7, 7] -> {1, 3, 7}
   [1, 1, 3, 3, 8] -> {1, 3, 8}
   [1, 1, 3, 8, 8] -> {1, 3, 8}
   

Ahora funciona. Todavía es lento pero funciona.

C - 16

Falla en valores superiores a 16 cuz de desbordamiento.

No tengo idea de qué tan rápido se ejecuta esto porque estoy en un Chromebook ejecutándolo en repl.it.

Simplemente implementa la pregunta a medida que se lee, revisa todas las cadenas de bits, calcula las matrices de períodos y comprueba si ya se han contado.

#include "stdio.h"
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int per(int s[], int l) {
  int period = 0;
  while (1) {
    period++;

    bool check = 1;
    int i;
    for (i=0; i<l-period; i++) {
      if (s[i]!=s[i+period]) {
        check = 0;
        break;
      }
    }
    if (check) {
      return period;
    }
  }
}

bool perar(int* s, int l, int* b, int i) {
  int n = 1;
  int j=0;
  while (n<=l) {
    b[i*l+j] = per(s, n);
    n=n<<1;
    j++;
  }

  for (j=0;j<i;j++) {
    int k;
    bool check = 1;
    for(k=0; k<l; k++) {
      if (b[j*l+k] != b[i*l+k]) {
        check = 0;
        break;
      }
    }
    if (check) {
      return 0;
    }
  }
  return 1;
}

int main(int argc, char* argv[]) {
  int n;
  scanf("%d", &n);
  puts("Running...");
  int i;
  int c = 0;
  int* a = malloc(n*sizeof(int));
  int m=pow(2, n);
  int* b = malloc(m*n*sizeof(int));
  for (i=0; i<m; i++) {
    int j;
    for (j=0; j<n; j++) {
      a[j] = (i>>j)&1;
    }
    c+=perar(a, n, b, i);
  }
  printf("Answer: %d\n", c);
  return 0;
}

Solo compílelo con gcc, etc.

Haskell

import qualified Data.Set as S
import Data.Bits

period :: Int -> Int -> Int
period num bits = go (bits-2) (div prefix 2) (clearBit prefix $ bits-1)
  where
  prefix = (2^bits-1) .&. num
  go p x y
    | x == y    = p
    | otherwise = go (p-1) (div x 2) (clearBit y p)

allPeriods :: Int ->  [[Int]]
allPeriods n = map periods [0..div(2^n)2-1]
  where
  periods num = map (period num) powers
  powers = takeWhile (<=n) $ iterate (*2) 2

main = readLn >>= print . S.size . S.fromList . allPeriods

Compilar con ghc -O2. Pruébalo en línea!

Se ejecuta en menos de 0.1 segundos en el hardware de mi computadora portátil de 6 años n=16. n=32toma 99 92 minutos, así que estoy factor 9 o 10 de descuento. Intenté almacenar en caché los períodos en una tabla de búsqueda para no tener que volver a calcularlos una y otra vez, pero esto rápidamente se queda sin memoria en mi máquina de 4GB.

Python 2 (PyPy), 16

import sys
import math
def do(n):
 masks=[]
 for i in range(n):
  masks+=[(1<<((2<<i)-1))-1]
 s=set()
 bits=1<<n
 for i in xrange(1<<bits):
  r=[0,]*n
  for j in range(len(masks)):
   mask=masks[j]
   k,c=i>>bits-(2<<j),1
   d=k>>1
   while k&mask^d:
    d>>=1
    mask>>=1
    c+=1
   r[j]=c
  s|={tuple(r)}
 return len(s)
print do(int(math.log(int(sys.argv[1]),2)))

[C ++], 32, 4 minutos

#include <iostream>
#include <vector>

typedef unsigned int u;
template<typename T, typename U>
u Min(T a, U b) {
    return a < b ? a : b;
}

template<typename T, typename U>
u Max(T a, U b) {
    return a > b ? a : b;
}

u Mask(int n) {
    if (n < 0) n = 0;
    return ~((u)(-1) << n);
}
u MASKS[32];

inline u Rshift(u v, int n) {
    return n < 0 ? v >> (-1*n)
    : n > 0 ? v << n
    : n;
}

int GetNextPeriodId(u pattern, int pattern_width, int prior_id) {
    int period = (prior_id % (pattern_width>>1)) + 1;
    int retval = prior_id * pattern_width;

    for (; period < pattern_width; period+=1) {
        u shift = pattern >> period;
        int remainder = pattern_width-period;
        u mask = MASKS[period];

        for (;remainder >= period && !((pattern ^ shift) & mask);
             shift >>= period, remainder -= period);

        if (remainder > period) continue;
        if (remainder == 0 || !((pattern ^ shift) & MASKS[remainder])) {
            retval += (period-1);
            break;
        }
    }
    if (period == pattern_width) {
        retval += pattern_width-1;
    }
    return retval;
}

int ParseInput(int argc, char** argv) {
    if (argc > 1) {
        switch(atoi(argv[1])) {
            case 1:
                return 1;
            case 2:
                return 2;
            case 4:
                return 4;
            case 8:
                return 8;
            case 16:
                return 16;
            case 32:
                return 32;
            default:
                return 0;
        }
    }
    return 0;
}

void PrintId(u id, int patternWidth) {
    for(;patternWidth > 0; id /= patternWidth, patternWidth >>= 1) {
        std::cout << (id % patternWidth)+1 << ",";
    }
    std::cout << std::endl;
}

int TestAndSet(std::vector<bool>& v, int i) {
    int retval = v[i] ? 0 : 1;
    v[i] = true;
    return retval;
}

std::vector<bool> uniques(1<<15);
int uniqueCount = 0;

void FillUniques(u i, int id, int target_width, int final_width) {
    int half_size = target_width / 2;
    u end = 1u<<(half_size-1);
    u mask = MASKS[half_size];
    u lowers[] = { i, (~i)&mask };
    for (u j = 0ul; j < end; j++) {
        u upper = j << half_size;
        u patterns[] = { (upper|lowers[0]), (upper|lowers[1]) };
        for (int k=0; k < sizeof(patterns)/sizeof(patterns[0]); k+=1) {
            int fid = GetNextPeriodId(patterns[k], target_width, id);
            if (target_width != final_width) {
                FillUniques(patterns[k], fid, target_width*2, final_width);
            } else {
                if (TestAndSet(uniques, fid)) {
                    uniqueCount += 1;
                }
            }
        }
    }
}

int main(int argc, char** argv) {
    for (int i = 0; i < 32; i++) {
        MASKS[i] = Mask(i);
    }
    int target_width = 32; // ParseInput(argc, argv);
    if (!target_width) {
        std::cout << "Usage: " << argv[0] << " [1|2|4|8|16|32]" << std::endl;
        return 0;
    }
    if (target_width == 1) {
        std::cout << 1 << std::endl;
        return 0;
    }
    FillUniques(0, 0, 2, target_width);
    std::cout << uniqueCount << std::endl;
    return 0;
}