O periodde uma string é o menor deslocamento diferente de zero, para que a string corresponda a si mesma, ignorando quaisquer partes que excedam. Então, por exemplo, abcabcabtem período 3. Por convenção, dizemos que, se não houver essa mudança, uma sequência terá um período igual ao seu comprimento. Portanto, o período de abcdeé 5e o período de aé 1.

Em termos mais formais, o período de uma string Sé o mínimo i > 0para que S[1,n-i] == S[i+1,n](indexando de 1).

Para uma determinada sequência S de potência de dois comprimentos, calcularemos o período de todos os seus prefixos de potência de dois comprimentos. Por exemplo, considere S = abcabcab. Os períodos que calcularemos são:

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

Na verdade, apenas produziremos a matriz de períodos, ou seja [1, 2, 3, 3].

Para um determinado poder positivo de dois n, considere todas as seqüências binárias possíveis S. Lembre-se de que uma cadeia binária é simplesmente uma cadeia de se 1es, 0para que exista exatamente 2^nessas cadeias (ou seja, 2a potência n). Para cada um, podemos calcular esse conjunto de períodos.

O desafio é escrever um código que tome n(um poder de dois) como entrada e calcule quantas matrizes distintas existem.

As respostas para n = 1, 2, 4, 8, 16, 32, 64, 128são:

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

O conjunto completo de matrizes de período distintas para n = 4é:

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

Ponto

Vou executar o seu código no meu computador executando o Ubuntu por 10 minutos. Sua pontuação é a maior npara a qual seu código termina nesse período. Em caso de empate, a resposta que completa as maiores nvitórias mais rápidas conjuntas . No caso de empate em 1 segundo nos horários, a primeira resposta postada vence.

Línguas e bibliotecas

Você pode usar qualquer idioma e bibliotecas disponíveis que desejar. Por favor, inclua uma explicação completa de como executar / compilar seu código no Linux, se possível.

Seu código deve realmente calcular as respostas e não, por exemplo, apenas gerar valores pré-computados.

Entradas principais

• 2 minutos e 21 segundos para n = 128 em C # por Peter Taylor
• 9 segundos para n = 32 em Rust por isaacg

C #, n = 128 em cerca de 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;
            }
        }
    }
}

Estender para n = 256 exigiria a troca BigIntegerpara as máscaras, o que provavelmente mata demais o desempenho para que n = 128 passe sem novas idéias, muito menos n = 256.

No Linux, compile mono-csce execute com mono.

Explicação básica

Não vou fazer uma dissecção linha a linha, apenas uma visão geral dos conceitos.

Como regra geral, fico feliz em repetir a ordem de 2 ⁵⁰ elementos em um programa combinatório de força bruta. Para chegar a n = 128, é necessário, portanto, usar uma abordagem que não analise cada cadeia de bits. Então, em vez de avançar de seqüências de bits para seqüências de período, eu trabalho para trás: dada uma sequência de período, existe uma cadeia de bits que a realiza? Para n = 2 ^x, existe um limite superior fácil de 2 ^{x (x + 1) / 2} seqüências de período (vs 2 ^{2 x} bitstrings).

Alguns dos argumentos usam o lema de periodicidade da string :

Let pE qSer dois períodos de uma seqüência de comprimento n. Se p + q ≤ n + gcd(p, q)então gcd(p, q)também é um período da string.

Wlog Vou assumir que todas as cadeias de bits em consideração começam com 0.

Dada uma sequência de períodos em que é o período do prefixo de comprimento 2 ⁱ ( sempre), há algumas observações fáceis sobre os possíveis valores de :[p1 p2 ... pk]pip0 = 1pk+1

• pk+1 ≥ pkjá que um período de uma sequência Stambém é um período de qualquer prefixo de S.

• pk+1 = pk é sempre uma extensão possível: basta repetir a mesma sequência primitiva para o dobro do número de caracteres.

• 2k < pk+1 ≤ 2k+1é sempre uma extensão possível. Basta mostrar isso porque uma cadeia de comprimento aperiódica pode ser estendida a uma seqüência de comprimento aperiódica anexando qualquer letra que não seja sua primeira letra.pk+1 = 2k+1LL+1

  Pegue uma sequência Sxde comprimento 2 ^k cujo período é e considere a sequência de comprimento 2 ^{k + 1} . Claramente tem um período de 2 ^k +1. Suponha que seu período seja menor.pkSxySSxySq

  Então , pela periodicidade, o lema também é um período de , e como o maior divisor é menor ou igual a seus argumentos e é o menor período, precisamos ser um fator adequado de 2 ^k +1. Como seu quociente não pode ser 2, nós temos .2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)gcd(2k+1, q)SxySqqq ≤ (2k+1)/3

  Agora, já que é um período , deve ser um período de . Mas o período de é . Temos dois casos:q ≤ 2kSxySSxSxpk

  1. gcd(pk, q) = pk, ou divide exatamente em exatamente .pkq
  2. pk + q > 2k + gcd(pk, q) para que o lema da periodicidade não force um período menor.

  Considere primeiro o segundo caso. , contradizendo a definição de como o período de . Portanto, somos forçados a concluir que esse é um fator de .pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2qpkSxpkq

  Mas como qé um período de Sxe é o período de , o prefixo de comprimento é apenas cópias do prefixo de comprimento , então vemos que também é um período de .pkSxqq/pkpkpkSxyS

  Portanto, o período de SxySé ou 2 ^k +1. Mas temos duas opções para ! No máximo, uma opção dará período , portanto, pelo menos uma dará período 2 ^k +1. QED.pkyypk

• O lema da periodicidade nos permite rejeitar algumas das possíveis extensões restantes.

• Qualquer extensão que não passou em um teste de aceitação rápida ou de rejeição rápida precisa ser testada de forma construtiva.

A construção de uma cadeia de bits, dada uma sequência de período, é essencialmente um problema de satisfação, mas possui muita estrutura. Existem restrições de igualdade simples implícitas em cada período de prefixo, então eu uso uma estrutura de dados de conjunto de união para combinar bits em clusters independentes. Isso foi suficiente para enfrentar n = 64, mas para n = 128 foi necessário ir além. Emprego duas linhas de argumento úteis:2k - pk

1. Se o prefixo de comprimento Mfor e o prefixo de comprimento tiver um período , o prefixo de comprimento deverá terminar em . Isso é mais poderoso precisamente nos casos que, de outra forma, teriam clusters independentes, o que é conveniente.01M-1L > MLL1M
2. Se o prefixo de comprimento Mfor e o prefixo de comprimento tiver um período com e termina em , ele deve de fato terminar em . Isso é mais poderoso no extremo oposto, quando a sequência do período começa com muitas.0ML > ML - dd < M0d10d

Se não obtivermos uma contradição imediata forçando o cluster com o primeiro bit (assumido como zero) a ser um, então força bruta (com algumas micro otimizações) sobre os valores possíveis para os clusters não forçados. Observe que a ordem está em número decrescente de unidades porque, se o i^th bit for um, o período não poderá ser ie queremos evitar períodos mais curtos que os que já são impostos pelo cluster. Descer aumenta as chances de encontrar uma tarefa válida com antecedência.

Ferrugem, 32, 10s 11s 29s no meu laptop

Chame-o com o tamanho do bits como argumento da linha de comando.

Técnicas inteligentes: representam cadeias de bits diretamente como números, use brincadeiras para verificar se há ciclos. Pesquise apenas a primeira metade das cadeias de bits, começando com 0, porque a matriz de períodos de uma cadeia de bits e seu inverso (0s trocados por 1s) são idênticos. Se todas as possibilidades para a posição final já ocorreram, eu não a busco.

Coisas mais inteligentes:

Para desduplicar cada bloco (cadeias em que a primeira metade dos bits são iguais) eu uso um vetor de bits, que é muito mais rápido que um hashset, pois os comprimentos finais do ciclo não precisam de hash.

Além disso, pulo as primeiras etapas da verificação do ciclo, porque sei que o ciclo final não pode ser mais curto que o penúltimo ciclo.

Depois de muitos perfis, agora posso dizer que quase todo o tempo está sendo usado de forma produtiva, portanto, melhorias algorítmicas serão necessárias para melhorar daqui, eu acho. Também mudei para números inteiros de 32 bits para economizar um pouco mais de tempo.

//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()
    );
}

Colocar bit-vec = "0.4.4" seu Cargo.toml

Se você deseja executar isso, clone-o: github.com/isaacg1/cycle, em seguida, Cargo build --releasepara compilar e, em seguida, Cargo run --release 32para executar.

Ferrugem , 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
}

Experimente online!

Compilação: rustc -O <name>.rs

A cadeia é implementada como um vetor Bool.

• A nextfunção itera através das combinações;

• O find_periodpega uma fatia Bool e retorna o ponto;

• O compute_count_arrayfaz o trabalho para cada subsequência "poder de dois" de cada combinação de Bools.

Teoricamente, nenhum estouro é esperado até 2^nexceder o valor máximo de u64, ou seja,n > 64 . Esse limite pode ser ultrapassado com um teste caro em s = [verdadeiro, verdadeiro, ..., verdadeiro].

A má notícia é: retorna 317 para n = 16, mas não sei por que. Também não sei se isso acontecerá em dez minutos para n = 32, pois o Vec<bool>não é otimizado para esse tipo de computação.

EDITAR

1. Eu consegui remover o limite de 64 para n. Agora, ele não trava até que nseja maior que o número máximo de tamanho máximo.

2. Eu descobri por que o código anterior retornou 317 para n=32. Eu estava contando conjuntos de períodos e não matrizes de períodos. Havia três matrizes com os mesmos 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}
   

Agora funciona. Ainda é lento, mas funciona.

C - 16

Ele falha em valores maiores que 16 cuz de estouro.

Não tenho ideia de quão rápido isso é executado, porque estou em um chromebook executando-o em repl.it.

Apenas implementa a pergunta enquanto lê, analisa todas as seqüências de bits, calcula as matrizes de período e verifica se elas já foram contadas.

#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;
}

Basta compilá-lo com o 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

Compile com ghc -O2. Experimente online!

É executado em menos de 0,1 segundo no meu laptop de 6 anos n=16. n=32leva 99 92min, então estou com fator 9 ou 10 de folga. Tentei armazenar em cache os períodos em uma tabela de pesquisa para não precisar recalculá-los repetidamente, mas isso fica rapidamente sem memória na minha máquina de 4 GB.

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;
}