jueves, 19 de marzo de 2015

Autonúmeros (2)


En la entrada anterior descubrimos que todos los números se pueden clasificar en generados por la digitadición de Kaprekar y autonúmeros, que no pueden ser generados. Nos dedicaremos en primer lugar a los generados, y con ellos descubriremos algo más sobre los autonúmeros.

Números generados

Señalamos que los números 2, 4, 6, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28,… (http://oeis.org/A176995) son los complementarios de los autonúmeros. Todos ellos se pueden expresar como N+SUMACIFRAS(N), por lo que Kaprekar les llamó “generados”. A este número N le podemos llamar generador del mismo, pero desafortunadamente no es único, por lo que no podemos considerarlo una función dependiente del número. En efecto, existen números, como el 103, que poseen más de un desarrollo de este tipo, ya que 103=92+9+2 y también 103=101+1+1.

Podíamos definir una función GENERADOR si para cada N eligiéramos el mayor K que cumple que K+SUMACIFRAS(K)=N, y asignar el valor 0 como generador de los autonúmeros. Así sí sería una función. La función AUTO descrita más arriba y debidamente adaptada nos servirá para este propósito:

Public Function generador(n)
Dim k, g

g = 0
While k < n
If k + sumacifras(k) = n Then g = k
k = k + 1
Wend
generador = g
End Function

En esta tabla puedes comprobar que si a cada número de la derecha le sumas la suma de sus cifras, resulta el de la izquierda, salvo el caso del autonúmero 97 al que le hemos asignado un cero.



Si construimos un diagrama de dispersión entre N y su generador, obtenemos un resultado similar a este:



Abajo los puntos de valor 0 representan a los autonúmeros, y los de arriba parecen presentar pautas lineales escalonadas, pero es una ilusión, ya que esos tramos no se podrían solapar. Lo que ocurre es que en este proceso los números consecutivos aparecen muy cercanos, y dan la impresión de sucederse. Analizaremos estos números con más detalle.

Si representamos un número N de k+1 cifras en base 10, lo estamos generando mediante un polinomio del tipo


Si ahora le sumamos sus cifras (digitadición) se convertirá en


Todos los números generados se podrán expresar de esta forma, y los autogenerados, no.
Según esta fórmula, los dobles de las cifras 1…9 serán todos números generados, y si dos generadores se diferencian sólo en una unidad en las decenas, sus generados se diferenciarán en 11, como ya hemos observado. Si se diferencian en una unidad de las centenas, sus generados se diferenciarán en 101, y así. Estas correspondencias también se dan en casi todos los autonúmeros, pues van la par de estos. No se da en todos.

En este gráfico hemos descompuesto cada autonúmero en relación con los menores de 100, y vemos una repetición de tramos lineales a unas alturas de 1001, 2002, 3003 y 4004. Esto es consecuencia de la fórmula que hemos desarrollado.



Fundamento del algoritmo de Kaprekar


La fórmula

nos da una forma paralela a la de Kaprekar para decidir si N es autonúmero en pocos pasos (es el mismo proceso con otra orientación). Observa que todos los coeficientes son congruentes con 2 módulo 9, con lo que si llamamos G al posible generador de N y SC(G) a la suma de sus cifras, se cumplirá que Nº2SC(G) (mod 9. Para saber esto no hacía falta la fórmula, pues como G es congruente con SC(G) módulo 9 y se cumple que N=G+SC(G), es evidente que N será congruente con el doble de SC(G).

Como 2 es primo con 9, en la ecuación Nº2SC(G) (mod 9 se podrá encontrar una solución S, con lo que G=9*k+S para valores de k no superiores al número de cifras. Lo vemos con el 30: Si N=30, será 30º3º2*SC(G). En este caso SC(G)º6, porque 6+6º3 (mod 9. De esta forma G puede ser 6, 15 0 24. Recorremos de mayor a menor y descubrimos que el 24 vale, porque 24+2+4=30, luego 30 no es autonúmero, sino generado.

Probamos con un número mayor, como 4327, del que ya sabemos por otros medios que es autonúmero:

Hallamos el resto módulo 9 de 4327 (puedes dividir mentalmente o usar la función RESIDUO de Excel) y resulta ser 7. Planteamos 7º2SC(G) (mod 9. También, mentalmente, vemos que SC(G) º8 (mod 9. Por tanto, vamos restando de 4327 números del tipo 9*k+8 hasta ver si la suma de las cifras de la diferencia es ese número:

K=0: 4327-8=4321, y su suma de cifras no es 8.
K=1: 4327-17=4310 y no suman 17
K=2: 4327-26=4301. No suman 26,
K=3: 4327-35=4292. No vale
Acabamos con k=4, porque la suma de cifras ya no puede ser mayor:
K=4: 4327-44=4283, de suma 17, luego tampoco es válido.

Hemos comprobado, con la misma técnica de Kaprekar y distinta presentación, que 4327 es autonúmero. No puede ser generado.

Para los aficionados a la programación, esta es la función que podemos usar:

Public Function esauto3(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
'módulo 9
r = n Mod 9
For k = 0 To 8: If (r - 2 * k) Mod 9 = 0 Then h = k
k = 0: es = True
While k <= nc And es
If sumacifras(n - 9 * k - h) = 9*k+h Then es = False
k = k + 1
Wend
esauto3 = es
End Function

Hemos construido un esquema de hoja de cálculo en el que vemos la equivalencia de las tres funciones que hemos programado en estas entradas. En la imagen tienes un ejemplo:



Sucesiones recurrentes de números generados

Kaprekar estudió también las sucesiones que se forman si a un número cualquiera le vamos aplicando la digitadición tanto a él como a los resultados sucesivos. Por ejemplo, si comenzamos con el 12 tendríamos la sucesión 12, 15, 21, 24, 30,…Evidentemente es infinita, creciente y todos sus elementos, salvo quizás el primero, son generados. Kaprekar destacó que si restamos el último del primero y sumamos las cifras del último, resulta la suma de cifras de todos ellos. Por ejemplo, aquí, 30-12+3=21=1+2+1+5+2+1+2+4+3+0

Aunque el autor le dio mucha importancia, basta recorrer la generación para darse cuenta de su validez: 12+3+6+3+6=30, luego al restar resultarán las sumas de cifras menos la del último. Es una obviedad.