periodZ ciągiem jest najkrótsza niezerowe przesunięcie tak, że ciąg pasuje do siebie, ignorując wszelkie części nawisu. Na przykład abcabcabma kropkę 3. Zgodnie z konwencją mówimy, że jeśli nie ma takiego przesunięcia, łańcuch ma okres równy jego długości. Więc okres abcdejest 5i okres ajest 1.

Mówiąc bardziej formalnie, okres ciągu znaków Sjest minimalny, i > 0więc S[1,n-i] == S[i+1,n](indeksowanie od 1).

Dla danego ciągu S potęgi dwóch długości obliczymy okres wszystkich jego prefiksów potęgi dwóch długości. Rozważmy na przykład S = abcabcab. Okresy, które obliczymy, to:

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

To znaczy po prostu wyprowadzimy tablicę okresów [1, 2, 3, 3].

Dla danej dodatniej mocy dwóch nrozważ wszystkie możliwe ciągi binarne S. Przypomnij sobie, że ciąg binarny jest po prostu ciągiem 1s i 0s, więc istnieją dokładnie 2^ntakie ciągi (czyli 2do potęgi n). Dla każdego z nich możemy obliczyć tę tablicę okresów.

Wyzwanie polega na napisaniu kodu, który pobiera n(potęga dwóch) danych wejściowych i oblicza, ile jest różnych takich tablic.

Odpowiedzi na n = 1, 2, 4, 8, 16, 32, 64, 128to:

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

Pełny zestaw różnych tablic okresowych dla n = 4:

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

Wynik

Uruchomię Twój kod na moim komputerze z systemem Ubuntu przez 10 minut. Twój wynik jest największy, ndla którego Twój kod kończy się w tym czasie. W przypadku remisu nwygrywa odpowiedź, która zakończy wspólne największe najszybsze. W przypadku remisu w czasie 1 sekundy wygrywa pierwsza opublikowana odpowiedź.

Języki i biblioteki

Możesz użyć dowolnego dostępnego języka i bibliotek, które ci się podobają. Proszę podać pełne wyjaśnienie, w jaki sposób uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe

Twój kod powinien w rzeczywistości obliczać odpowiedzi, a nie na przykład generować wstępnie obliczonych wartości.

Wiodące wpisy

• 2 minuty i 21 sekund dla n = 128 w języku C # autorstwa Petera Taylora
• 9 sekund dla n = 32 w Rust przez isaacg

C #, n = 128 w około 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;
            }
        }
    }
}

Rozszerzenie do n = 256 wymagałoby przełączenia BigIntegerna maski, co prawdopodobnie zabija wydajność zbyt mocno, aby n = 128 mógł przejść bez nowych pomysłów, nie mówiąc już o n = 256.

Pod Linuksem kompiluj mono-csci wykonuj za pomocą mono.

Podstawowe wyjaśnienie

Nie zamierzam dokonywać szczegółowej analizy, tylko przegląd pojęć.

Zasadniczo chętnie powtarzam w kolejności 2 ⁵⁰ elementów w programie kombinatorycznym typu brute-force. Aby dostać się do n = 128, konieczne jest zatem zastosowanie podejścia, które nie analizuje każdego ciągu bitów. Więc zamiast pracować naprzód od ciągów bitów do sekwencji kropek, pracuję wstecz: czy biorąc pod uwagę sekwencję kropek, czy istnieje ciąg bitów, który to realizuje? Dla n = 2 ^x jest łatwa górna granica 2 ^{x (x + 1) / 2} sekwencji okresowych (w porównaniu do 2 ^{2 x} ciągów bitów).

Niektóre argumenty używają lematu okresowości łańcucha :

Niech pi qdwa okresy ciąg długości n. Jeśli p + q ≤ n + gcd(p, q)wtedy gcd(p, q)jest także kropka ciągu.

Wlog Zakładam, że wszystkie rozważane ciągi bitów zaczynają się od 0.

Biorąc pod uwagę sekwencję okresów, w której występuje okres prefiksu o długości 2 ⁱ ( zawsze), istnieją pewne łatwe obserwacje dotyczące możliwych wartości :[p1 p2 ... pk]pip0 = 1pk+1

• pk+1 ≥ pkponieważ okres ciągu znaków Sjest również okresem dowolnego prefiksu S.

• pk+1 = pk jest zawsze możliwym rozszerzeniem: wystarczy powtórzyć ten sam prymitywny ciąg dla dwóch razy większej liczby znaków.

• 2k < pk+1 ≤ 2k+1jest zawsze możliwym rozszerzeniem. Wystarczy to wykazać, ponieważ aperiodyczny ciąg długości można przedłużyć do aperiodycznego ciągu długości , dodając dowolną literę, która nie jest jego pierwszą literą.pk+1 = 2k+1LL+1

  Weź łańcuch Sxo długości 2 ^k, którego okres jest, i rozważ łańcuch o długości 2 ^{k + 1} . Wyraźnie ma na okres 2 ^k +1. Załóżmy, że jego okres jest krótszy.pkSxySSxySq

  Zatem przez okresowość lemat jest także okresem , a ponieważ największy dzielnik jest mniejszy lub równy swoim argumentom i jest najmniejszym okresem, musimy mieć odpowiedni współczynnik 2 ^k +1. Ponieważ jego iloraz nie może wynosić 2, mamy .2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)gcd(2k+1, q)SxySqqq ≤ (2k+1)/3

  Teraz, ponieważ jest to okres, który musi być okresem . Ale okres jest . Mamy dwa przypadki:q ≤ 2kSxySSxSxpk

  1. gcd(pk, q) = pklub równo dzieli się na .pkq
  2. pk + q > 2k + gcd(pk, q) aby lemat okresowości nie wymuszał krótszego okresu.

  Rozważ najpierw drugi przypadek. , co jest sprzeczne z definicją okresu . Dlatego jesteśmy zmuszeni dojść do wniosku, że jest to czynnik .pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2qpkSxpkq

  Ale ponieważ qjest to okres Sxi jest to okres , prefiks długości jest tylko kopią prefiksu długości , więc widzimy, że jest to również okres .pkSxqq/pkpkpkSxyS

  Dlatego okres SxySwynosi albo 2 ^k +1. Ale mamy dwie opcje ! Co najwyżej jeden wybór da okres , więc co najmniej jeden da okres 2 ^k +1. CO BYŁO DO OKAZANIA.pkyypk

• Lemat okresowości pozwala nam odrzucić niektóre z pozostałych możliwych rozszerzeń.

• Każde rozszerzenie, które nie przeszło testu szybkiego akceptowania lub szybkiego odrzucania, musi zostać przetestowane konstruktywnie.

Konstrukcja łańcucha bitów w sekwencji okresu jest zasadniczo problemem satysfakcji, ale ma wiele struktur. Istnieją proste ograniczenia równości implikowane przez każdy okres prefiksu, więc używam struktury danych zbioru unii do łączenia bitów w niezależne klastry. To wystarczyło, aby pokonać n = 64, ale dla n = 128 konieczne było pójście dalej. Używam dwóch użytecznych argumentów:2k - pk

1. Jeśli prefiksem długości Mjest i prefiks długości ma kropkę, to prefiks długości musi kończyć się na . Jest to najsilniejsze właśnie w przypadkach, które w innym przypadku miałyby najbardziej niezależne klastry, co jest wygodne.01M-1L > MLL1M
2. Jeśli prefiks długości Mjest, a prefiks długości ma kropkę z i kończy się w, to tak naprawdę musi on kończyć się na . Jest to najsilniejsze w przeciwnej skrajności, gdy sekwencja okresu zaczyna się od wielu.0ML > ML - dd < M0d10d

Jeśli nie otrzymamy natychmiastowej sprzeczności, zmuszając klaster z pierwszym bitem (zakładanym jako zero) do jednego, wówczas brutalnie działamy (z pewnymi mikrooptymalizacjami) nad możliwymi wartościami dla niewymuszonych klastrów. Zauważ, że kolejność jest w malejącej liczby tych, bo jeśli i^ty bit jest jeden, to okres ten nie może być ii chcemy uniknąć okresów, które są krótsze niż te, które są już egzekwowane przez klastry. Zejście w dół zwiększa szanse na wcześniejsze znalezienie ważnego zadania.

Rust, 32, 10s 11s 29s na moim laptopie

Wywołaj to z bitowym rozmiarem jako argumentem wiersza poleceń.

Sprytne techniki: reprezentuj ciągi bitów bezpośrednio jako liczby, użyj bittwiddling, aby sprawdzić cykle. Przeszukuj tylko pierwszą połowę ciągów bitów, zaczynających się od 0, ponieważ tablica okresów ciągu bitów i jego odwrotności (0 zamienionych na 1s) są identyczne. Jeśli pojawiła się już każda możliwość uzyskania ostatecznej pozycji, nie szukam jej.

Bardziej sprytne rzeczy:

Aby deduplikować każdy blok (ciągi, w których pierwsza połowa bitów jest taka sama), używam bitvectora, który jest znacznie szybszy niż hashset, ponieważ końcowe długości cyklu nie wymagają haszowania.

Pomijam też pierwsze kroki sprawdzania cyklu, ponieważ wiem, że ostatni cykl nie może być krótszy niż cykl od drugiego do ostatniego.

Po wielu profilach mogę teraz stwierdzić, że prawie cały czas jest produktywnie wykorzystywany, więc myślę, że w tym przypadku konieczne będą ulepszenia algorytmów. Zmieniłem również na 32-bitowe liczby całkowite, aby zaoszczędzić trochę czasu.

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

Umieść bit-vec = "0.4.4"swój Cargo.toml

Jeśli chcesz to uruchomić, sklonuj to: github.com/isaacg1/cycle, a następnie Cargo build --releaseskompiluj, a następnie Cargo run --release 32uruchom.

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

Wypróbuj online!

Kompilacja: rustc -O <name>.rs

Ciąg jest implementowany jako wektor Bool.

• nextFunkcja iterację kombinacji;

• find_periodBierze kawałek Bool i zwraca okresu;

• compute_count_arrayNie praca dla każdego „mocą dwóch” podciąg każdej kombinacji Bools.

Teoretycznie nie oczekuje się przepełnienia, dopóki nie 2^nprzekroczy maksymalnej wartości u64, tj n > 64. Limit ten można przekroczyć kosztownym testem na s = [prawda, prawda, ... prawda].

Zła wiadomość: zwraca 317 dla n = 16, ale nie wiem dlaczego. Nie wiem też, czy to zajmie dziesięć minut dla n = 32, ponieważ Vec<bool>nie jest zoptymalizowane dla tego rodzaju obliczeń.

EDYTOWAĆ

1. Udało mi się usunąć limit 64 dla n. Teraz nie nzawiedzie się, dopóki nie będzie większa niż maksymalna liczba całkowita usize.

2. Dowiedziałem się, dlaczego poprzedni kod zwrócił 317 n=32. Liczyłem zestawy okresów, a nie tablice okresów. Były trzy tablice z tymi samymi elementami:

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

Teraz działa. Nadal jest wolny, ale działa.

C - 16

Nie działa przy wartościach większych niż 16 cuz przepełnienia.

Nie mam pojęcia, jak szybko to działa, bo jestem na Chromebooku, który działa na repl.it.

Po prostu implementuje pytanie w trakcie czytania, przechodzi przez wszystkie ciągi bitów, oblicza tablice kropek i sprawdza, czy zostały już policzone.

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

Po prostu skompiluj go za pomocą gcc itp.

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

Kompiluj z ghc -O2. Wypróbuj online!

Działa w czasie krótszym niż 0,1 sekundy na moim 6-letnim laptopie dla n=16. n=32zajmuje 99 92min, więc mam 9 lub 10 zniżki. Próbowałem buforować kropki w tabeli odnośników, więc nie muszę ich ponownie obliczać w kółko, ale na moim komputerze o pojemności 4 GB szybko kończy się pamięć.

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 minuty

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