Die periodeiner Zeichenfolge ist die kürzeste Verschiebung ungleich Null, sodass die Zeichenfolge mit sich selbst übereinstimmt und alle überhängenden Teile ignoriert werden. So hat zum Beispiel abcabcabPunkt 3. Konventionell sagen wir, dass wenn es keine solche Verschiebung gibt, eine Zeichenfolge eine Periode hat, die ihrer Länge entspricht. Also die Periode von abcdeist 5und die Periode von aist 1.

In formaleren Begriffen ist die Periode eines Strings Sdas Minimum, i > 0so dass S[1,n-i] == S[i+1,n](Indizierung von 1).

Für eine gegebene Zeichenfolge S mit einer Potenz von zwei Längen berechnen wir die Periode aller ihrer Präfixe der Potenz mit zwei Längen. Betrachten Sie zum Beispiel S = abcabcab. Die Perioden, die wir berechnen werden, sind:

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

Wir werden in der Tat nur das Array von Perioden ausgeben, das heißt [1, 2, 3, 3].

nBerücksichtigen Sie für eine gegebene positive Zweierpotenz alle möglichen binären Zeichenfolgen S. Denken Sie daran, dass eine binäre Zeichenfolge einfach eine Zeichenfolge aus 1s und 0s ist, sodass es genau 2^nsolche Zeichenfolgen gibt (dh 2nach Potenz n). Für jeden können wir dieses Array von Perioden berechnen.

Die Herausforderung besteht darin, Code zu schreiben, der n(eine Zweierpotenz) als Eingabe verwendet und berechnet, wie viele unterschiedliche solche Arrays es gibt.

Die Antworten für n = 1, 2, 4, 8, 16, 32, 64, 128sind:

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

Der vollständige Satz unterschiedlicher Periodenarrays für n = 4ist:

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

Ergebnis

Ich werde Ihren Code 10 Minuten lang auf meinem Computer mit Ubuntu ausführen. Ihre Punktzahl ist die größte, nfür die Ihr Code in dieser Zeit endet. Im Falle eines Unentschieden ngewinnt die Antwort, die den gemeinsamen größten Schnellsten vervollständigt . Für den Fall, dass es innerhalb von 1 Sekunde zu einem Unentschieden kommt, gewinnt die erste Antwort.

Sprachen und Bibliotheken

Sie können jede verfügbare Sprache und Bibliothek verwenden, die Sie mögen. Bitte geben Sie eine vollständige Erklärung an, wie Sie Ihren Code unter Linux ausführen / kompilieren können, wenn dies überhaupt möglich ist. "

Ihr Code sollte tatsächlich die Antworten berechnen und nicht nur vorberechnete Werte ausgeben.

Führende Einträge

• 2 Minuten und 21 Sekunden für n = 128 in C # von Peter Taylor
• 9 Sekunden für n = 32 in Rust von isaacg

C #, n = 128 in ungefähr 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;
            }
        }
    }
}

Das Erweitern auf n = 256 würde das Wechseln zu BigIntegerfür die Masken erfordern , was die Leistung wahrscheinlich zu sehr beeinträchtigt, als dass n = 128 ohne neue Ideen durchgehen könnte, geschweige denn n = 256.

Kompilieren Sie unter Linux mit mono-cscund führen Sie mit aus mono.

Grundlegende Erklärung

Ich werde keine zeilenweise Dissektion durchführen, sondern nur einen Überblick über die Konzepte.

Als Faustregel gehe ich gerne in der Größenordnung von 2 ⁵⁰ Elementen in einem kombinatorischen Brute-Force-Programm durch. Um zu n = 128 zu gelangen, muss daher ein Ansatz verwendet werden, der nicht jede Bitfolge analysiert. Anstatt von Bitfolgen zu Periodensequenzen vorwärts zu arbeiten, arbeite ich rückwärts: Gibt es bei einer Periodensequenz eine Bitfolge, die dies realisiert? Für n = 2 ^x gibt es eine einfache Obergrenze von 2 ^{x (x + 1) / 2} Periodensequenzen (vs 2 ^{2 x} Bitstrings).

Einige der Argumente verwenden das String-Periodizitäts-Lemma :

Sei pund qsei zwei Perioden einer Länge n. Wenn p + q ≤ n + gcd(p, q)dann gcd(p, q)ist auch ein Punkt der Zeichenfolge.

Wlog Ich gehe davon aus, dass alle betrachteten Bitstrings mit beginnen 0.

Bei einer Periodenfolge, in der die Periode des Präfixes der Länge 2 ⁱ ( immer) angegeben ist, gibt es einige einfache Beobachtungen zu möglichen Werten von :[p1 p2 ... pk]pip0 = 1pk+1

• pk+1 ≥ pkda eine Periode eines Strings Sauch eine Periode eines beliebigen Präfixes von ist S.

• pk+1 = pk ist immer eine mögliche Erweiterung: Wiederholen Sie einfach dieselbe primitive Zeichenfolge für doppelt so viele Zeichen.

• 2k < pk+1 ≤ 2k+1ist immer eine mögliche Erweiterung. Es reicht aus, dies zu zeigen, da eine aperiodische Zeichenfolge mit einer Länge zu einer aperiodischen Zeichenfolge mit Länge erweitert werden kann, indem ein Buchstabe angehängt wird, der nicht der erste Buchstabe ist.pk+1 = 2k+1LL+1

  Nehmen Sie eine Zeichenfolge mit Sxeiner Länge von 2 ^k, deren Periode ist, und betrachten Sie die Zeichenfolge mit einer Länge von 2 ^{k + 1} . Offensichtlich hat eine Periode 2 ^k +1. Angenommen, seine Periode ist kleiner.pkSxySSxySq

  Dann ist also durch die Periodizität das Lemma auch eine Periode von , und da der größte Teiler kleiner oder gleich seinen Argumenten ist und die kleinste Periode ist, müssen wir ein geeigneter Faktor von 2 ^k + 1 sein. Da sein Quotient nicht 2 sein kann, haben wir .2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q)gcd(2k+1, q)SxySqqq ≤ (2k+1)/3

  Nun, da ist eine Periode davon muss eine Periode von sein . Aber die Zeit von ist . Wir haben zwei Fälle:q ≤ 2kSxySSxSxpk

  1. gcd(pk, q) = pkoder gleichwertig genau in .pkq
  2. pk + q > 2k + gcd(pk, q) damit das Periodizitäts-Lemma keine kleinere Periode erzwingt.

  Betrachten Sie zunächst den zweiten Fall. , im Widerspruch zur Definition von als der Zeitraum von . Deshalb sind wir zu dem Schluss gezwungen, dass dies ein Faktor ist .pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2qpkSxpkq

  Da es sich jedoch qum eine Periode von Sxund um die Periode von handelt , ist das Präfix der Länge nur eine Kopie des Präfixes der Länge , sodass wir sehen, dass dies auch eine Periode von ist .pkSxqq/pkpkpkSxyS

  Daher ist die Periode von SxySentweder oder 2 ^k + 1. Wir haben aber zwei Möglichkeiten für ! Höchstens eine Wahl von ergibt eine Periode , so dass mindestens eine Periode 2 ^k + 1 ergibt . QED.pkyypk

• Das Periodizitäts-Lemma erlaubt es uns, einige der verbleibenden möglichen Erweiterungen abzulehnen.

• Jede Erweiterung, die keinen Quick-Accept- oder Quick-Reject-Test bestanden hat, muss konstruktiv getestet werden.

Die Konstruktion eines Bitstrings bei gegebener Periodenfolge ist im Wesentlichen ein Problem der Erfüllbarkeit, hat jedoch eine große Struktur. Es gibt einfache Gleichheitsbeschränkungen, die von jeder Präfixperiode impliziert werden, daher verwende ich eine Union-Set- Datenstruktur, um Bits zu unabhängigen Clustern zu kombinieren. Dies war genug, um n = 64 anzugehen, aber für n = 128 war es notwendig, weiter zu gehen. Ich verwende zwei nützliche Argumentationslinien:2k - pk

1. Wenn das Präfix der Länge Mist und das Präfix der Länge einen Punkt hat, muss das Präfix der Länge mit enden . Dies ist gerade in den Fällen am wirkungsvollsten, in denen sonst die meisten unabhängigen Cluster vorhanden wären, was praktisch ist.01M-1L > MLL1M
2. Wenn das Präfix der Länge Mist und das Präfix der Länge einen Punkt mit hat und mit endet , muss es tatsächlich mit enden . Dies ist im entgegengesetzten Extrem am stärksten, wenn die Periodensequenz mit vielen beginnt.0ML > ML - dd < M0d10d

Wenn wir keinen unmittelbaren Widerspruch erhalten, indem wir den Cluster mit dem ersten Bit (angenommen Null) als Eins erzwingen, erzwingen wir (mit einigen Mikrooptimierungen) die möglichen Werte für die ungezwungenen Cluster. Beachten Sie, dass die Reihenfolge in absteigender Anzahl von Einsen ist, denn wenn das i^th- Bit ein Eins ist, kann die Periode nicht sein, iund wir möchten Perioden vermeiden, die kürzer sind als diejenigen, die bereits durch das Clustering erzwungen werden. Ein Abstieg erhöht die Wahrscheinlichkeit, frühzeitig einen gültigen Auftrag zu finden.

Rust, 32, 10s 11s 29s auf meinem Laptop

Nennen Sie es mit der Bitgröße als Befehlszeilenargument.

Clevere Techniken: Stellen Sie Bitstrings direkt als Zahlen dar und verwenden Sie Bittwiddling, um nach Zyklen zu suchen. Suchen Sie nur die erste Hälfte der Bitstrings, die mit 0 beginnen, da das Array der Perioden eines Bitstrings und seine Umkehrung (0s gegen 1s getauscht) identisch sind. Wenn bereits alle Möglichkeiten für die endgültige Position vorhanden sind, suche ich nicht danach.

Klügeres Zeug:

Um jeden Block zu deduplizieren (Strings, bei denen die erste Hälfte der Bits gleich ist), verwende ich einen Bitvektor, der viel schneller als ein Hashset ist, da die endgültigen Zykluslängen kein Hashing benötigen.

Außerdem überspringe ich die ersten Schritte der Zyklusprüfung, da ich weiß, dass der letzte Zyklus nicht kürzer sein kann als der vorletzte Zyklus.

Nach vielen Profilen kann ich jetzt feststellen, dass fast die gesamte Zeit produktiv genutzt wird, sodass von hier aus algorithmische Verbesserungen erforderlich sind, denke ich. Ich habe auch auf 32-Bit-Ganzzahlen umgestellt, um etwas mehr Zeit zu sparen.

//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"Geben Sie Ihre Cargo.toml ein

Wenn Sie dies ausführen möchten, klonen Sie Folgendes: github.com/isaacg1/cycle, dann Cargo build --releaseerstellen und dann Cargo run --release 32ausführen.

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

Probieren Sie es online aus!

Zusammenstellung: rustc -O <name>.rs

Die Zeichenfolge wird als Bool-Vektor implementiert.

• Die nextFunktion durchläuft die Kombinationen.

• Der find_periodnimmt ein Bool-Slice und gibt den Punkt zurück.

• Das compute_count_arrayerledigt den Job für jede "Potenz von zwei" -Subsequenz jeder Kombination von Bools.

Theoretisch wird kein Überlauf erwartet, bis 2^nder u64-Maximalwert überschritten wird, d n > 64. H. Diese Grenze könnte mit einem teuren Test für s = [wahr, wahr, ..., wahr] erreicht werden.

Schlechte Nachrichten sind: Es gibt 317 für n = 16 zurück, aber ich weiß nicht warum. Ich weiß auch nicht, ob es in zehn Minuten für n = 32 sein wird, da das Vec<bool>nicht für diese Art der Berechnung optimiert ist.

BEARBEITEN

1. Ich habe es geschafft, das Limit von 64 für zu entfernen n. Jetzt stürzt es erst ab, wenn ndie maximale Ganzzahl usize größer ist.

2. Ich habe herausgefunden, warum der vorherige Code 317 für zurückgegeben hat n=32. Ich zählte Sätze von Perioden und keine Anordnungen von Perioden. Es gab drei Arrays mit denselben Elementen:

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

Jetzt funktioniert es. Es ist immer noch langsam, aber es funktioniert.

C - 16

Bei Werten über 16 cuz Überlauf schlägt dies fehl.

Ich habe keine Ahnung, wie schnell dies läuft, weil ich auf einem Chromebook bin, das es auf repl.it ausführt.

Implementiert einfach die Frage beim Lesen, durchläuft alle Bitfolgen, berechnet die Periodenarrays und prüft, ob sie bereits gezählt wurden.

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

Kompilieren Sie es einfach mit gcc usw.

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

Kompilieren mit ghc -O2. Probieren Sie es online aus!

Läuft in weniger als 0,1 Sekunden auf meiner 6 Jahre alten Laptop-Hardware für n=16. n=32dauert 99 92min, also bin ich Faktor 9 oder 10 aus. Ich habe versucht, die Punkte in einer Nachschlagetabelle zwischenzuspeichern, damit ich sie nicht immer wieder neu berechnen muss, aber auf meinem 4-GB-Computer geht schnell der Speicher aus.

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 Minuten

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