viernes, 13 de marzo de 2015

Autonúmeros (1)


Autonúmeros o números colombianos

Estos números, llamados también de Devlali, fueron descritos por el matemático indio Kaprekar (el de la constante 6174, http://es.wikipedia.org/wiki/Constante_de_Kaprekar). Son muy conocidos por haberlos presentado Martin Gadner en uno de sus libros. En esta dirección puedes leer su artículo.

http://librosdemates.blogspot.com.es/2013/01/viajes-por-el-tiempo-y-otras.html

Su definición es algo extraña, porque son aquellos números enteros positivos que no pueden ser expresados como la suma de otro entero con la suma de sus cifras (Kaprekar llamó a esta operación digitadición). Por ejemplo, 20, no puede generarse con números más pequeños a los que les sumamos sus cifras. Con los de una cifra se ve que es imposible, y con los de dos: 11+1+1=13, 12+1+2=15, 13+1+3=17, 14+1+4=19, 15+1+5=21, y el resto tampoco daría como resultado 20.

Con esta definición se comprende que existan infinitos tipos de autonúmeros, dependiendo de la base elegida, y así se ha demostrado. Nosotros nos limitaremos a la base 10. En este caso los tienes en http://en.wikipedia.org/wiki/Self_number y son estos:

1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97, 108, 110, 121, 132, 143, 154, 165, 176, 187, 198, …

También los puedes estudiar en http://oeis.org/A003052

Estos números proceden de una criba. Puedes ir calculando todos los resultados posibles si se suma cada número con la suma de sus dígitos en la base dada. Resultarían estos:

2, 4, 6, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28,…, que están contenidos en http://oeis.org/A176995 y los que nos ocupan serían su complemento.

Algoritmo de fuerza bruta

Una cuestión interesante es cómo saber si un número es autonúmero o no. El primer acercamiento a este tema puede consistir en recorrer todos los números inferiores a N, añadirles la suma de sus cifras y comprobar si el resultado es N. Desembocamos entonces en la programación con hojas de cálculo. Necesitaríamos:


  •  La función SUMACIFRAS
  •  Un bucle que recorra los números k de 1 a N y pare si el resultado de k+sumacifras(k) es N.
  •  Si la prueba anterior es positiva, declaramos que el número N no es autonúmero, y si es negativa para todos los números inferiores a N, diremos que sí lo es.


La función SUMACIFRAS debemos tenerla publicada en algún documento. Por si no fuera así, la reproducimos en Basic de hoja de cálculo:

Public Function sumacifras(n)

'No analiza si el número es entero positivo

Dim h, i, s, m

h = n ‘De la variable h se irán extrayendo las cifras
s = 0 ‘Esta variable recogerá la suma de cifras
While h > 9 ‘Bucle para extraer las cifras una a una
i = Int(h / 10)
m = h - i * 10
h = i
s = s + m ‘La nueva cifra se suma a la variable
Wend
s = s + h ‘La cifra residual se suma a la variable
sumacifras = s
End Function

Una vez tenemos la función sumacifras podemos organizar el test en forma de función booleana:

Public Function esauto(n)
Dim es As Boolean
Dim k

es = True ‘Se declara de entrada que el número es “colombiano”
k = 0  ‘Comenzamos a recorrer los números menores que n
While k < n And es  ‘No paramos hasta llegar a n o hasta que es sea falso
If k + sumacifras(k) = n Then es = False ‘Si hay igualdad, paramos y declaramos “False”
k = k + 1
Wend
esauto = es ‘La función recoge el valor de es
End Function

Aplicamos esta función a los primeros números y obtendremos el valor VERDADERO en los
autonúmeros:



Por ejemplo, busquemos el primer autonúmero que sigue a 1000:


Resulta ser el 1006.

Test de Kaprekar

El anterior algoritmo recorre demasiados números y es ineficiente para enteros grandes. El mismo Kaprekar demostró un test en el que sólo hay que analizar enteros no superiores al número de dígitos. Lo copiamos de la página http://www.numbersaplenty.com/set/self_number/



Lo hemos implementado como función para Excel. No detallamos el código. Sólo lo copiamos con algún comentario:

Public Function esauto2(n)
Dim nc, a, r, h, k
Dim es As Boolean

'número de cifras
a = 1: nc = 0
While a <= n
a = a * 10: nc = nc + 1
Wend
'Se preparan las variables del test de Kaprekar
If nc = 0 Then esauto2 = False: Exit Function
r = 1 + ((n - 1) Mod 9)
If r / 2 = r \ 2 Then h = r / 2 Else h = (r + 9) / 2
'Bucle del test
es = True
k = 0
While k <= nc And es
If sumacifras(Abs(n - h - 9 * k)) = h + 9 * k Then es = False
k = k + 1
Wend
esauto2 = es
End Function

Hemos preparado un esquema en el que se puede elegir el inicio y compara las dos funciones, ESAUTO y ESAUTO2. Por si se hubiera deslizado algún error se han efectuado varias comprobaciones y coinciden ambas funciones, pero con gran lentitud en la primera.


En la siguiente entrada justificaremos este test ofreciendo simultáneamente otro similar.

Distribución de los autonúmeros

Es fácil ver que el incremento entre dos autonúmeros consecutivos es frecuentemente 11. Por ello esperamos tramos lineales en su distribución. Los veremos creando un gráfico con los primeros, pero si elegimos un gráfico con muchos puntos, se nos presenta una distribución prácticamente lineal, con pendiente 10,2, cercana al 11, que como hemos visto, aparece en muchos tramos.



Para ver mejor los tramos lineales elegimos un rango de números más pequeño:



Normalmente el salto de 11 se produce porque equivale a rebajar en una unidad las decenas cuando es posible. Así la suma total se rebaja en 11. Si el primero es autonúmero puede obligar a que el segundo también lo sea, pues si éste admitiera una suma, al rebajar esa unidad podría no ser autonúmero el primero. Esto vale sólo para la mayoría de los casos. No es una regla general. Ocurre algo parecido con 101, 1001, 10001, … Estos números nos aparecerán en la siguiente entrada.
Hay una forma sencilla de engendrar autonúmeros (no todos), y es comenzar por 9 y después usar la fórmula recurrente

Ck=8*10k-1+Ck-1+8

El siguiente número sería 8*10+9+8=97, el siguiente 800+97+8=905.

Con hoja de cálculo es fácil construir esta generación recurrente. Inténtalo si quieres. En la imagen hemos añadido a la derecha la función esauto.