Cantidad de números repetidos en una secuencia especial

Question

Proponemos la secuencia de secuencias que se construye según estas reglas:

1. La primera secuencia se llena con 1.
2. La segunda secuencia copia la primera, pero pone 2 en cada posición que sea múltiplo de 2.
3. La tercera secuencia copia la segunda, pero pone 3 en cada posición que sea múltiplo de 3.

4. (...)

   1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 3 1 2 3 2 1 2 3 4 1 3 1 4 3 2 1 2 3 4 5 3 1 4 3 5

¿Esta secuencia tiene un nombre especial? ¿Existen fórmulas para estimar la cantidad de números M en i -ésima secuencia de longitud N ?

Por ejemplo:

func count(M int, i int, length int) int { //... }

count(1, 1, 10) == 10
count(1, 2, 10) == 5
count(1, 3, 10) == 3
count(5, 1, 10) == 0
count(5, 5, 10) == 2

Answer 1

No hay una fórmula sencilla para count(1, i, length) .

Reducción a tarea conocida

Observación 1

El proceso descrito es el conocido algoritmo Sieve de Eratósfenes para la búsqueda de números primos, en el que tenemos 1-s en los lugares que pertenecen a los números primos. Y tenemos estos hechos:

• Siempre hay 1 en la primera columna
• Los números de las columnas 2 M-1 de la fila (M-1) no son 1-s.
• El número de la columna M de la fila (M-1) es igual a 1 entonces y sólo entonces cuando M es un número primo.

Observación 2

La cantidad de 1-s dentro de las primeras M-ésimas celdas de la fila M-1 es igual a

U(M) = count(1, M-1, M) - count(1, M-2, M)

si count es una fórmula barata de calcular, entonces U también es barato.

Consecuencia

U(M) es igual a 2 si M es primo y a 1 si no lo es.

Así, y el original count por 1 no es más barato que U y eso no es especialmente barato. Es decir, U(M) muestra si M es primo o no. Esto no es barato.