Números cubifinitos

El enunciado del problema Números cubifinitos de ¡Acepta el reto! es el siguiente

Se dice que un número es cubifinito cuando al elevar todos sus dígitos al cubo y sumarlos el resultado o bien es 1 o bien es un número cubifinito.

Por ejemplo, el número 1243 es cubifinito, pues al elevar todos sus dígitos al cubo obtenemos 100 que es cubifinito.

Por su parte, el 513 no es cubifinito, pues al elevar al cubo sus dígitos conseguimos el 153 que nunca podrá ser cubifinito, pues la suma de los cubos de sus dígitos vuelve a dar 153.

Definir las funciones

tales que

  • (esCubifinito n) se verifica si n es un número cubifinito. Por ejemplo,

  • (grafica n) dibuja la gráfica de la sucesión de los primeros n números cubifinitos. Por ejemplo, al evaluar (grafica 50) se dibuja
    Numeros_cubifinitos

Soluciones

Números de Catalan

Los números de Catalan forman la sucesión cuyo término general es
Numeros_de_Catalan_1

Los primeros números de Catalan son

Los números de Catalan satisfacen la siguiente relación de recurrencia:
Numeros_de_Catalan_2

Asintóticamente, los números de Catalan crecen como:
Numeros_de_Catalan_3
considerando que el cociente entre el n-ésimo número de Catalan y la expresión de la derecha tiende hacia 1 cuando n tiende a infinito.

Definir las funciones

tales que

  • catalan es la lista de términos de la sucesión de Catalan. Por ejemplo,

  • (grafica a b) dibuja los n-ésimos términos de la sucesión de Catalan, para n entre a y b, junto con los de la expresión de la derecha de
    Numeros_de_Catalan_3
    Por ejemplo, (grafica 5 10) dibuja
    Numeros_de_Catalan_4
    y (grafica 55 60) dibuja
    Numeros_de_Catalan_5

Soluciones

La codificación de Luka

En el problema Kemija se utiliza la codificación de Luka consistente en añadir detrás de cada vocal la letra ‘p’ seguida de la vocal. Por ejemplo, la palabra «elena» se codifica como «epelepenapa» y «luisa» por «lupuipisapa».

Definir las funciones

tales que
+ (codifica cs) es la codificación de Luka de la cadena cs. Por ejemplo,

  • (decodifica cs) es la decodificación de Luka de la cadena cs. Por ejemplo,

Soluciones

Números binarios invertidos

La representación binaria de 13 es 1101, que al invertirlo da 1011 cuya representación decimal es el número 11.

Definir la función

tal que (transformado x) es la representación decimal del número obtenido invirtiendo la representación binaria de x. Por ejemplo,

Nota: El ejercicio está basado en el problema Reversed Binary Numbers de Kattis.

Soluciones

Contando en la arena

El problema de ayer de ¡Acepta el reto! fue Contando en la arena cuyo enunciado es el siguiente:

Es ampliamente conocido que escribimos los números utilizando base 10, en la que expresamos las cantidades utilizando 10 dígitos distintos (0…9). El valor de cada uno de ellos depende de la posición que ocupe dentro del número, pues cada dígito se multiplica por una potencia de 10 distinta según cuál sea esa posición.

La descomposición, por ejemplo, del número 1.234 es: 1.234 = 1×10^3 + 2×10^2 + 3×10^1 + 4×10^0

Otra base muy conocida es la base 2 al ser la utilizada por los dispositivos electrónicos. En ella sólo hay dos dígitos distintos (0 y 1), que se ven multiplicados por potencias de 2.

Mucho antes de que llegaran la base 2, la base 10 e incluso los números romanos, los primeros seres humanos contaban haciendo surcos en la arena, muescas en un trozo de madera o colocando palos en línea. Estaban, sin saberlo, usando base 1. En ella sólo hay un símbolo y cada dígito es multiplicado por una potencia de 1. Dado que 1^n = 1 el resultado es que todos los dígitos tienen el mismo peso.

Definir la función

tal que al evaluar (transformaAbase1 f1 f2) lee el contenido del fichero f1 (que estará compuesto por distintos números mayores que 0, cada uno en una línea) y escribe en el fichero f2 una línea con la representación en base 1 de cada uno de los números de f1 excepto el 0 final. Por ejemplo, si el contenido de «Entrada.txt» es

al evaluar (transformaAbase1 «Entrada.txt» «Salida.txt») el contenido de «Salida.txt» debe de ser

Soluciones

Sucesiones alícuotas

La sucesión alícuota de un número x es la sucesión cuyo primer término es x y cada otro término es la suma de los divisores propios del término anterior. Por ejemplo, la sucesión alícuota de 10 es [10,8,7,1,0,0,0] ya que

Definir la función

tal que (sucAlicuota x) es la sucesión alícuota de x. Por ejemplo,

Soluciones

Precisión de aproximaciones de pi

La precisión de una aproximación x de pi es el número de dígitos comunes entre el inicio de x y de pi. Por ejemplo, puesto que 355/113 es 3.1415929203539825 y pi es 3.141592653589793, la precisión de 355/113 es 7.

Definir las siguientes funciones

tales que

  • (mayorPrefijoComun xs ys) es el mayor prefijo común de xs e ys. Por ejemplo,

  • (precisionPi x) es la precisión de la aproximación de pi x. Por ejemplo,

  • (precisionPiCR x) es la precisión de la aproximación de pi x, como números reales. Por ejemplo,

Nota: Para la definición precisionPiCR se usa la librería Data.Number.CReal que se instala con

Soluciones

Cálculo de pi mediante el método de Newton

El método de Newton para el cálculo de pi se basa en la relación
Calculo_de_pi_mediante_el_metodo_de_Newton_1
y en el desarrollo del arco seno
Calculo_de_pi_mediante_el_metodo_de_Newton_2
de donde se obtiene la fórmula
Calculo_de_pi_mediante_el_metodo_de_Newton_3

La primeras aproximaciones son

Definir las funciones

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Newton. Por ejemplo,

  • (grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..30]) dibuja
    Calculo_de_pi_mediante_el_metodo_de_Newton_4

Nota: Este ejercicio ha sido propuesto por Manuel Herrera.

Soluciones

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

La fórmula de Gregory-Leibniz para calcular pi es
Calculo_de_pi_mediante_los_metodos_de_Gregory-Leibniz_y_de_Beeler_1
y la de Beeler es
Calculo_de_pi_mediante_los_metodos_de_Gregory-Leibniz_y_de_Beeler_2

Definir las funciones

tales que

  • (aproximaPiGL n) es la aproximación de pi con los primeros n términos de la fórmula de Gregory-Leibniz. Por ejemplo,

  • (aproximaPiBeeler n) es la aproximación de pi con los primeros n términos de la fórmula de Beeler. Por ejemplo,

  • (graficas xs) dibuja la gráfica de las k-ésimas aproximaciones de pi, donde k toma los valores de la lista xs, con las fórmulas de Gregory-Leibniz y de Beeler. Por ejemplo, (graficas [1..25]) dibuja
    Calculo_de_pi_mediante_los_metodos_de_Gregory-Leibniz_y_de_Beeler_3
    donde la línea morada corresponde a la aproximación de Gregory-Leibniz y la verde a la de Beeler.

Nota: Este ejercicio ha sido propuesto por Enrique Naranjo.

Soluciones

Cálculo de pi mediante la variante de Euler de la serie armónica

En el artículo El desarrollo más bello de Pi como suma infinita, Miguel Ángel Morales comenta el desarrollo de pi publicado por Leonhard Euler en su libro «Introductio in Analysis Infinitorum» (1748).

El desarrollo es el siguiente
Calculo_de_pi_mediante_la_variante_de_Euler_de_la_serie_armonica_1
y se obtiene a partir de la serie armónica
Calculo_de_pi_mediante_la_variante_de_Euler_de_la_serie_armonica_2
modificando sólo el signo de algunos términos según el siguiente criterio:

  • Dejamos un + cuando el denominador de la fracción sea un 2 o un primo de la forma 4m-1.
  • Cambiamos a – si el denominador de la fracción es un primo de la forma 4m+1.
  • Si el número es compuesto ponemos el signo que quede al multiplicar los signos correspondientes a cada factor.

Por ejemplo,

  • la de denominador 3 = 4×1-1 lleva un +,
  • la de denominador 5 = 4×1+1 lleva un -,
  • la de denominador 13 = 4×3+1 lleva un -,
  • la de denominador 6 = 2×3 lleva un + (porque los dos llevan un +),
  • la de denominador 10 = 2×5 lleva un – (porque el 2 lleva un + y el 5 lleva un -) y
  • la de denominador 50 = 5x5x2 lleva un + (un – por el primer 5, otro – por el segundo 5 y un + por el 2).

Definir las funciones

tales que

  • (aproximacionPi n) es la aproximación de pi obtenida sumando los n primeros términos de la serie de Euler. Por ejemplo.

  • (grafica n) dibuja la gráfica de las aproximaciones de pi usando k sumando donde k toma los valores de la lista [100,110..n]. Por ejemplo, al evaluar (grafica 4000) se obtiene
    Calculo_de_pi_mediante_la_variante_de_Euler_de_la_serie_armonica_3.png

Nota: Este ejercicio ha sido propuesto por Paula Macías.

Soluciones

Regresión lineal

Dadas dos listas de valores

la ecuación de la recta de regresión de ys sobre xs es y = a+bx, donde

Definir la función

tal que (regresionLineal xs ys) es el par (a,b) de los coeficientes de la recta de regresión de ys sobre xs. Por ejemplo, para los valores

se tiene

Para comprobar la definición, se importa la librería Graphics.Gnuplot.Simple y se define el procedimiento

tal que (grafica xs ys) pinta los puntos correspondientes a las listas de valores xs e ys y su recta de regresión. Por ejemplo, con (grafica ejX ejY) se obtiene el siguiente dibujo
Regresion_lineal

Soluciones

Sucesión de trazas de dígitos de pi

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

Las matrices de orden 1×1, 2×2, …, 5×5 formadas por los primeros dígitos de pi son

y sus trazas (es decir, sumas de los elementos de la diagonal principal) son 3, 4, 13, 20 y 25, respectivamente.

Definir la función

tal que (trazas n) es la lista de las trazas de las matrices de orden 1×1, 2×2, 3×3, …, nxn formadas por los primeros dígitos de pi. Por ejemplo,

Soluciones

Distribución de dígitos de pi

Se pueden generar los dígitos de Pi, como se explica en el artículo Unbounded spigot algorithms for the digits of pi, con la función digitosPi definida por

Por ejemplo,

La distribución de los primeros 25 dígitos de pi es [0,2,3,5,3,3,3,1,2,3] ya que el 0 no aparece, el 1 ocurre 2 veces, el 3 ocurre 3 veces, el 4 ocurre 5 veces, …

Usando digitosPi, definir las siguientes funciones

tales que

  • (distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,

  • (frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,

Soluciones

Búsqueda en los dígitos de pi

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

Definir la función

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

Nota. Se puede comprobar la función mediante The pi-search page o Pi search engine.

Soluciones

Cálculo de pi usando la fórmula de Vieta

La fórmula de Vieta para el cálculo de pi es la siguiente
Calculo_de_pi_usando_la_formula_de_Vieta

Definir las funciones

tales que

  • (aproximacionPi n) es la aproximación de pi usando n factores de la fórmula de Vieta. Por ejemplo,

  • (errorPi x) es el menor número de factores de la fórmula de Vieta necesarios para obtener pi con un error menor que x. Por ejemplo,

Soluciones

Cálculo de pi usando el producto de Wallis

El producto de Wallis es una expresión, descubierta por John Wallis en 1655, para representar el valor de π y que establece que:

Definir las funciones

tales que

  • factoresWallis es la sucesión de los factores del productos de Wallis. Por ejemplo,

  • productosWallis es la sucesión de los productos de los primeros factores de Wallis. Por ejemplo,

  • (aproximacionPi n) es la aproximación de pi obtenida multiplicando los n primeros factores de Wallis. Por ejemplo,

  • (errorPi x) es el menor número de factores de Wallis necesarios para obtener pi con un error menor que x. Por ejemplo,

Soluciones

Caminos en un árbol binario con suma dada

Los árboles binarios se pueden representar con el de tipo de dato algebraico

Por ejemplo, los árboles

se representan por

Definir las funciones

tales que

  • (caminos a) es la lista de los caminos entre dos nodos cualesquiera del árbol a. Por ejemplo,

  • (caminosSuma a k) es la lista de los caminos entre dos nodos cualesquiera del árbol a cuya suma es k. Por ejemplo,

Soluciones

Referencia

Basado en Print all k-sum paths in a binary tree de GeeksforGeeks.

Máximo común divisor de x e y veces n

Definir las funciones

tales que

  • (repite x n) es el número obtenido repitiendo x veces el número n. Por ejemplo.

  • (mcdR n x y) es el máximo común divisor de los números obtenidos repitiendo x veces e y veces el número n. Por ejemplo.

Soluciones

Caminos desde la raíz en un árbol binario

Los árboles binarios se pueden representar con el de tipo de dato algebraico

Por ejemplo, los árboles

se representan por

Definir la función

tal que (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la raíz de a hasta cualquiera de sus nodos. Por ejemplo.

Soluciones

Prefijo con suma acotada

Definir la función

tal que (prefijoAcotado x ys) es el mayor prefijo de ys cuya suma es menor que x. Por ejemplo,

Soluciones

Aplicaciones de operaciones

Definir la función

tal que (aplicaciones os xs ys) es la lista obtenida aplicando las operaciones de os a los elementos de xs es ys. Por ejemplo,

Soluciones

Sucesión de Cantor de números innombrables

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior
como se indica a continuación:

Definir la sucesión

cuyos elementos son los términos de la sucesión de Cantor. Por ejemplo,

Soluciones

Referencia

Basado en Cantor’s unspeakable numbers de
CodeGolf.

Particiones de una lista

Definir la función

tal que (particiones xs) es la lista de las particiones de xs en segmentos de elementos consecutivos. Por ejemplo,

Comprobar con QuickCheck que la concatenación de cada uno de los elementos de (particiones xs) es igual a xs.

Nota: En la comprobación usar ejemplos pequeños como se indica a continuación

Soluciones

Eliminación de triplicados

Definir la función

tal que (sinTriplicados xs) es la lista obtenida dejando en xs sólo las dos primeras ocurrencias de cada uno de sus elementos. Por ejemplo,

Soluciones

Máximo producto de pares en la lista

Definir la función

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir
como producto de dos elementos distintos de xs o Nothing, en el caso de que
ningún elemento de xs se pueda escribir como producto de dos elementos
distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Soluciones

Suma minimal de productos de pares de elementos consecutivos

Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos:

  • 10, por ejemplo con [1,4,2,3] ya que 1×4+2×3 = 10
  • 11, por ejemplo con [1,3,2,4] ya que 1×3+2×4 = 11
  • 14, por ejemplo con [1,2,3,4] ya que 1×2+3×4 = 14

Por tanto, la mínima suma de los productos de elementos consecutivos en las permutaciones de [1,2,3,4] es 10 y una permutación con dicha suma es [1,4,2,3].

Definir las funciones

tales que

  • (minimaSumaProductos xs) es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,

  • (permutacionMinimal xs) es una permutación de xs cuya suma de productos de elementos consecutivos de xs es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,

Soluciones

Árboles continuos

Los árboles binarios se pueden representar con el de tipo de dato algebraico

Por ejemplo, los árboles

se representan por

Un árbol binario es continuo si el valor absoluto de la diferencia de los elementos adyacentes es 1. Por ejemplo, el árbol ej1 es continuo ya que el valor absoluto de sus pares de elementos adyacentes son

En cambio, el ej2 no lo es ya que |8-10| ≠ 1.

Definir la función

tal que (esContinuo x) se verifica si el árbol x es continuo. Por ejemplo,

Soluciones

Referencias

La sucesión «Mira y di»

La sucesión «Mira y di» (en inglés, Look-and-Say) es una sucesión de números naturales en donde cada término se obtiene agrupando las cifras iguales del anterior y recitándolas. Por ejemplo, si x(0) = 1 se lee como «un uno» y por tanto x(1) = 11. Análogamente,

Definir la función

tal que (sucMiraYDi n) es la sucesión «Mira y di» cuyo primer término es n. Por ejemplo,

Independientemente del término inicial x(0) elegido (con la única salvedad del 22), la sucesión diverge y la razón entre el número de cifras de x(n) y el de x(n-1) tiende a un valor fijo que es la constante de Conway λ ≈ 1.303577269. Por ejemplo, para x(0) = 1, las razones son

Definir la función

tal que (aproximacionConway n e) es el menor k tal que la diferencia entre la constante de Conway y la razón entre el número de cifras de x(k) x(k-1) es, en valor absoluto, menor que e. Por ejemplo,

Nota: Este ejercicio ha sido propuesto por Elías Guisado.

Soluciones

Cadena de primos

La lista de los primeros números primos es

Los primeros elementos de la cadena obtenida concatenado los números primos es

Definir la función

tal que (primoEnPosicion n) es el número primo que tiene algún dígito en la posición n de la cadena obtenida concatenado los números primos. Por ejemplo,

Soluciones

Notación polaca inversa

La notación polaca inversa (en inglés, Reverse Polish Notation, o RPN), es una forma alternativa de escribir expresiones matemáticas. Por ejemplo, la expresión "20 - (4 + 3) * 2" en RPN es "20 4 3 + 2 * -".

Para evaluar una expresión en RPN, usamos una lista auxiliar (inicialmente vacía) y recorremos la expresión de izquierda a derecha. Cada vez que encontramos un número, lo añadimos a la lista auxiliar. Cuando encontramos un operador, retiramos los dos números que hay al principio de la pila, utilizamos el operador con ellos y los quitamos de la lista y le añadimos el resultado. Cuando alcancemos el final de la expresión, debemos tener un solo número en la lista auxiliar si la expresión estaba bien formada, y éste representa el resultado de la expresión. Por ejemplo, la evaluación de RPN "20 4 3 + 2 * -" es la siguiente

Definir la función

tal que (valor cs) es el valor de la expresión RPN cs. Por ejemplo,

Soluciones