La tarea es calcular OEIS A005434 lo más rápido posible.

Considere una cadena binaria Sde longitud n. Indexando desde 1, podemos determinar si S[1..i+1]coincide S[n-i..n]exactamente para todos ien orden de 0a n-1. Por ejemplo,

S = 01010

da

[Y, N, Y, N, Y].

Esto se debe a que 0coincide 0, 01no coincide 10, 010coincide 010, 0101no coincide 1010 y finalmente 01010coincide a sí mismo.

Definir f(n)a ser el número de matrices distintas de Ys y Ns se obtiene cuando se itera sobre todas las 2^ndiferentes cadenas de bits posibles Sde longitud n.

El observador notará que esta pregunta es una variante más simple de otra pregunta reciente mía . Sin embargo, espero que los trucos inteligentes puedan hacer esto mucho más rápido y fácil.

Tarea

Para aumentar a npartir de 1, su código debería salir n, f(n).

Ejemplo de respuestas

Para n = 1..24, las respuestas correctas son:

1, 2, 3, 4, 6, 8, 10, 13, 17, 21, 27, 30, 37, 47, 57, 62, 75, 87, 102, 116, 135, 155, 180, 194

Puntuación

Su código debe iterar desde n = 1dar la respuesta para cada uno npor turno. Tomaré el tiempo de toda la carrera, matándola después de dos minutos.

Tu puntaje es el más alto nque alcanzas en ese momento.

En caso de empate, la primera respuesta gana.

¿Dónde se probará mi código?

Ejecutaré su código en Virtualbox en una máquina virtual invitada de Lubuntu (en mi host de Windows 7).

Mi computadora portátil tiene 8GB de RAM y una CPU Intel i7 [email protected] GHz (Broadwell) con 2 núcleos y 4 hilos. El conjunto de instrucciones incluye SSE4.2, AVX, AVX2, FMA3 y TSX.

Entradas principales por idioma

• n = 599 en Rust bu Anders Kaseorg.
• n = 30 en C por Grimy. La versión paralela llega a 32 cuando se ejecuta de forma nativa en cygwin.

Óxido , n ≈ 660

use std::collections::HashMap;
use std::iter::once;
use std::rc::Rc;

type Memo = HashMap<(u32, u32, Rc<Vec<u32>>), u64>;

fn f(memo: &mut Memo, mut n: u32, p: u32, mut s: Rc<Vec<u32>>) -> u64 {
    debug_assert!(p != 0);
    let d = n / p;
    debug_assert!(d >= 1);
    let r = n - p * if d >= 2 { d - 1 } else { 1 };

    let k = s.binary_search(&(n - r + 1)).unwrap_or_else(|i| i);
    for &i in &s[..k] {
        if i % p != 0 {
            return 0;
        }
    }

    if d >= 3 {
        let o = n - (p + r);
        n = p + r;
        s = Rc::new(s[k..].iter().map(|i| i - o).collect());
    } else if n == p {
        return 1;
    } else if k != 0 {
        s = Rc::new(s[k..].to_vec());
    }

    let query = (n, p, s);
    if let Some(&c) = memo.get(&query) {
        return c;
    }
    let (n, p, s) = query;

    let t = Rc::new(s.iter().map(|i| i - p).collect::<Vec<_>>());
    let c = if d < 2 {
        (1..r + 1).map(|q| f(memo, r, q, t.clone())).sum()
    } else if r == p {
        (1..p + 1)
            .filter(|&q| p % q != 0 || q == p)
            .map(|q| f(memo, r, q, t.clone()))
            .sum()
    } else {
        let t = match t.binary_search(&p) {
            Ok(_) => t,
            Err(k) => {
                Rc::new(t[..k]
                            .iter()
                            .cloned()
                            .chain(once(p))
                            .chain(t[k..].iter().cloned())
                            .collect::<Vec<_>>())
            }
        };
        (1..t.first().unwrap() + 1)
            .filter(|&q| p % q != 0 || q == p)
            .map(|q| f(memo, r, q, t.clone()))
            .sum()
    };
    memo.insert((n, p, s), c);
    c
}

fn main() {
    let mut memo = HashMap::new();
    let s = Rc::new(Vec::new());
    for n in 1.. {
        println!("{} {}",
                 n,
                 (1..n + 1)
                     .map(|p| f(&mut memo, n, p, s.clone()))
                     .sum::<u64>());
    }
}

Pruébalo en línea!

Cómo funciona

Esta es una implementación memorable del predicado recursivo Ξ dado en Leo Guibas, "Períodos en cadenas" (1981). La función f(memo, n, p, s)encuentra el número de correlaciones de longitud ncon el período más pequeño py también cada uno de los períodos del conjunto s.

Solo una simple búsqueda de fuerza bruta, para comenzar el desafío:

#include <stdio.h>
#include <stdint.h>
#include <string.h>

typedef uint16_t u16;
typedef uint64_t u64;

static u64 map[1<<16];

int main(void)
{
    for (u64 n = 1;; ++n) {
        u64 result = 1;
        u64 mask = (1ul << n) - 1;
        memset(map, 0, sizeof(map));

        #pragma omp parallel
        #pragma omp for
        for (u64 x = 1ul << (n - 1); x < 1ul << n; ++x) {

            u64 r = 0;
            for (u64 i = 1; i < n; ++i)
                r |= (u64) (x >> i == (x & (mask >> i))) << i;
            if (!r)
                continue;

            u16 h = (u16) (r ^ r >> 13 ^ r >> 27);
            while (map[h] && map[h] != r)
                ++h;

            if (!map[h]) {
                #pragma omp critical
                if (!map[h]) {
                    map[h] = r;
                    ++result;
                }
            }
        }

        printf("%ld\n", result);
    }
}

Compilar con clang -fopenmp -Weverything -O3 -march=native. En mi máquina alcanza n = 34 en 2 minutos.

EDITAR: roció algunas directivas OMP para facilitar el paralelismo.