[Carlos Ivorra]

En este artículo:

N.P. Herzberg, "On a problem of Hurwitz" Pacific J. Math. , 50 (1974) pp. 485–493.

Se da un Teorema que propone un algoritmo que permite calcular todas las soluciones fundamentales no triviales de la ecuación:

\( x_1^2+x_2^2+\ldots+x_n^2=zx_1x_2\ldots x_n \)

con \( n\leq M \) (\( M \) dado).

Un hecho básico que está presupuesto en la tabla que muestra el artículo es algo que nombra en el primer párrafo, pero, ojo, que hay una errata. Es justo al revés: dice que la ecuación no tiene solución para \( n>z \), pero debería decir para \( z>n \). Por eso en la tabla sólo se consideran los casos \( z<n \), ya que en el caso \( z = n \) hay trivialmente solución.

[Richard R Richard]

Hola, me resulta extraño el caso de $$n=12$$ que no tenga soluciones para ningún z.

Si llamaos $$K_n=\sum\limits_{i=1}^nx_i^2=z \prod\limits_{i=1}^n x_i$$ con $$z<n$$

cuando escribí la ecuación cuadrática para tratar de encontrar el x  faltante para n+1 me vi tentado a hacer  esto

$$x_{n+1}^2-x_{n+1}K_n+\dfrac{K_n}{z}=0$$  pero no tiene porque cumplirse que los $$x_i$$  que fueron resultado para $$n$$ sean los mismos que para $$n+1$$

La idea era encontrar una solución no trivial de esta manera

Igualmente vi que esto lleva a resolver un discriminante

$$d^2=K_n^2-4\dfrac{K_n}z$$ y por lo visto de los planteos de conjeturas sobre este tipo de formas, que aunque K no sea el que yo propuse, no se puede afirmar que nunca se hallara un d que sea cuadrado perfecto, por lo que de ese modo me resulta extraño que n=12 no tenga respuesta y n=11 si para 2,3,y7 , si bien para (n,z)=(6,1) yo busque y no encontré soluciones, para números "bajos" no veo como pueden estar seguros para números altos...

yo veo una cota de la siguiente manera

$$nx_{max}^2=zx_{max}^n$$ si aumenta $$x$$ el termino de la derecha crece mas rápido

si paso de términos  $$\dfrac{n}{z}=x_{max}^{n-2}$$ entonces buscar $$x$$ mas grandes que $$x_{max}=\sqrt[n-2]{\dfrac{n}{z}}$$ pero se contradice con los resultados ya que no todos los $$x_i$$ serán iguales a $$x_{max}$$

[Luis Fuentes]

HOla

Hola, me resulta extraño el caso de $$n=12$$ que no tenga soluciones para ningún z.

Ando un poco apurado para analizar punto por punto lo que dices. Pero en esencia, ¿crees que está mal el artículo que te he enlazado?.

Ya viste por ejemplo que para \( (n,z)=(6,1) \) no aparecen soluciones; entonces sinceramente, me parece muy aventurado tener una intuición que haga que resulte extraño o natural la existencia de soluciones en otros casos.

Lo que tocaría (y si tengo tiempo intento mirarlo) es remangarse y estudiar con calma cada uno de los resultados del artículo; ahí puedes ver si te van convenciendo uno por uno o no.

Como te dije al final propone un algoritmo que, una vez entendido, podrías programar tu mismo.

Saludos.

[Richard R Richard]

HOla

Hola, me resulta extraño el caso de $$n=12$$ que no tenga soluciones para ningún z.

Ando un poco apurado para analizar punto por punto lo que dices. Pero en esencia, ¿crees que está mal el artículo que te he enlazado?.

No, no es así como se debería interpretar mi comentario, puedes perfectamente cambiar la palabra extraño por curioso, o anti intuitivo.

Ya viste por ejemplo que para \( (n,z)=(6,1) \) no aparecen soluciones; entonces sinceramente, me parece muy aventurado tener una intuición que haga que resulte extraño o natural la existencia de soluciones en otros casos.

Lo que tocaría (y si tengo tiempo intento mirarlo) es remangarse y estudiar con calma cada uno de los resultados del artículo; ahí puedes ver si te van convenciendo uno por uno o no.

Como te dije al final propone un algoritmo que, una vez entendido, podrías programar tu mismo.

Saludos.

Si, si te fijas de algún modo dije que había visto que en algunos  no había resultados, lo que ando pensando porque unos si y otros no,, y estoy buscándome el tiempo para programar.[/quote]

[Carlos Ivorra]

En este artículo:

N.P. Herzberg, "On a problem of Hurwitz" Pacific J. Math. , 50 (1974) pp. 485–493.

Se da un Teorema que propone un algoritmo que permite calcular todas las soluciones fundamentales no triviales de la ecuación:

\( x_1^2+x_2^2+\ldots+x_n^2=zx_1x_2\ldots x_n \)

con \( n\leq M \) (\( M \) dado).

Me he estudiado el artículo. Es totalmente elemental en el sentido de que no usa ningún resultado matemático más allá de la aritmética y el álgebra elemental. Adjunto aquí una versión con ejemplos y más explicaciones, por si a alguien le interesa, y pongo también el algoritmo en Python para generar todas las soluciones para un parámetro \( a \) dado (en el artículo lo llama \( z \)) y todos los \( n\leq M \), para una cota \( M \) prefijada. Si se quieren las soluciones para todo \( a \) sólo hay que meter el algoritmo en un bucle en el que \( a \) varía de \( 1 \) a (la parte entera de) \( (M+3)/2 \).

Corregido:

Código: [Seleccionar]

def SF(a,x):
    """Calcula la longitud de una solución fundamental de soporte x.
        Devuelve 0 si no hay."""
    prod = a
    suma = 0
    k = len(x)
    for i in range(0, k):
        prod = prod * x[i]
        suma = suma + x[i]**2
    n = k + prod - suma
    if prod<2*x[0]**2 or n<k or n <3:
        n = 0
    return n


def Genera(M, a):
    def añade(s):                   #Si s es de la forma [[n, a], x] y n está en el
        n = s[0][0]                 #rango considerado, añade s a la lista de soluciones pendientes.
        if n >= 3 and n <= M:
            Pendientes.append(s)
           
    Sol = []                        #Define una lista vacía de soluciones.
    Pendientes = []                 #Define una lista vacía de soluciones pendientes.
    if a == 1:                      #Añade (3, 3, 3) a Pendientes.
        añade([[3, 1],[3,3,3]])
    x = []
    n = 0
    while n == 0:                   #Buscamos la menor solución de la forma (2, ... , 2) si la hay
        x.append(2)                 #y la añadimos a Pendientes
        n = SF(a, x)
        añade([[n, a],x])
   
    while len(Pendientes) > 0:
        Sol.append(Pendientes[0])   #Leemos la primera solución pendiente y la añade a la lista de soluciones.
        x = (Pendientes.pop(0))[1]  #La borramos de Pendientes y nos quedamos con su soporte (quintándole [n, a])
        y = x[:]                    #Copiamos x en y.
        y[0] = y[0] + 1             #Consideramos la solución que resulta
        n = SF(a, y)                #de añadir 1 a x[0].
        añade([[n, a],y])           #Si es válida, se añade a Pendientes.
       
        if x[0] == 2:               #Si x es constante igual a 2
            y = x[:]                #Copiamos x en y.
            y.append(2)             #Añadimos un 2
            n = SF(a, y)            #y si es válida se añade a Pendientes
            añade([[n, a],y])

        if len(x) > 1:                              #Si x tiene longitud > 1,
            j=1
            while j< len(x)-1 and x[j-1] == x[j]:   #Buscamos el mínimo j tal que x[j-1] > x[j]
                j=j+1
            if x[j-1] == x[j]+1:                    #Si x[j] se diferencia del anterior en una unidad
                y = x[:]                            #Copiamos x en y.
                y[j] = y[j] + 1                     #Consideramos la solución que resulta
                n = SF(a, y)                        #de añadir 1 a x[j]
                añade([[n, a],y])                   #Si es válida, la añadimos a Pendientes.
                   
    Sol.sort()                          #Ordenamos las soluciones.                   
    return Sol

Con él he calculado las soluciones para \( n\leq 1\,000\,000 \) (y todo \( a \)) en 22 minutos. Con la versión refinada del código me ha tardado menos de 5 minutos.

El artículo señala que sólo hay quince valores de \( n\leq 301\,020 \) para los que no existen soluciones no triviales (y hay una errata, porque dice quince, pero sólo enumera catorce, y falta el penúltimo). Yo lo he comprobado que no hay más para \( n\leq 10\,000\,000 \), con una modificación del algoritmo que no guarda las soluciones que encuentra, sino que meramente va tachando los valores de \( n \) para los que hay solución.

[Richard R Richard]

Muchísimas gracias Carlos por el aporte, me alegro que el hilo te despertara curiosidad.
Como no pude descifrar bien las instrucciones para construir  el algoritmo,  use un copie y pegue del lema 2 y de las instrucciones del algoritmo a la famosa IA, y me creo, un programa, que los resolvía casi instantáneamente,  pero vi un problema, para $$n=4$$ y $$z=1$$ no mostraba $$[2,2,2,2]$$,y el resto  hasta 45 bien,  cuando le pedí  que lo corrigiera aparecieron soluciones para $$n=12$$... En fin es difícil verificar a veces el propio código, menos si no tengo idea de lo que hace el algoritmo.
Espero que pueda seguir  tus líneas y encontrar mi fallo,pero más importante  la seguir la logica del algoritmo,  ,te comento que la solución  me sorprendió por lo rápida, quizá no explore n tan grandes.

[Carlos Ivorra]

Espero que pueda seguir  tus líneas y encontrar mi fallo,pero más importante  la seguir la logica del algoritmo, 

La idea del algoritmo es muy sencilla. Está explicada en el pdf, pero si no entiendes algo, pregunta.

,te comento que la solución  me sorprendió por lo rápida, quizá no explore n tan grandes.

A mí me calculta todas las soluciones hasta \( n\leq 100 \) en 0.004 segundos, para \( n\leq 1\,000 \) en 0.032 segundos, para \( n\leq 10\,000 \) en 0.59 segundos, para \( n\leq 100\,000 \) en 19 segundos.

[Richard R Richard]

Código: [Seleccionar]

def SF(a,x):
    """Calcula la longitud de una solución fundamental de soporte x.
        Devuelve 0 si no hay."""
    prod = a
    suma = 0
    k = len(x)
    for i in range(0, k):
        prod = prod * x[i]
        suma = suma + x[i]**2
    n = k + prod - suma
    if prod<2*x[0]**2 or n<k or n <3:
        n = 0
    return n


def Genera(M, a):
    def añade(s):                   #Si s es de la forma [[n, a], x] y n está en el
        n = s[0][0]                 #rango considerado, añade s a la lista de soluciones pendientes.
        if n >= 3 and n <= M:
            Pendientes.append(s)
           
    Sol = []                        #Define una lista vacía de soluciones.
    Pendientes = []                 #Define una lista vacía de soluciones pendientes.
    kM = 1
    while a * 2**kM - 3 * kM <= M:  #kM es el máximo que cumple esta desigualdad.
        kM = kM + 1
    kM = kM - 1
   
    for k in range(1, kM+1):    #Añadimos a Pendientes todas las soluciones
        if k == 3 and a == 1:   #de la forma (2, ..., 2) y (3, 3, 3) si procede.
            x = [3,3,3]
        else:
            x = [2]*k   
        n = SF(a, x)
        añade([[n, a],x])

    while len(Pendientes) > 0:
        Sol.append(Pendientes[0])   #Lee la primera solución pendiente x,
        x = (Pendientes.pop(0))[1]  #la añade a la lista de soluciones y la borra de Pendientes
        y = x[:]
        y[0] = y[0] + 1             #Consideramos la solución que resulta
        n = SF(a, y)                #de añadir 1 a x[0].
        añade([[n, a],y])           #Si es válida, se añade a Pendientes.
       
        if len(x)>1:                #Buscamos si existe un (mínimo) índice con x[j-1] > x[j]
            j=1
            while j< len(x)-1 and x[j-1] == x[j]:
                j=j+1
            if x[j-1] == x[j]+1:    #Si se diferencia del anterior en una unidad
                x[j] = x[j] + 1     #Consideramos la solución que resulta
                n = SF(a, x)        #de añadir 1 a x[j]
                añade([[n, a],x])   #Si es válida, se añade a Pendientes.
                   
    Sol.sort()                          #Ordenamos las soluciones.                   
    return Sol

Hola, lo ejecute tal cual, y no me devolvió nada,  veo que son solo dos funciones, no faltaría un codigo main o principal? Gracias

[Carlos Ivorra]

Hola, lo ejecute tal cual, no no me devolvió nada,  veo que son solo dos funciones, no faltaría un codigo main o principal? Gracias

Sí, claro, son dos funciones. La primera determina si una sucesión de números se puede prolongar con unos hasta una solución fundamental, y en tal caso da su longitud n.

La segunda función (que usa la primera) te calcula todas las soluciones con parámetro \( a \) con \( n\leq M \). Por ejemplo, si quieres todas las soluciones fundamentales de las ecuaciones  \( x_1^2+ \cdots + x_n^2 = x_1\cdots x_n \) con \( n\leq 100 \) tienes que calcular \( Genera(100, 1) \) e imprimir el resultado.

Y si quieres todas las soluciones para todos los valores de a, tienes que hacer un bucle que te calcule la función para \( a \) entre \( 1 \) y \( (M+3)/2 \).

Yo había puesto únicamente las funciones que hacen los cálculos, para que las uses como quieras. Por ejemplo, un ejecutable es

Código: [Seleccionar]

import time
inicio = time.time()
Sol = Genera(100,1)
print("--- %s segundos ---" % (time.time() - inicio))
for i in range(0, len(Sol)):
    print(Sol[i])

Si quieres calcular las soluciones para todo \( a \) necesitas la función:

Código: [Seleccionar]

def Soluciones(M):
    Sol = []
    for a in range(1,1+(M+3)//2):
        Sol.extend(Genera(M, a))
    Sol.sort()
    return Sol
Y, en el ejecutable, cambiar Genera(100, 1) por Soluciones(100).

[Richard R Richard]

Entendido , Perfecto!!!