Tren de potencias

Si n es el número natural cuya expansión decimal es abc… , el tren de potencias de n es a^bc^d… donde el último exponente es 1, si n tiene un número impar de dígitos. Por ejemplo

Definir las funciones

tales que

  • (trenDePotencias n) es el tren de potencia de n. Por ejemplo.

  • (esPuntoFijoTrenDePotencias n) se verifica si n es un punto fijo de trenDePotencias; es decir, (trenDePotencias n) es igual a n. Por ejemplo,

  • puntosFijosTrenDePotencias es la lista de los puntso fijos de trenDePotencias. Por ejemplo,

  • (tablaTrenDePotencias a b) es la tabla de los trenes de potencias de los números entre a y b. Por ejemplo,

Comprobar con QuickCheck que entre 2593 y 24547284284866559999999999 la función trenDePotencias no tiene puntos fijos.

Soluciones

Puedes escribir tus soluciones en los comentarios o ver las soluciones propuestas pulsando [expand title=»aquí»]

[/expand]

Valores de polinomios y de expresiones

Las expresiones aritméticas construidas con una variables, los números enteros y las operaciones de sumar y multiplicar se pueden representar mediante el tipo de datos Exp definido por

Por ejemplo, la expresión 3+5x^2 se puede representar por

Por su parte, los polinomios se pueden representar por la lista de sus
coeficientes. Por ejemplo, el polinomio 3+5x^2 se puede representar por [3,0,5].

Definir las funciones

tales que

  • (valorE e n) es el valor de la expresión e cuando se sustituye su variable por n. Por ejemplo,

  • (expresion p) es una expresión aritmética equivalente al polinomio p. Por ejemplo,

  • (valorP p n) es el valor del polinomio p cuando se sustituye su variable por n. Por ejemplo,

Comprobar con QuickCheck que, para todo polinomio p y todo entero n,

Soluciones

Las sucesiones de Loomis

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

  • f(0) es x
  • f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

  • Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, …
  • Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
  • Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
  • Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, …
  • Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, …

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

  • la generada por 2 converge a 2
  • la generada por 3 converge a 26
  • la generada por 4 converge a 4
  • la generada por 5 converge a 26

Definir las siguientes funciones

tales que

  • (sucLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

  • (convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

  • (graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja
    Las_sucesiones_de_Loomis_1
    y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja
    Las_sucesiones_de_Loomis_2

Soluciones

Decidir si existe un subconjunto con suma dada

Sea S un conjunto finito de números naturales y m un número natural. El problema consiste en determinar si existe un subconjunto de S cuya suma es m. Por ejemplo, si S = [3,34,4,12,5,2] y m = 9, existe un subconjunto de S, [4,5], cuya suma es 9. En cambio, no hay ningún subconjunto de S que sume 13.

Definir la función

tal que (existeSubSuma xs m) se verifica si existe algún subconjunto de xs que sume m. Por ejemplo,

Soluciones

La conjetura de Levy

Hyman Levy observó que

y conjeturó que todos los número impares mayores o iguales que 7 se pueden escribir como la suma de un primo y el doble de un primo. El objetivo de los siguientes ejercicios es comprobar la conjetura de Levy.

Definir las siguientes funciones

tales que

  • (descomposicionesLevy x) es la lista de pares de primos (p,q) tales que x = p + 2q. Por ejemplo,

  • (graficaLevy n) dibuja los puntos (x,y) tales que x pertenece a [7,9..7+2x(n-1)] e y es el número de descomposiciones de Levy de x. Por ejemplo, (graficaLevy 200) dibuja
    La_conjetura_de_Levy-200

Comprobar con QuickCheck la conjetura de Levy.

Soluciones

[schedule on=’2018-03-19′ at=»06:00″]

Recorrido de árboles en espiral

Los árboles se pueden representar mediante el siguiente tipo de datos

Por ejemplo, los árboles

se representan por

Definir la función

tal que (espiral x) es la lista de los nodos del árbol x recorridos en espiral; es decir, la raíz de x, los nodos del primer nivel de izquierda a derecha, los nodos del segundo nivel de derecha a izquierda y así sucesivamente. Por ejemplo,

Soluciones

Sucesión de Lichtenberg

La sucesión de Lichtenberg esta formada por la representación decimal de los números binarios de la sucesión de dígitos 0 y 1 alternados Los primeros términos de ambas sucesiones son

Definir las funciones

tales que

  • lichtenberg es la lista cuyos elementos son los términos de la sucesión de Lichtenberg. Por ejemplo,

  • (graficaLichtenberg n) dibuja la gráfica del número de dígitos de los n primeros términos de la sucesión de Lichtenberg. Por ejemlo, (graficaLichtenberg 100) dibuja
    Sucesion_de_Lichtenberg

Comprobar con QuickCheck que todos los términos de la sucesión de Lichtenberg, a partir del 4º, son números compuestos.

Soluciones

Números apocalípticos

Un número apocalíptico es aquel número natural n tal que 2^n contiene la secuencia 666.

Definir las funciones

tales que

  • (esApocaliptico n) se verifica si n es un número apocalíptico. Por ejemplo,

  • apocalipticos es la lista de los números apocalípticos. Por ejemplo,

  • (mayorNoApocalipticoMenor n) es justo el mayor número no apocalíptico menor que n. Por ejemplo,

  • (grafica n) dibuja las gráficas de los n primeros términos de la sucesión de los números apocalípticos junto con los de la sucesión a(n) = 3715+n. Por ejemplo, (grafica 3000) dibuja
    Numeros_apocalipticos_3000
    y (grafica 30000) dibuja
    Numeros_apocalipticos_30000

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Soluciones

El problema 3SUM

El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se pueden elegir los elementos 7, -9 y 2 que suman 0.

Definir las funciones

tales que
+ (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,

  • (pb3Sum xs) se verifica si xs posee tres elementos cuya suma sea cero. Por ejemplo,

Soluciones

Recorrido por niveles de árboles binarios

Los árboles binarios con valores en las hojas y en los nodos se definen por

Por ejemplo, el árbol

se pueden representar por

Definir la función

tal que (recorrido a) es el recorrido del árbol a por niveles desde la raíz a las hojas y de izquierda a derecha. Por ejemplo,

Soluciones

Biparticiones de un número

Definir la función

tal que (biparticiones n) es la lista de pares de números formados por las primeras cifras de n y las restantes. Por ejemplo,

Soluciones

Números completos

Las descomposiciones de un número n son las parejas de números (x,y) tales que x >= y y la suma de las cuatro operaciones básicas (suma, producto, resta (el mayor menos el menor) y cociente (el mayor entre el menor)) es el número n. Por ejemplo, (8,2) es una descomposición de 36 ya que

Un número es completo si tiene alguna descomposición como las anteriores. Por ejemplo, el 36 es completo pero el 21 no lo es.

Definir las siguientes funciones

tales que

  • (descomposiciones n) es la lista de las descomposiones de n. Por ejemplo,

  • completos es la lista de los números completos. Por ejemplo,

Soluciones

Números como sumas de primos consecutivos

El número 311 se puede escribir de 5 formas distintas como suma de 1 o más primos consecutivos

el número 41 se puede escribir de 4 formas

y el número 14 no se puede escribir como suma de primos consecutivos.

Definir la función

tal que (sumas x) es la lista de las formas de escribir x como suma de uno o más números primos consecutivos. Por ejemplo,

Soluciones

Estratificación de un árbol

Los árboles se pueden representar mediante el siguiente tipo de datos

Por ejemplo, los árboles

se representan por

Un estrato de un árbol es la lista de nodos que se encuentran al mismo nivel de profundidad. Por ejemplo, los estratos del árbol ej1 son [1], [8,3] y [4].

Definir la función

tal que (estratos x) es la lista de los estratos del árbol x. Por ejemplo,

Soluciones

Distancia a Erdős

Una de las razones por la que el matemático húngaro Paul Erdős es conocido es por la multitud de colaboraciones que realizó durante toda su carrera, un total de 511. Tal es así que se establece la distancia a Erdős como la distancia que has estado de coautoría con Erdős. Por ejemplo, si eres Paul Erdős tu distancia a Erdős es 0, si has escrito un artículo con Erdős tu distancia es 1, si has escrito un artículo con alguien que ha escrito un artículo con Erdős tu distancia es 2, etc. El objetivo de este problema es definir una función que a partir de una lista de pares de coautores y un número natural n calcular la lista de los matemáticos a una distancia n de Erdős.

Para el problema se considerará la siguiente lista de coautores

La lista anterior es real y se ha obtenido del artículo Famous trails to Paul Erdős.

Definir la función

tal que (numeroDeErdos xs n) es la lista de lista de los matemáticos de la
lista de coautores xs que se encuentran a una distancia n de Erdős. Por ejemplo,

Nota: Este ejercicio ha sido propuesto por Enrique Naranjo.

Soluciones

Listas engarzadas

Una lista de listas es engarzada si el último elemento de cada lista coincide con el primero de la siguiente.

Definir la función

tal que (engarzada xss) se verifica si xss es una lista engarzada. Por ejemplo,

Soluciones

Números consecutivos compuestos

Una serie compuesta de longitud n es una lista de n números consecutivos que son todos compuestos. Por ejemplo, [8,9,10] y [24,25,26] son dos series compuestas de longitud 3.

Cada serie compuesta se puede representar por el par formado por su primer y último elemento. Por ejemplo, las dos series anteriores se pueden representar pos (8,10) y (24,26) respectivamente.

Definir la función