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:
>>> 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:
(n-x)x+(n-x)=a
Código:
>>> 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:
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
''' 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:
>>> 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:
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:
>>> 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.