Contando (la teoría de números y / o Factores)

Question

Estoy atascado con este conteo problema: tengo una expresión: $T = (N!) \times (N!) / D$ donde, $D \in [1 - N!]$, es decir, $D$ toma todos los valores de $1$ $N!$y estoy para contar el número de puntos donde se $T$, viene a ser un número entero (un número entero positivo).

Por ejemplo, para $N=3$: $$ D \in \{1, 2, 3, 4, 5, 6\} $$ y $T$, viene a ser un número entero para $D \in \{1, 2, 3, 4, 6\}$, es decir, de 5 valores.

Me gustaría desarrollar un algoritmo eficiente para contar, desde $N$ puede ser un número grande.

Creo que en el numerador tenemos los posibles factores roto como $N!$ 's y tenemos que empezar a hacer productos hasta $N!$ de ellos y el recuento de todos los diferentes. Que parece una forma de hacerlo. Por favor ayudarme a quitarle el envoltorio o proporcionar consejos y sugerencias en las direcciones correctas para hacerlo de la manera más eficiente posible como $N$ aquí pasa a ser un valor enorme.

Answer 1

Este es un problema difícil! Si es posible enumerar todos los números primos entre 1 y N :

Sea P la lista de todos los números primos entre 1 y N. Para cada p en P se puede mantener una tupla (p,q) donde p es la potencia total de p en N!*N!. Que es q = max v tal que N!*N!/p^v es un número entero. Ahora, una vez que tenga estos (p,q) tuplas, debería ser posible enumerar todos los valores de v = p1^r1 * p1^r1 *...*pk^rk tal que 0<=ri<=qi (suponga que |P|=k). Ahora, es posible buscar diferentes (r1,r2,..., rk) tal que v <= N!.

El rango de cada ri puede ser reducido aún más. 0 <=r_i<=max_i donde max_i = máxima j tales que pi^j <= N!.

Diferentes valores de v = p1^r1 * p1^r1 *...*pk^rk, proporcionar a los casos donde el resultado de la división de N!*N!/v es un número entero.

Answer 2

Esto está relacionado con el divisor de la función. Deje d(n) el número de (positivo) divisores del número entero n. Por ejemplo,

  n  = 1 2 3 4 5 6 7 8 9
d(n) = 1 2 2 3 2 4 2 4 3

Su pregunta casi equivalente a la determinación de d(N!*N!), con la salvedad de que usted considera solo los divisores de a N!.

Porque usted está considerando sólo los valores especiales de n de entrada, específicamente factoriales al cuadrado, que la respuesta puede simplificar. Por ejemplo, si usted considera como entrada sólo factoriales, entonces la respuesta es

  N   =  1  2  3  4  5  6  7  8  9
d(N!) =  1  2  4  8 16 30 60 96 160

Suponiendo que usted puede (eficiente) calcular números primos menos de N, entonces se puede calcular d(N!) como sigue. Deje p1,p2,...,pm ser los números primos menos de N. A continuación, defina Qk por

Qk = sum{i >= 1} floor(N/pk^i)

Entonces tenemos

d(N!) = Q1 * Q2 * ... * Qm

Algunos asymptotics son conocidos, la más simple de las cuales es d(N!) <= 2^N. Erdos, Graham, Ivic, y Pomerance tienen un papel en este derecho En el número de divisores de n!.

Dejando T(N) el número de enteros entre 1 y N! que dividen N! * N!, los primeros términos de esta serie son

  N  =  1  2  3  4  5  6  7
T(N) =  1  2  5 11 32 88 203

Claramente T(N) >= d(N!), por lo que el análisis anterior nos da una cota inferior. No veo cómo extender los resultados de N! a este caso de forma explícita, pero si pienso en algo útil, voy a actualizar esta respuesta. En la media hora, esto puede dar otras ideas de cómo abordar este problema.

Answer 3

1, cuente el número de veces que cada primer dividir N!2
2 ahora tienes la factorización de N!2, a contar de las combinaciones que representa el número de soluciones para un D en el intervalo [1,(N!)2]
3 Dividir este resultado por 2 y sumar 1 para obtener la solución final (gracias Kaganar).

r=1
for i in primes_less_than(N):
   r=r*(1+numberofdivisorsinfaculty(N,i)*2)
#r at this point is numer of solutions fro D element [1-N!*N!]
print(r/2+1) # Kangar explaind this extra trick

donde

numberofdivisorsinfaculty(N,i):
# this func returns highest power r 
# as i^r that is divisible by N!
# complexity is log(N)/log(i)
   r=0
   while(N>0):
      r+=N/i
      N=N/i
   return r

Todo lo que usted necesita para agregar es el primer generador de número.

EDITAR:
Tomó 0.35 s en python para N = 10^6 y solución modulo 10^8 (he comprobado función con ingenua de la búsqueda para " N de 3 a 12 años, y parece ok)
Así que aquí está lleno de origen
http://ideone.com/7v0RV