Le periodd'une chaîne est le décalage non nul le plus court afin que la chaîne corresponde à elle-même, en ignorant toutes les parties qui dépassent. Ainsi, par exemple, abcabcaba des règles 3. Par convention, nous disons que s'il n'y a pas un tel décalage, une chaîne a une période égale à sa longueur. Donc la période de abcdeest 5et la période de aest 1.

En termes plus formels, la période d'une chaîne Sest le minimum i > 0pour que S[1,n-i] == S[i+1,n](indexation à partir de 1).

Pour une chaîne S donnée de puissance de deux longueurs, nous calculerons la période de tous ses préfixes de puissance de deux longueurs. Par exemple, réfléchissez S = abcabcab. Les périodes que nous calculerons sont:

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

Nous allons en fait simplement sortir le tableau des périodes, c'est-à-dire [1, 2, 3, 3].

Pour une puissance positive donnée de deux n, considérez toutes les chaînes binaires possibles S. Rappelons qu'une chaîne binaire est simplement une chaîne de 1s et 0s donc il y a exactement de 2^ntelles chaînes (c'est à dire 2à la puissance n). Pour chacun, nous pouvons calculer ce tableau de périodes.

Le défi consiste à écrire du code qui prend n(une puissance de deux) en entrée et calcule le nombre de tableaux distincts.

Les réponses pour n = 1, 2, 4, 8, 16, 32, 64, 128sont:

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

L'ensemble complet de tableaux de périodes distincts pour n = 4est:

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

But

Je vais exécuter votre code sur mon ordinateur exécutant Ubuntu pendant 10 minutes. Votre score est le plus élevé npour lequel votre code se termine pendant cette période. Dans le cas d'une égalité, la réponse qui complète le plus grand ngain conjoint le plus rapide. Dans le cas où il y a égalité en moins d'une seconde sur le chronométrage, la première réponse publiée l'emporte.

Langues et bibliothèques

Vous pouvez utiliser toutes les langues et bibliothèques disponibles que vous aimez. Veuillez inclure une explication complète sur la façon d'exécuter / compiler votre code sous Linux si possible. »

Votre code doit en fait calculer les réponses et non pas, par exemple, simplement afficher des valeurs précalculées.

Entrées principales

• 2 minutes et 21 secondes pour n = 128 en C # par Peter Taylor
• 9 secondes pour n = 32 en rouille par isaacg

C #, n = 128 dans environ 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;
            }
        }
    }
}

L'extension à n = 256 nécessiterait de passer à BigIntegerpour les masques, ce qui tue probablement trop les performances pour que n = 128 passe sans nouvelles idées, encore moins n = 256.

Sous Linux, compilez avec mono-cscet exécutez avec mono.

Explication de base

Je ne vais pas faire une dissection ligne par ligne, juste un aperçu des concepts.

En règle générale, je suis heureux de parcourir de l'ordre de 2 ⁵⁰ éléments dans un programme combinatoire à force brute. Pour arriver à n = 128, il est donc nécessaire d'utiliser une approche qui n'analyse pas chaque chaîne de bits. Donc, plutôt que de travailler en avant des chaînes de bits aux séquences de périodes, je travaille en arrière: étant donné une séquence de périodes, y a-t-il une chaîne de bits qui la réalise? Pour n = 2 ^x, il existe une borne supérieure facile de 2 ^{x (x + 1) / 2} séquences de périodes (vs 2 ^{2 x} chaînes de bits).

Certains des arguments utilisent le lemme de périodicité des chaînes :

Soit pet qsoit deux périodes d'une chaîne de longueur n. Si p + q ≤ n + gcd(p, q)alors gcd(p, q)est également une période de la chaîne.

Wlog Je suppose que toutes les chaînes de bits considérées commencent par 0.

Étant donné une séquence de périodes où est la période du préfixe de longueur 2 ⁱ ( toujours), il y a quelques observations faciles sur les valeurs possibles de :[p1 p2 ... pk]pip0 = 1pk+1

• pk+1 ≥ pkcar une période d'une chaîne Sest également une période de n'importe quel préfixe de S.

• pk+1 = pk est toujours une extension possible: il suffit de répéter la même chaîne primitive pour deux fois plus de caractères.

• 2k < pk+1 ≤ 2k+1est toujours une extension possible. Il suffit de le montrer car une chaîne apériodique de longueur peut être étendue à une chaîne apériodique de longueur en ajoutant n'importe quelle lettre qui n'est pas sa première lettre.pk+1 = 2k+1LL+1

  Prenez une chaîne Sxde longueur 2 ^k dont la période est et considérez la chaîne de longueur 2 ^{k + 1} . Il est clair a une période de 2 ^k 1. Supposons que sa période soit plus petite.pkSxySSxySq

  Alors donc selon la périodicité, le lemme est aussi une période de , et comme le plus grand diviseur est inférieur ou égal à ses arguments et est la plus petite période, nous devons être un facteur propre de 2 ^k +1. Puisque son quotient ne peut pas être 2, nous l'avons .2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)gcd(2k+1, q)SxySqqq ≤ (2k+1)/3

  Maintenant, puisque c'est une période, cela doit être une période de . Mais la période de l' est . Nous avons deux cas:q ≤ 2kSxySSxSxpk

  1. gcd(pk, q) = pk, ou se divise de manière équivalente exactement en .pkq
  2. pk + q > 2k + gcd(pk, q) de sorte que le lemme de périodicité ne force pas une période plus courte.

  Considérons d'abord le deuxième cas. , contredisant la définition de comme période de . Par conséquent, nous sommes obligés de conclure que c'est un facteur .pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2qpkSxpkq

  Mais comme qc'est une période de Sxet est la période de , le préfixe de longueur n'est que des copies du préfixe de longueur , donc nous voyons que c'est aussi une période de .pkSxqq/pkpkpkSxyS

  La période de SxySest donc soit ou 2 ^k +1. Mais nous avons deux options pour ! Au plus, un choix donnera la période , donc au moins un donnera la période 2 ^k +1. QED.pkyypk

• Le lemme de périodicité nous permet de rejeter certaines des extensions possibles restantes.

• Toute extension qui n'a pas réussi un test d'acceptation rapide ou de rejet rapide doit être testée de manière constructive.

La construction d'une chaîne de bits étant donné une séquence de périodes est essentiellement un problème de satisifiabilité, mais elle a beaucoup de structure. Il y a des contraintes d'égalité simples impliquées par chaque période de préfixe, donc j'utilise une structure de données d' ensemble d'unions pour combiner des bits en grappes indépendantes. C'était suffisant pour s'attaquer à n = 64, mais pour n = 128, il fallait aller plus loin. J'emploie deux arguments utiles:2k - pk

1. Si le préfixe de longueur Mest et que le préfixe de longueur a une période, le préfixe de longueur doit se terminer par . Ceci est plus puissant précisément dans les cas qui auraient autrement la plupart des clusters indépendants, ce qui est pratique.01M-1L > MLL1M
2. Si le préfixe de longueur Mest et que le préfixe de longueur a une période avec et se termine par, il doit en fait se terminer par . C'est le plus puissant à l'extrême opposé, lorsque la séquence de périodes commence par beaucoup.0ML > ML - dd < M0d10d

Si nous n'obtenons pas de contradiction immédiate en forçant le cluster avec le premier bit (supposé à zéro) à un, alors nous force brute (avec quelques micro-optimisations) sur les valeurs possibles pour les clusters non forcés. Notez que l'ordre est en nombre décroissant de car parce que si le i^e bit est un alors la période ne peut pas être iet nous voulons éviter les périodes qui sont plus courtes que celles qui sont déjà appliquées par le clustering. Descendre augmente les chances de trouver tôt une affectation valide.

Rust, 32, 10s 11s 29s sur mon ordinateur portable

Appelez-le avec la taille de bit comme argument de ligne de commande.

Techniques intelligentes: représentez les chaînes de bits directement sous forme de nombres, utilisez bittwiddling pour vérifier les cycles. Recherchez uniquement la première moitié des chaînes de bits, celles commençant par 0, car le tableau de périodes d'une chaîne de bits et son inverse (0 échangés contre 1) sont identiques. Si chaque possibilité pour la position finale s'est déjà produite, je ne la recherche pas.

Des trucs plus intelligents:

Pour dédupliquer chaque bloc (chaînes où la première moitié des bits est la même), j'utilise un bitvector, qui est beaucoup plus rapide qu'un hachage, car les longueurs de cycle finales n'ont pas besoin d'être hachées.

De plus, je saute les premières étapes de la vérification du cycle, car je sais que le dernier cycle ne peut pas être plus court que l'avant-dernier cycle.

Après beaucoup de profilage, je peux maintenant dire que presque tout le temps est utilisé de manière productive, donc des améliorations algorithmiques seront nécessaires pour s'améliorer à partir d'ici, je pense. Je suis également passé à des entiers 32 bits pour gagner un peu plus de temps.

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

Mettez bit-vec = "0.4.4"votre Cargo.toml

Si vous souhaitez exécuter ceci, clonez ceci: github.com/isaacg1/cycle puis Cargo build --releasepour construire, puis Cargo run --release 32pour exécuter.

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

Essayez-le en ligne!

Compilation: rustc -O <name>.rs

La chaîne est implémentée en tant que vecteur booléen.

• La nextfonction parcourt les combinaisons;

• Le find_periodprend une tranche Bool et renvoie la période;

• Le compute_count_arrayfait le travail pour chaque sous-séquence "puissance de deux" de chaque combinaison de booléens.

Théoriquement, aucun débordement n'est prévu jusqu'à ce qu'il 2^ndépasse la valeur maximale u64, c'est-à-dire n > 64. Cette limite pourrait être dépassée avec un test coûteux sur s = [vrai, vrai, ..., vrai].

La mauvaise nouvelle est: elle renvoie 317 pour n = 16, mais je ne sais pas pourquoi. Je ne sais pas non plus s'il le fera en dix minutes pour n = 32, car le Vec<bool>n'est pas optimisé pour ce type de calcul.

ÉDITER

1. J'ai réussi à supprimer la limite de 64 pour n. Maintenant, il ne se bloquera pas tant qu'il nn'est pas supérieur à l'entier max usize.

2. J'ai trouvé pourquoi le code précédent renvoyait 317 pour n=32. Je comptais des ensembles de périodes et non des tableaux de périodes. Il y avait trois tableaux avec les mêmes éléments:

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

Maintenant ça marche. C'est encore lent mais ça marche.

C - 16

Il échoue sur des valeurs supérieures à 16 cuz de débordement.

Je n'ai aucune idée de la vitesse à laquelle cela s'exécute cuz im sur un Chromebook l'exécutant sur repl.it.

Implémente simplement la question pendant sa lecture, passe en revue toutes les chaînes de bits, calcule les tableaux de périodes et vérifie s'ils ont déjà été comptés.

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

Compilez-le simplement avec 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

Compilez avec ghc -O2. Essayez-le en ligne!

Fonctionne en moins de 0,1 seconde sur mon matériel portable de 6 ans n=16. n=32prend 99 92min, donc je suis facteur 9 ou 10. J'ai essayé de mettre en cache les périodes dans une table de recherche, donc je n'ai pas à les recalculer encore et encore, mais cela manque rapidement de mémoire sur ma machine de 4 Go.

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 minutes

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