Particion aritmetica en python

[dijsktra]

Vuelvo a recuperar la cuestión no resuelta desde Mayo del 2017

https://foro.elhacker.net/ejercicios/ejercicio_bucle_while_en_python-t469250.0.html

"Dados dos números enteros n (n≥0) y a (a>0) encontrar, si existe, el
menor entero x del intervalo [0, n] para el que se cumpla lo siguiente: la diferencia
entre las sumas de los valores enteros de los intervalos [n-x, n] y [0, x] coincide
con a."

Se mostraron dos soluciones:

La primera es incorrecta, ya que para n = 100000 y para a= 350 se daba x=449, cosa que no
es cierta, pues

Código [Seleccionar] Expandir

>>> n,a,x = 100000, 350, 449
>>> n,a,x
(100000, 350, 449)
>>> a == sum(range(x,n+1)) - sum(range(0,x+1))
False
>>> a ,  sum(range(x,n+1)) - sum(range(0,x+1))
(350, 4999848399)

En la segunda, se dice que el problema se puede resolver en O(1) sin más que resolver la ecuacion

Código [Seleccionar] Expandir

(n-x)x+(n-x)=a
diciendo que (n-x)x+(n-x)  es la diferencia buscada. Cosa que no es, ya que

Código [Seleccionar] Expandir

>>> n,x
(100000, 449)
>>> (n-x)*x+(n-x) ==  sum(range(x,n+1)) - sum(range(0,x+1))
False
>>> (n-x)*x+(n-x) , sum(range(x,n+1)) - sum(range(0,x+1))
(44797950, 4999848399)

Propongo mi solución. La ecuación que hay que resolver en valores enteros 0 <= x <=n es (al final del mensaje digo como la he obtenido):

Código [Seleccionar] Expandir

n(n+1) = 2(a+x^2)

En el cuerpo de los complejos, siempre tiene solución, pero en los enteros 0 <= x <= n puede que ésta no exista, por lo que emplearé el tipo None de Python para expresar esta circunstancia...


El algoritmo python que lo resuelve es el siguiente:

Código (python) [Seleccionar] Expandir

'''
   P :  N >= 0 and a > 0
   Q : x = min i : 0 <= i <= N and N(N+1)==2(a +i^2) : i
'''
def partition(N,a):
    m = 0
    while (m<=N) and (N*(N+1)!=2*(a+m*m)):
        m=m+1
    return (None if m>N else m)



Van algunos ejemplos

Código [Seleccionar] Expandir


>>> for n in range(5,10):    
       for a in range(6,10):
           print n,a , " => Sol : " , partition(n,a)


Lo que arroja esta salida

Código [Seleccionar] Expandir


5 6  => Sol :  3
5 7  => Sol :  None
5 8  => Sol :  None
...
9 7  => Sol :  None
9 8  => Sol :  None
9 9  => Sol :  6



Vemos que

Código [Seleccionar] Expandir



>>> n,a,x = 5,6,3
>>> n,a,x
(5, 6, 3)
>>> a == sum(range(x,n+1)) - sum(range(0,x+1))
True
>>> a , sum(range(x,n+1)) - sum(range(0,x+1))
(6, 6)

El caso n=100000 y a = 350, no tiene solución.

Si puedo, mañana escribo de donde sale la ecuación.