Encontrar los máximos divisores de un número en el rango

Question

Mientras jugaba con la programación, se me ocurrió un problema.

Dado $n$ digamos que $2^{64}$ (entero sin signo de 64 bits). Encuentra un entero positivo $x$ , $1 \leq x \leq n$ , de tal manera que $x$ tiene máximos divisores.

Mi intento fue:
Dejemos que $n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}.$
El número de divisores viene dado por: $$(a_1 + 1) \times (a_2 + 1) \times ... \times (a_k + 1)$$

Tenemos que encontrar el máximo de estos productos. Dado que $(a_1 + 1)_{max} \implies {a_1}_{max}$ el producto se convierte en: $a_1 \times a_2 \times .... \times a_k$
Dejemos que $P = a_1 \times a_2 \times .... \times a_k$ .
El máximo de $P$ significa $a_i = a_j$ donde $1 \leq i, j \leq k$ .

Así que supongo que mi pregunta es cómo podemos encontrar un número que sea menor que $n$ que tiene esta propiedad?

Gracias,

Answer 1

Secuencia A002182 da los números altamente compuestos, donde el número de divisores establece un récord.

Usted quiere el mayor bajo $2^{64}$ . Por desgracia, la tabla no llega tan alto, pero las referencias sí. Siguiendo un poco el espíritu de la respuesta de Mark Eicenlaub, si se piensa en $$n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k} \text{ and } d(n)=(a_1 + 1) \times (a_2 + 1) \times ... \times (a_k + 1)$$ y pensar en añadir uno al exponente de $p_i$ , $\log (n)$ aumenta en $\log (p_i)$ y $\log (d(n))$ aumenta en $\log(a_i+2)-\log(a_i+1)$ .

Así que la cifra de mérito para un aumento es $$\frac{\log(a_i+2)-\log(a_i+1)}{\log (p_i)}$$ y puedes buscar entre los primos para encontrar cuál debes añadir. Esto hará que se pierdan algunos, en los que quitando uno y añadiendo otro se consigue un paso más.

Answer 2

No sé la respuesta exacta a la pregunta, pero aquí hay una forma de obtener una solución aproximada.

Estamos maximizando $a_1a_2a_3\ldots$ sujeta a una restricción $p_1^{a_1}p_2^{a_2}p_3^{a_3}\ldots \leq n$ . Tratemos el $a_i$ como variables continuas que podemos diferenciar. En ese caso, también podríamos establecer la restricción $=n$ en lugar de $\leq n$ .

Toma los logaritmos de ambos productos. Ahora estamos maximizando $\ln a_1 + \ln a_2 + \ln a_3 \ldots$ con sujeción a $a_1 \ln p_1 + a_2 \ln p_2 + a_3 \ln p_3 \ldots = \ln n$ .

Introduce un multiplicador de Langrange y establece los gradientes de las dos sumas para que sean proporcionales entre sí.

$$ \frac{1}{a_1} \hat{a_1} + \frac{1}{a_2} \hat{a_2} + \frac{1}{a_3} \hat{a_3 }+ \ldots = \lambda (\ln p_1 \hat{a_1} + \ln p_2 \hat{a_2} + \ln p_3 \hat{a_3} + \ldots) $$

Salpicando ambos lados con $\hat{a_i}$ da

$$\frac{1}{a_i} = \lambda \ln p_i$$

o

$$a_i = \frac{1}{\lambda \ln p_i}$$

$\lambda$ se elige entonces para satisfacer la restricción original.

Esto debería especificar el máximo $a_i$ tratamiento de $a_i$ como continuo. Para obtener el $a_i$ para que sean enteros, redondearías algunos hacia arriba y otros hacia abajo. Como estás escribiendo código, podrías simplemente buscar por fuerza bruta en este espacio mucho más pequeño de posibles soluciones enteras.

Answer 3

Esta respuesta puede ser útil si buscas un algoritmo real para resolver el problema (y no un enfoque teórico). Si $x$ es un número entero en el rango $[1,n]$ con el máximo número de divisores escribir $$ x = q_1^{a_1} q_2^{a_2} \dots q_k^{a_k} $$ con el $q_i$ primos distintos y $$ a_1 \ge a_2 \ge \cdots \ge a_k. \quad(*)$$

Entonces vemos que el número entero $$ x' = 2^{a_1} 3^{a_2} \dots p_k^{a_k} \quad (**)$$ tiene el mismo número de divisores y es $\le x$ . Así que podemos limitar nuestra búsqueda a los enteros de la forma $(**)$ que verifican $(*)$ . Esto hace que la búsqueda sea realmente fácil, y rápida en rangos pequeños: empezar con $(a_1,\dots,a_k) = (t,0,\dots,0)$ y $k$ tal que $2\cdot3\cdot\dots\cdot p_{k+1} > n$ y $2^t \le n < 2^{t+1}$ y pasar por todos los $k$ -tuplas que verifican $(*)$ y $(**)$ en orden lexicográfico decreciente, manteniendo su producto máximo y $<n$ .

Puede encontrar un programa en C++ que realiza esta tarea en este hilo en TopCoder, aunque hay que adaptarlo para llegar hasta $2^{64}$ ya que se limita a $n\le 2^{64}/47$ .

EDIT: He escrito una versión PARI-GP que puede llegar mucho más lejos, para $n=2^{64}$ el número entero probablemente no único con el máximo número de divisores es: $$ 18401055938125660800 = 2^7\cdot 3^4\cdot 5^2\cdot 7^2\cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 $$ con 184320 divisores.