Sucesión de Mian-Chowla

Esta sucesión se define por recurrencia de dos formas equivalentes:

(a)  a(1) = 1,  a(n) es el menor número mayor que a(n-1) tal que todas las sumas a(i)+a(j) con i, j £ n son distintas.

(b) a(1) = 1,  a(n) es el menor número mayor que a(n-1) tal que todas las diferencias a(i)-a(j) con i,j£n i>j son distintas.

Aquí trabajaremos con la primera.

Pertenece al rango de problemas y conjuntos de Sidon, matemático que estudió las cuestiones sobre sumas o diferencias todas distintas, Puedes leer nuestra entrada

http://hojaynumeros.blogspot.com.es/2010/03/jugamos-con-sidon-y-golomb.html

Los primeros elementos son 1, 2 , 4, 8, 13, 21, 31, 45, 66,...
http://oeis.org/A005282

Comprobemos la definición con el 8: Los términos anteriores (1, 2, 4) producen las siguientes sumas 2, 3, 4, 5, 6, 8. Deberíamos ahora probar con el siguiente número, el 5, pero este produce la suma 1+5=6, que ya está en la lista, luego no es válido. Probamos el 6, y la suma 2+6=8 lo invalida. El 7 tampoco pertenece a la sucesión, ya que 1+7=8 pertenece a la lista de sumas. Probamos el 8, que produce las sumas 9, 10 y 12, no incluidas en la lista, luego el 8 es válido y se incorpora a la lista.

Generación con hoja de cálculo

Para generar esta sucesión necesitamos definir una matriz  en la que almacenar las distintas sumas que hay que considerar. Se puede aprovechar el hecho de que una vez calculadas las sumas para a(n-1), se pueden usar también para a(n), con lo que en cada iteración aparecerán n sumas nuevas. Esto nos puede llevar a usar una columna de hoja de cálculo como matriz que almacene las sumas previas a cada elemento. Así lo hemos implementado, como puedes ver en la imagen (más adelante explicaremos cómo conseguimos que aparezcan):

En la columna de la izquierda hemos ido acumulando sumas, y en la de la derecha, elementos de la sucesión. Así, la suma 2 pertenece al elemento 1. Al incorporar un nuevo elemento, en este caso el 2, se incorporan las sumas 3 y 4. Con el elemento 4, las sumas 5, 6 y 8, y por último, con el 8, las restantes 9, 10, 12 y 16.

¿Cómo conseguimos la aparición automática de elementos y sumas nuevas?

Hemos diseñado un botón que en cada pulsación incorpora un elemento nuevo en la columna (o matriz) de elementos y las correspondientes sumas en la columna de la izquierda.

La idea es esta:

Comenzamos con a(1)=1 s(1)=1

Para cada posible elemento nuevo, ensayamos en primer lugar el valor a(n-1)+1. Si ese valor produce sumas distintas a las ya existentes, lo aceptamos e incorporamos a la lista. En caso contrario, probamos con a(n-1)+2, a(n-1)+3,…hasta que lleguemos a un número que produzca un conjunto de sumas todas distintas.

Si deseas practicar con ese botón, puedes descargarte la hoja alojada en esta dirección

http://www.hojamat.es/sindecimales/aritmetica/teoria/apunarit.htm#mian

Si te gusta la programación, sigue esta rutina en VBA, contenida en la hoja enlazada:

Sub nuevo()
Dim sumas, elem, x, x1, i, j, x0, s
Dim vale, dasuma As Boolean

sumas = ActiveWorkbook.Sheets(3).Cells(7, 4).Value ‘Lee los primeros elementos
elem = ActiveWorkbook.Sheets(3).Cells(7, 7).Value
x1 = ActiveWorkbook.Sheets(3).Cells(8 + elem, 7).Value

vale = False
x = x1 + 1
While Not vale ‘Se recorre un bucle mientras no aparezcan sumas distintas
dasuma = False ’Esta variable controla si una suma se repite
i = 1
While i <= elem And Not dasuma ‘Bucle de búsqueda de sumas no repetidas
x0 = ActiveWorkbook.Sheets(3).Cells(8 + i, 7).Value
j = 1
While j <= sumas And Not dasuma
s = ActiveWorkbook.Sheets(3).Cells(8 + j, 4).Value
If x1 + x0 = s Then dasuma = True ‘Una suma se ha repetido, y se rechaza el nuevo elemento
j = j + 1
Wend
i = i + 1
Wend
If dasuma Then
x1 = x1 + 1
Else
vale = True
elem = elem + 1 ‘Se ha encontrado un elemento válido y se incorpora a la columna
ActiveWorkbook.Sheets(3).Cells(8 + elem, 7).Value = x1
For j = 1 To elem ‘Se incorporan las sumas nuevas
x0 = ActiveWorkbook.Sheets(3).Cells(8 + j, 7).Value
ActiveWorkbook.Sheets(3).Cells(8 + sumas + j, 4).Value = x1 + x0
Next j
End If
Wend
End Sub

Hemos aprovechado la estructura de la hoja de cálculo para no tener que definir matrices o vectores de datos.

Curiosidades sobre esta sucesión

En la hoja arriba enlazada hemos copiado los primeros términos de la sucesión en la hoja “Propiedades”. Como en OEIS sólo figuran 50 elementos y algunas curiosidades implican muchos términos, hemos adaptado el algoritmo anterior para convertirlo en una función MIAN(N), tal que dado el número de términos, devuelva una cadena de caracteres (string) con los primeros términos de la sucesión de Mian-Chowla. Después, con la técnica de “Texto en columna” se pueden organizar en fila o columna. Hay que advertir que según el número de términos, la función puede ser lenta. Al ser este algoritmo muy parecido, remitimos al código VBA de la hoja enlazada.

Con esta lista de la hoja “Propiedades” podemos comprobar algunas de las afirmaciones que se han hecho sobre esta sucesión. Por ejemplo:

El límite de la suma de los inversos de esta sucesión está entre 2.158435 y 2.158677

Creamos una columna paralela a la lista que contenga los inversos, y al lado otra que recoja la sumas parciales. Con los términos que hemos identificado, la lista termina así:

Como vemos, se queda a una milésima aproximada de lo conjeturado, pero con hoja de cálculo no se puede afinar más sin un enorme gasto de tiempo.

La suma de los cuadrados de los inversos converge a 1.33853369 

Con un par de columnas, una de cuadrados de inversos, y otra de sumas parciales, llegaremos a

Es más aproximado que el anterior, porque los sumando son más pequeños.

Los valores de la sucesión, a partir de n=4, están comprendidos entre n^2/2 y n^3/3

Aquí tienes el cálculo para los términos 401, 475 y 565:

Ajuste

Se han dado otros varios ajustes de esta sucesión, pero no ha sido posible comprobarlos con la hoja. Así que, como una práctica, ajustaremos mediante una función potencial:

No está mal, un R2=0,9975, que nos aproximaría a una potencial de exponente 2,5 aproximadamente, pero es un cálculo no muy exacto.