algorithm - teorema - Coeficiente binomial módulo 142857

propiedades de los numeros combinatorios demostraciones

Question

Cómo calcular el coeficiente binomial módulo 142857 para n grande y r . ¿Hay algo especial sobre el 142857? Si la pregunta es modulo p donde p es primo, entonces podemos usar el teorema de Lucas pero lo que debería hacerse para 142857.

Answer 1

El algoritmo es:

• factorizar la base en poderes principales; 142857 = 3 ^ 3 × 11 × 13 × 37
• calcular el módulo de resultado de cada potencia principal
• combine los resultados usando el Teorema del Remanente chino.

Para calcular (n above k) mod p^q :

Fuente: http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf , teorema 1

define (n!)_p como el producto de los números 1..n que no son divisibles por p

define n_j como n después de borrar j dígitos menos significativos en la base p

definir r como n - k

define e_j como el número de acarreos cuando se agrega k+r , sin contar los acarreos de j dígitos más bajos, computando en base p

define s como 1 si p=2 & q>=3 y -1 contrario

luego (n above k) mod p^q := p^e_0 * s^e_(q-1) * concatenate(j=d..0)( (n_j!)_p / ((k_j!)_p*(r_j!)_p) ) con cada término de la concatenación que computa un dígito base-p del resultado, el menor j calcula los dígitos menos significativos que no sean cero.

Answer 2

Lo especial de 142857 es que 7 * 142857 = 999999 = 10 ^ 6 - 1. Este es un factor que surge del Pequeño Teorema de Fermat con a = 10 yp = 7, produciendo la equivalencia modular 10 ^ 7 == 10 (mod 7 ) Eso significa que puede trabajar con el módulo 999999 en su mayor parte y reducir al módulo final al dividir por 7 al final. La ventaja de esto es que la división modular es muy eficiente en las bases de representación de la forma 10 ^ k para k = 1,2,3,6. Todo lo que haces en estos casos es agregar grupos de dígitos; esta es una generalización de sacar nueves .

Esta optimización solo tiene sentido si tienes multiplicación de hardware base-10. Lo que realmente quiere decir que funciona bien si tienes que hacer esto con papel y lápiz. Dado que este problema apareció recientemente en un concurso en línea, imagino que ese es exactamente el origen de la pregunta.

Answer 3

En realidad puedes calcular C(n,k) % m en el tiempo O(n) para m arbitraria.

El truco es calcular n! , k! y (nk)! como vectores de potencia principal, reste los dos más adelante del primero y multiplique el módulo m restante. Para C(10, 4) hacemos esto:

10! = 2^8 * 3^4 * 5^2 * 7^1
 4! = 2^3 * 3^1
 6! = 2^4 * 3^2 * 5^1

Por lo tanto

C(10,4) = 2^1 * 3^1 * 5^1 * 7^1

Podemos calcular esto fácilmente mod m ya que no hay divisiones. El truco es calcular la descomposición de n! y amigos en tiempo lineal. Si precalculamos los números primos hasta n , podemos hacerlo de la siguiente manera: Claramente, para cada número par en el producto 1*2*...*9*10 obtenemos un factor de 2 . Para cada cuarto número, obtenemos un segundo y así sucesivamente. De ahí la cantidad de 2 factores en n! es n/2 + n/4 + n/8 + ... (donde / está el piso). Hacemos lo mismo para los primos restantes, y como hay primos O(n/logn) menores que n , y hacemos O(logn) para cada uno, la descomposición es lineal.

En la práctica, lo codificaría más implícito de la siguiente manera:

func Binom(n, k, mod int) int {
    coef := 1
    sieve := make([]bool, n+1)
    for p := 2; p <= n; p++ {
        if !sieve[p] {
            // Sieve of Eratosthenes
            for i := p*p; i <= n; i += p {
                sieve[i] = true
            }
            // Calculate influence of p on coef
            for pow := p; pow <= n; pow *= p {
                cnt := n/pow - k/pow - (n-k)/pow
                for j := 0; j < cnt; j++ {
                    coef *= p
                    coef %= mod
                }
            }
        }
    }
    return coef
}

Esto incluye un tamiz de Eratóstenes, por lo que el tiempo de ejecución es nloglogn lugar de n si los primos se han calculado previamente o tamizado con un tamiz más rápido.