periodСтрок является кратчайшим ненулевым сдвигом так , что строка соответствует самому себе, игнорируя любые детали , которые сверхмандаты. Так, например, abcabcabесть период 3. По соглашению мы говорим, что если такого сдвига нет, то строка имеет период, равный ее длине. Итак, период abcdeесть 5и период aесть 1.

В более формальных терминах период строки Sявляется минимальным, i > 0так что S[1,n-i] == S[i+1,n](индексация из 1).

Для данной строки S степени двух длин мы вычислим период всех ее префиксов степени двух длин. Например, рассмотрим S = abcabcab. Периоды, которые мы рассчитаем:

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

Фактически, мы просто выведем массив периодов [1, 2, 3, 3].

Для данной положительной степени двойки nрассмотрим все возможные двоичные строки S. Напомним, что бинарная строка - это просто строка 1s и 0s, так что именно 2^nтаких строк (то есть 2в степени n). Для каждого мы можем вычислить этот массив периодов.

Задача состоит в том, чтобы написать код, который принимает n(степень два) в качестве входных данных и вычисляет, сколько различных таких массивов существует.

Ответы для n = 1, 2, 4, 8, 16, 32, 64, 128:

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

Полный набор различных массивов периодов для n = 4:

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

Гол

Я буду запускать ваш код на моем компьютере с Ubuntu в течение 10 минут. Ваша оценка самая большаяn для которой ваш код заканчивается в это время. В случае ничьей, ответ, который завершает объединение nсамых больших быстрых побед. В случае, если в течение 1 секунды есть связь по времени, первый опубликованный ответ выигрывает.

Языки и библиотеки

Вы можете использовать любой доступный язык и библиотеки, которые вам нравятся. Пожалуйста, включите полное объяснение того, как запустить / скомпилировать ваш код в Linux, если это возможно.

Ваш код должен фактически вычислять ответы, а не, например, просто выводить предварительно вычисленные значения.

Ведущие записи

• Питер Тейлор: 2 минуты 21 секунда для n = 128 в C #
• 9 секунд для n = 32 в Rust от isaacg

C #, n = 128 примерно в 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;
            }
        }
    }
}

Расширение до n = 256 потребовало бы переключения BigIntegerна маски, что, вероятно, слишком сильно снижает производительность, чтобы n = 128 мог пройти без новых идей, не говоря уже о n = 256.

Под Linux скомпилируйте mono-cscи выполните с mono.

Основное объяснение

Я не собираюсь делать построчное рассечение, просто обзор концепций.

Как правило, я рад перебрать порядка 2 ⁵⁰ элементов в комбинаторной программе грубой силы. Поэтому, чтобы получить n = 128, необходимо использовать подход, который не анализирует каждую цепочку битов. Таким образом, вместо того чтобы работать вперед от цепочек битов к последовательностям периодов, я работаю задом наперед: есть ли последовательность периодов, есть ли цепочка битов, которая ее реализует? Для n = 2 ^x существует простая верхняя граница 2 ^{x (x + 1) / 2} последовательностей периодов (против 2 ^{2 x} цепочек битов).

Некоторые аргументы используют лемму периодичности строки :

Позвольте pи qбыть два периода строки длины n. Если p + q ≤ n + gcd(p, q)то gcd(p, q)это также период строки.

Wlog Я предполагаю, что все рассматриваемые цепочки битов начинаются с 0.

Учитывая последовательность периодов, где есть период префикса длины 2 ⁱ ( всегда), есть несколько простых наблюдений о возможных значениях :[p1 p2 ... pk]pip0 = 1pk+1

• pk+1 ≥ pkтак как период строки Sтакже является периодом любого префикса S.

• pk+1 = pk всегда возможное расширение: просто повторите одну и ту же примитивную строку для вдвое большего количества символов.

• 2k < pk+1 ≤ 2k+1всегда возможное расширение. Достаточно показать это, потому что апериодическая строка длины может быть расширена до апериодической строки длиныpk+1 = 2k+1LL+1 , добавляя любую букву, которая не является ее первой буквой.

  Возьмем строку Sxдлиной 2 ^k , период которой равен, и рассмотрим строку длиной 2 ^{k + 1} . Ясно , что есть в период 2 ^к +1. Предположим, его период меньше.pkSxySSxySq

  Тогда по лемме о периодичности также есть период , и, поскольку наибольший делитель меньше или равен своим аргументам и является наименьшим периодом, мы требуем, чтобы коэффициент составлял 2 ^k +1. Так как его частное не может быть 2, мы имеем .2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)gcd(2k+1, q)SxySqqq ≤ (2k+1)/3

  Теперь, поскольку это период, это должен быть период . Но период является . У нас есть два случая:q ≤ 2kSxySSxSxpk

  1. gcd(pk, q) = pkили эквивалентно делится точно на .pkq
  2. pk + q > 2k + gcd(pk, q) так что лемма периодичности не форсирует меньший период.

  Рассмотрим сначала второй случай. , противореча определению как период . Поэтому мы вынуждены сделать вывод, что это фактор .pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2qpkSxpkq

  Но поскольку qэто период Sxи является периодом , префикс длины - это просто копии префикса длины , поэтому мы видим, что это также период .pkSxqq/pkpkpkSxyS

  Следовательно, период SxySравен или 2 ^k +1. Но у нас есть два варианта ! Максимум один выбор даст период , поэтому по крайней мере один даст период 2 ^k +1. QED.pkyypk

• Лемма периодичности позволяет отбросить некоторые из оставшихся возможных расширений.

• Любое расширение, которое не прошло тест быстрого принятия или быстрого отклонения, нуждается в конструктивной проверке.

Построение цепочки битов с заданной последовательностью периодов является по существу проблемой удовлетворительности, но она имеет много структур. Существуют простые ограничения равенства, подразумеваемые каждым периодом префикса, поэтому я использую структуру данных объединенного набора для объединения битов в независимые кластеры. Этого было достаточно, чтобы решить n = 64, но для n = 128 нужно было идти дальше. Я использую две полезные аргументы:2k - pk

1. Если префикс длины Mравен, а префикс длины имеет период, тогда префикс длины должен заканчиваться на . Это наиболее эффективно именно в тех случаях, когда в противном случае было бы большинство независимых кластеров, что удобно.01M-1L > MLL1M
2. Если префикс длины Mравен, а префикс длины имеет период с и заканчивается, то фактически он должен заканчиваться на . Это наиболее эффективно в противоположной крайности, когда последовательность периодов начинается с множества единиц.0ML > ML - dd < M0d10d

Если мы не получим непосредственное противоречие, заставив кластер с первым битом (предположительно равным нулю) равным единице, то мы перебираем силу (с некоторыми микрооптимизациями) над возможными значениями для не принудительных кластеров. Обратите внимание, что в порядке убывания числа единиц, потому что, если i^th-й бит равен единице, период не может быть, iи мы хотим избежать периодов, которые короче тех, которые уже применяются кластеризацией. Понижение повышает шансы найти действительное назначение на ранней стадии.

Ржавчина, 32, 10 с 11 с 29 на моем ноутбуке

Вызовите его с битовым размером в качестве аргумента командной строки.

Умные методы: представлять битовые строки непосредственно в виде чисел, использовать битовую переписку для проверки циклов. Выполняйте поиск только в первой половине цепочек битов, начинающихся с 0, поскольку массив периодов цепочки битов и ее обратной последовательности (с заменой 0 на 1 с) идентичны. Если все возможности для окончательной позиции уже произошли, я не ищу ее.

Более умные вещи:

Чтобы дедуплицировать каждый блок (строки, в которых первая половина битов одинакова), я использую битовый вектор, который намного быстрее, чем хэш-набор, поскольку длины последнего цикла не требуют хеширования.

Кроме того, я пропускаю первые шаги проверки цикла, потому что я знаю, что последний цикл не может быть короче второго до последнего цикла.

После большого количества профилирования я могу теперь сказать, что почти все время используется продуктивно, поэтому, я думаю, потребуется усовершенствование алгоритма, чтобы улучшить его отсюда. Я также переключился на 32-разрядные целые числа, чтобы сэкономить немного больше времени.

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

Положить bit-vec = "0.4.4" в свой Cargo.toml

Если вы хотите запустить это, клонируйте это: github.com/isaacg1/cycle, Cargo build --releaseчтобы построить, а затем Cargo run --release 32запустить.

Ржавчина , 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
}

Попробуйте онлайн!

Компиляция: rustc -O <name>.rs

Строка реализована в виде вектора Bool.

• nextФункция перебирать комбинации;

• find_periodБерет кусочек Bool и возвращает период;

• compute_count_arrayДелает работу для каждой «власти два» подпоследовательности каждой комбинации BOOLS.

Теоретически, переполнение не ожидается, пока не 2^nпревысит максимальное значение u64, т.е.n > 64 . Этот предел может быть превышен дорогостоящим тестом s = [true, true, ..., true].

Плохая новость: она возвращает 317 для n = 16, но я не знаю почему. Я также не знаю, удастся ли это сделать за десять минут при n = 32, поскольку Vec<bool>он не оптимизирован для такого рода вычислений.

РЕДАКТИРОВАТЬ

1. Мне удалось снять ограничение 64 для n. Теперь он не будет аварийно nзавершать работу, пока не станет больше целого числа max usize.

2. Я нашел, почему предыдущий код вернул 317 для n=32. Я считал наборы периодов, а не массивы периодов. Было три массива с одинаковыми элементами:

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

Теперь это работает. Это все еще медленно, но это работает.

С - 16

Это терпит неудачу на значениях больше чем 16 унций переполнения.

Я понятия не имею, как быстро это работает, потому что на Chromebook работает на repl.it.

Просто реализует вопрос во время чтения, просматривает все битовые строки, вычисляет массивы периодов и проверяет, были ли они уже подсчитаны.

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

Просто скомпилируйте его с помощью gcc и т. Д.

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

Компилировать с ghc -O2. Попробуйте онлайн!

Работает менее чем за 0,1 секунды на моем 6-летнем ноутбуке n=16. n=32занимает 99 92 мин, так что я фактор 9 или 10 от. Я пытался кэшировать периоды в справочной таблице, поэтому мне не нужно пересчитывать их снова и снова, но это быстро исчерпывает память на моей машине 4 ГБ.

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 минуты

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