Se llaman números de
Ulam a los que forman una sucesión construida de la siguiente forma:
Se declara u(1)=1 y u(2)=2 (veremos que esto se puede
alterar) y después definiremos u(n+1) como el primer número que se pueda
expresar como suma de dos números de
Ulam anteriores distintos, de forma única.
Los creó el matemático polaco Stanislaw Ulam y los publicó
en SIAM Review en 1964.
Puedes ampliar este concepto en las páginas
El 1 y el 2 se toman de forma arbitraria. El siguiente
deberá ser el 3, ya que 3=1+2 de forma única. También está claro que el cuarto
debe ser 4=1+3, pues 4=2+2 no sería válido por ser iguales los sumandos.
Deberíamos rechazar el 5, pues 5=1+4=2+3. El 6 sí nos vale,
pues 6=2+4, siendo no válida la suma 6=3+3.
Por tanto, los primeros términos de la sucesión de Ulam
serán 1, 2, 3, 4, 6. Es sencillo buscar los siguientes: 8, 11, 13, 16, 18, 26,…
Tienes más elementos en http://oeis.org/A002858,
junto con una gran cantidad de comentarios sobre estos números. Aquí nos
interesarán aspectos algorítmicos.
Veamos alguno:
Encontrar el número
de Ulam de orden N
Siguiendo la costumbre de este blog, resolveremos la
cuestión a través de una función que nos devuelva el término enésimo de la
sucesión. Esto tiene el inconveniente de que hay que ir tomando nota de los
términos anteriores. Los lenguajes avanzados lo resuelven mediante una lista, tal como veremos en PARI.
En
hoja de cálculo se pueden construir fácilmente listas mediante las columnas,
usando una variable que recuerde el número de términos de la lista y unos
procedimientos para escribir y leer en ella. No es complicado. Ya lo usamos en
otra sucesión, la de Mian-Chowla:
Aquí lo implementaremos de forma más simple, dimensionando
un vector con 2000 componentes. El inconveniente es que no podremos pasar de
esa cantidad, salvo que modifiquemos la dimensión, pero resulta más manejable.
Una vez determinemos la lista, en este caso u(2000),
rellenaremos en primer lugar los elementos u(1)=1 y u(2)=2. Después habrá que
ir probando los siguientes números hasta ver si proceden de una suma única de
elementos distintos o no. Crearemos una variable m que cuente las sumas posibles, y si vale 1, incorporamos un nuevo
elemento a la lista. Al llegar a n elementos,
paramos el cálculo y devolvemos ese resultado. El código de la función para
Excel y Calc es el siguiente, en el que hemos añadido los parámetros a y b por si deseamos iniciar la sucesión en otro par de números que no
sean 1, 2:
Public Function ulam(a, b, n)
Dim u(2000) ‘Usamos un vector o
matriz, pero puede ser una lista
Dim i, j, k, m, uu
Dim noes As Boolean
u(1) = a: u(2) = b ‘Se rellenan los
primeros términos
If n = 1 Or n = 2 Then ulam = u(n): Exit
Function ‘Primeros dos casos
For i = 3 To n
noes = True
uu = u(i - 1) + 1 ‘La variable uu recorre
los números de Ulam previos
While noes
m = 0
For j = 1 To i - 1
For k = j + 1 To i - 1
If j <> k And u(j) + u(k) = uu Then m
= m + 1 ‘Cuenta las sumas distintas
Next k
Next j ‘A continuación actúa cuando
la suma es única
If m = 1 Then u(i) = uu: noes = False Else
uu = uu + 1
Wend
Next i
ulam = uu
End Function
En la siguiente tabla, mediante esta función, hemos
representado los 20 primeros números de Ulam:
Recuerda que solo podremos actuar sobre los 2000
primeros, tal como hemos definido la función. Este inconveniente no existe si
usas lista en el lenguaje PARI. En el siguiente listado observarás que se
comienza creando la lista v: “my(v=List(),”
y, después, para incorporar un elemento a la lista se usa “lisput”. Lo que sigue es difícil de leer, pero se puede comprobar
que contiene las mismas ideas que en la función de Excel, con alguna ligera
variante. Esta es la función propuesta:
ulam(n)=my(v=List(),i,j,k,o,uu,m);listput(v,1);listput(v,2);for(i=3,n,o=1;uu=v[i-1]+1;while(o==1,m=0;for(j=1,i-1,for(k=j+1,i-1,if(v[j]+v[k]==uu&&j<>k,m+=1)));uu+=1;if(m==1,uu=uu-1;listput(v,uu);o=0)));uu
Por no complicar más (ya es bastante oscuro), no
hemos implementado la función para n=1 o n=2, por lo que el listado general
comenzará en el 3:
Así que con esta función podemos crear la lista de
los números de Ulam, pero nos puede interesar también si un número es de Ulam o
no. Por ejemplo, ¿Qué número de Ulam sigue al 200?
Para ello disponemos de otra función basada en la
anterior. Se podían refundir ambas en una sola, pero no compensaba el esfuerzo.
La orientación que se propone aquí es más lenta, pero más fácil de entender.
Ver si un
número es de Ulam
Llamaremos esulam a una función que nos
devuelva un 0 si el número propuesto no pertenece a la sucesión de Ulam y que
nos dé su número de orden en caso de que pertenezca.
Public Function esulam(a, b, n)
Dim i, uu, k
If n = a Then esulam = 1: Exit Function ‘Caso
u(1)
If n = b Then esulam = 2: Exit Function ’Caso u(2)
i = 3: k = 0: uu = 0
While uu <= n ‘Busca elementos
menores que n
uu = ulam(a, b, i)
If uu = n Then k = i ‘Si se llega a n, es que pertenece, y se
toma nota del orden k. Si no, k=0
i = i + 1
Wend
esulam = k
End Function
Con esta función averiguamos que el primer número de Ulam
posterior al 200 es el 206:
Los primeros números de Ulam que son números primos son:2,
3, 11, 13, 47, 53, 97, 131, 197, 241, 409, 431, 607, 673, 739, 751, 983, 991,
1103, 1433, 1489.
Como ejercicio, puedes comprobar los siguientes listados de
números de Ulam que cumplen otras condiciones:
Cuadrados: 1, 4, 16, 36, 324, 400, 441,…
Triangulares: 1, 3, 6, 28, 36, 253,…
Capicúas (contando los de una cifra): 1, 2, 3, 4, 6, 8, 11,
77, 99, 131, 282, 363, 414, 434, 585, 646,…
Otras sucesiones de
Ulam
Podemos cambiar los valores iniciales 1 y 2 por otros (por
eso se incluyeron los parámetros a y b en nuestras funciones). A continuación
se copian algunas, con indicación de su número en OEIS:
(a,b) Dirección Sucesión
(1, 2) A002858 1, 2, 3, 4, 6, 8, 11, 13, 16, 18,
...
(1, 3) A002859 1, 3, 4, 5, 6, 8, 10, 12, 17, 21,
...
(1, 4) A003666 1, 4, 5, 6, 7, 8, 10, 16, 18, 19,
...
(15) A003667 1, 5, 6, 7, 8, 9, 10, 12, 20, 22,
...
(2, 3) A001857 2, 3, 5, 7, 8, 9, 13, 14, 18, 19,
...
(2, 4) A048951 2, 4, 6, 8, 12, 16, 22, 26, 32,
36, ...
(2, 5) A007300 2, 5, 7, 9, 11, 12, 13, 15, 19,
23, ...
Con esto terminamos. No parece que este estudio dé
para más.
No hay comentarios:
Publicar un comentario