Quantum Insights

Vamos a jugar un poco con Austra, para ver hasta dónde nos deja llegar. Comencemos por definir un número, que supondremos que tiene cuatro dígitos, y vamos a crear un vector de enteros con esos cuatro dígitos:

let x=4123, v = [int:x/1000%10, x/100%10, x/10%10, x%10] in
    v;

Ahora vamos a ordenar esos dígitos, primero de mayor a menor, y luego, en sentido contrario:

let x=4123, v = [int:x/1000%10, x/100%10, x/10%10, x%10];
v.sortDesc; v.sort;

Mi intención, no obstante, es recomponer las dos listas de dígitos y restar el número mayor del menor:

let x=4123, v = [int:x/1000%10, x/100%10, x/10%10, x%10] in
    polyeval(10, v.sortDesc) - polyeval(10, v.sort);

Cuando el número inicial es 4123, la respuesta es 3087. Para hacer las cosas fáciles, vamos a definir ahora una función que reciba un entero y lo transforme de acuerdo con este procedimiento:

let kt(x: int): int = 
  let v = [int:x/1000%10, x/100%10, x/10%10, x%10] in
    (polyeval(10, v.sortDesc) - polyeval(10, v.sort)).toInt in
      kt(4123);

He llamado kt a la función: Kaprekar‘s transform.
Ahora quiero aplicar esta función sucesivamente al resultado de la propia función. La forma más sencilla de hacerlo en Austra es usar el método de clase unfold de las secuencias de enteros:

let ks(n: int) =
  let kt(x: int): int = 
    let v = [int:x/1000%10, x/100%10, x/10%10, x%10] in
      (polyeval(10, v.sortDesc) - polyeval(10, v.sort)).toInt in
        iseq::unfold(100, n, n => kt(n)) in
          ks(4123)

Para evitar sustos, he limitado el número de elementos en la secuencia generada a 100. En realidad, nos sobran elementos, porque si ejecutamos lo anterior obtendremos:

4,123  3,087  8,352  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174
6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174
6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174
6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174
6,174  6,174  6,174  6,174  6,174  6,174  6,174  6,174  

Como se ve, a la tercera aplicación de la función de transformación, la secuencia produce el número 6174, que tiene la curiosa propiedad kt(6174)=6174. A este número, comprensiblemente, se le conoce como constante de Kaprekar. Este es un ejemplo de punto fijo de una función, que en este caso es la transformación de Kaprekar.
Para embellecer un poco el resultado, vamos a intentar parar la secuencia cuando se empiecen a repetir valores. A la secuencia que generamos antes, vamos a aplicarle la propiedad fixedPoint:

let ks(n: int) =
  let kt(x: int): int = 
    let v = [int:x/1000%10, x/100%10, x/10%10, x%10] in
      (polyeval(10, v.sortDesc) - polyeval(10, v.sort)).toInt in
        iseq::unfold(100, n, n => kt(n)).fixedPoint in
          ks(4123)

Con este pequeño cambio, la secuencia ahora es más clara:

4,123  3,087  8,352  6,174

Si, en vez de utilizar 4123 como semilla, usamos 7773, digamos, obtenemos una secuencia parecida, que también converge en 6174:

7,773  3,996  6,264  4,176  6,174

Esta vez hemos necesitado cuatro pasos para tropezar con la constante de Kaprekar. ¿Cuál es el número máximo de pasos para que una secuencia creada a partir de un número arbitrario de cuatro dígitos converja en la constante de Kaprekar? Para calcularlo, sólo necesitamos añadir un paso más: una comprensión de listas.

let ks(n: int) =
  let kt(x: int): int = 
    let v = [int:x/1000%10, x/100%10, x/10%10, x%10] in
      (polyeval(10, v.sortDesc) - polyeval(10, v.sort)).toInt in
        iseq::unfold(100, n, n => kt(n)).fixedPoint in
          [x <- 1000..9999 => ks(x).length].max

La respuesta es ocho. La cota inicial máxima de 100 pasos es más que suficiente, pero como las secuencias de Austra se calculan por demanda, no hace daño al tiempo de ejecución del algoritmo.
¿Para qué sirve todo esto? El punto fijo es un concepto muy importante en matemáticas. No voy a enumerar aquí las aplicaciones del concepto. Pero podemos quedar en que la constante de Kaprekar nos ha servido de excusa para probar si el lenguaje funcional de Austra es suficientemente potente. Para el ejemplo, he decidido crear una expresión enorme y relativamente complicada, pero también podríamos haberlo conseguido definiendo las funciones kt y ks por separado. Cuestión de gustos…