Números autodescriptivos

Un número n es autodescriptivo cuando para cada posición k de n (empezando a contar las posiciones a partir de 0), el dígito en la posición k es igual al número de veces que ocurre k en n. Por ejemplo, 1210 es autodescriptivo porque tiene 1 dígito igual a «0», 2 dígitos iguales a «1», 1 dígito igual a «2» y ningún dígito igual a «3».

Definir la función

tal que (autodescriptivo n) se verifica si n es autodescriptivo. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Aproximación del número pi

Una forma de aproximar el número π es usando la siguiente igualdad:

Es decir, la serie cuyo término general n-ésimo es el cociente entre el producto de los primeros n números y los primeros n números impares:

Definir la función

tal que (aproximaPi n) es la aproximación del número π calculada con la serie anterior hasta el término n-ésimo. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Pandigitales primos

Un número con n dígitos es pandigital si contiene todos los dígitos del 1 a n exactamente una vez. Por ejemplo, 2143 es un pandigital con 4 dígitos y, además, es primo.

Definir la lista

tal que sus elementos son los números pandigitales primos, ordenados de mayor a menor. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Codificación de Fibonacci

La codificación de Fibonacci http://bit.ly/1Lllqjv de un número n es una cadena d = d(0)d(1)…d(k-1)d(k) de ceros y unos tal que

donde F(i) es el i-ésimo término de la sucesión de Fibonacci

Por ejemplo, la codificación de Fibonacci de 4 es «1011» ya que los dos últimos elementos son iguales a 1 y

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

Definir la función

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

Comprobar con QuickCheck las siguientes propiedades:

  • Todo entero positivo se puede descomponer en suma de números de la sucesión de Fibonacci.
  • Las codificaciones de Fibonacci tienen como mínimo 2 elementos.
  • En las codificaciones de Fibonacci, la cadena «11» sólo aparece una vez y la única vez que aparece es al final.

Soluciones

El código se encuentra en GitHub.

La sucesión del reloj astronómico de Praga

La cadena infinita «1234321234321234321…», formada por la repetición de los dígitos 123432, tiene una propiedad (en la que se basa el funcionamiento del reloj astronómico de Praga: la cadena se puede partir en una sucesión de números, de forma que la suma de los dígitos de dichos números es la sucesión de los números naturales, como se observa a continuación:

Definir la lista

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

Soluciones

El código se encuentra en GitHub.

Método de bisección para aproximar raíces de funciones

El método de bisección para calcular un cero de una función en el intervalo [a,b] se basa en el teorema de Bolzano:

«Si f(x) es una función continua en el intervalo [a, b], y si, además, en los extremos del intervalo la función f(x) toma valores de signo opuesto (f(a) * f(b) < 0), entonces existe al menos un valor c en (a, b) para el que f(c) = 0".

El método para calcular un cero de la función f en el intervalo [a,b] con un error menor que e consiste en tomar el punto medio del intervalo c = (a+b)/2 y considerar los siguientes casos:

  • Si |f(c)| < e, hemos encontrado una aproximación del punto que anula f en el intervalo con un error aceptable.
  • Si f(c) tiene signo distinto de f(a), repetir el proceso en el intervalo [a,c].
  • Si no, repetir el proceso en el intervalo [c,b].

Definir la función

tal que (biseccion f a b e) es una aproximación del punto del intervalo [a,b] en el que se anula la función f, con un error menor que e, calculada mediante el método de la bisección. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Números para los que mcm(1,2,…n-1) = mcm(1,2,…,n)

Un número n es especial si mcm(1,2,…,n-1) = mcm(1,2,…,n). Por ejemplo, el 6 es especial ya que

Definir la sucesión

cuyos términos son los números especiales. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Cálculo de la suma 1*1! + 2*2! + 3*3! + … + n*n!

Definir la función

tal que (suma n) es la suma 1·1! + 2·2! + 3·3! + ... + n·n!. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Cálculo aproximado de integrales definidas

La integral definida de una función f entre los límites a y b puede calcularse mediante la regla del rectángulo usando la fórmula

con a+n*h+h/2 <= b < a+(n+1)*h+h/2 y usando valores pequeños para h.

Definir la función

tal que (integral a b f h) es el valor de dicha expresión. Por ejemplo, el cálculo de la integral de f(x) = x^3 entre 0 y 1, con paso 0.01, es

Otros ejemplos son

Soluciones

El código se encuentra en GitHub.

Menor número con una cantidad dada de divisores

El menor número con 2 divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).

El menor número con 4 divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).

El menor número con 8 divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.

El menor número con 16 divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.

Definir la función

tal que (menor n) es el menor número con 2^n divisores. Por ejemplo,

Comprobar con QuickCheck que, para todo k >=0, (menor (2^k)) es un divisor de (menor (2^(k+1))).

Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2011.

Soluciones

El código se encuentra en GitHub.

Distancia esperada entre dos puntos de un cuadrado unitario

Definir, por simulación, la función

tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,

El valor exacto de la distancia esperada es

Definir la función

tal que (graficaDistanciaEsperada ns) dibuja las gráficas de los pares (n, distanciaEsperada n) para n en la lista creciente ns junto con la recta y = ve, donde ve es el valor exacto. Por ejemplo, (graficaDistanciaEsperada [10,30..4000]) dibuja

Soluciones

El código se encuentra en GitHub.

Representación matricial de relaciones binarias

Dada una relación r sobre un conjunto de números enteros, la matriz asociada a r es una matriz booleana p (cuyos elementos son True o False), tal que p(i,j) = True si y sólo si i está relacionado con j mediante la relación r.

Las relaciones binarias homogéneas y las matrices booleanas se pueden representar por

Definir la función

tal que (matrizRB r) es la matriz booleana asociada a r. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Codificación de Gödel

Dada una lista de números naturales xs, codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificación de xs es

Definir las funciones

tales que

  • (codificaG xs) es la codificación de Gödel de xs. Por ejemplo,

  • (decodificaG n) es la lista xs cuya codificación es n. Por ejemplo,

Comprobar con QuickCheck que ambas funciones son inversas; es decir,

Soluciones

El código se encuentra en GitHub.

Primos circulares

Un primo circular es un número tal que todas las rotaciones de dígitos producen números primos. Por ejemplo, 195 es un primo circular ya que las rotaciones de sus dígitos son 197, 971 y 719 y los tres números son primos.

Definir la lista

cuyo valor es la lista de los números primos circulares. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Diccionario de frecuencias

Definir la función

tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Descomposiciones con sumandos 1 ó 2

Definir la funciones

tales que

  • (sumas n) es la lista de las descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,

  • (nSumas n) es el número de descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Suma de los elementos de las diagonales matrices espirales

Empezando con el número 1 y moviéndose en el sentido de las agujas del reloj se obtienen las matrices espirales

La suma los elementos de sus diagonales es

Definir la función

tal que (sumaDiagonales n) es la suma de los elementos en las diagonales de la matriz espiral de orden nxn. Por ejemplo.

Comprobar con QuickCheck que el último dígito de (sumaDiagonales n) es 0, 4 ó 6 si n es par y es 1, 5 ó 7 en caso contrario.

Soluciones

El código se encuentra en GitHub.

Término ausente en una progresión aritmética

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay un término de la progresión aritmética que no está en la lista.

Soluciones

El código se encuentra en GitHub.

Polinomios de Bell

Los polinomios de Bell forman una sucesión de polinomios, definida como sigue:

  • B₀(x) = 1 (polinomio unidad)
  • Bₙ(x) = x·[Bₙ(x) + Bₙ'(x)] (donde Bₙ'(x) es la derivada de Bₙ(x))

Por ejemplo,

Definir la función

tal que (polBell n) es el polinomio de Bell de grado n. Por ejemplo,

Notas: Se usa la librería I1M.PolOperaciones que se encuentra aquí y se describe aquí. Además, en el último ejemplo se usa la función coeficiente tal que (coeficiente k p) es el coeficiente del término de grado k en el polinomio p definida por

Soluciones

El código se encuentra en GitHub.

Ordenación de los racionales

En este ejercicio, representamos las fracciones mediante pares de números de enteros.

Definir la función

tal que (fraccionesOrd n) es la lista con las fracciones propias positivas ordenadas, con denominador menor o igual que n. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Polinomios cuadráticos generadores de primos

En 1772, Euler publicó que el polinomio n² + n + 41 genera 40 números primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n = 40, 40²+40+41 = 40(40+1)+41 es divisible por 41.

Usando ordenadores, se descubrió que el polinomio n² – 79n + 1601 genera 80 números primos para todos los valores de n entre 0 y 79.

Definir la función

tal que (generadoresMaximales n) es el par (m,xs) donde

  • xs es la lista de pares (x,y) tales que n²+xn+y es uno de polinomios que genera un número máximo de números primos consecutivos a partir de cero entre todos los polinomios de la forma n²+an+b, con |a| ≤ n y |b| ≤ n y
  • m es dicho número máximo.

Por ejemplo,

Soluciones

El código se encuentra en GitHub.

El triángulo de Floyd

El triángulo de Floyd, llamado así en honor a Robert Floyd, es un triángulo rectángulo formado con números naturales. Para crear un triángulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se continúa escribiendo la secuencia de los números naturales de manera que cada línea contenga un número más que la anterior. Las 5 primeras líneas del triángulo de Floyd son

Definir la función

tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Numeración con base múltiple

Sea (b(i) | i ≥ 1) una sucesión infinita de números enteros mayores que 1. Entonces todo entero x mayor que cero se puede escribir de forma única como

donde cada x(i) satisface la condición 0 ≤ x(i) < b(i+1). Se dice que [x(n),x(n-1),…,x(2),x(1),x(0)] es la representación de x en la base (b(i)). Por ejemplo, la representación de 377 en la base (2, 6, 8, …) es [7,5,0,1] ya que

y, además, 0 ≤ 1 < 2, 0 ≤ 0 < 4, 0 ≤ 5 < 6 y 0 ≤ 7 < 8.

Definir las funciones

tales que

  • (decimalAmultiple bs x) es la representación del número x en la base bs. Por ejemplo,

  • (multipleAdecimal bs cs) es el número decimal cuya representación en la base bs es cs. Por ejemplo,

Comprobar con QuickCheck que se verifican las siguientes propiedades

  • Para cualquier base bs y cualquier entero positivo n,

  • Para cualquier base bs y cualquier entero positivo n, el coefiente i-ésimo de la representación múltiple de n en la base bs es un entero no negativo menos que el i-ésimo elemento de bs.

Soluciones

El código se encuentra en GitHub.

Matriz zigzagueante

La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n² primeros números naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es

La colocación de los elementos se puede ver gráficamente en esta figura

Definir la función

tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Densidades de números abundantes, perfectos y deficientes

La n-ésima densidad de un tipo de número es el cociente entre la cantidad de los números entre 1 y n que son del tipo considerado y n. Por ejemplo, la 7-ésima densidad de los múltiplos de 3 es 2/7 ya que entre los 7 primeros números sólo 2 son múltiplos de 3.

Definir las funciones

tales que

  • (densidades n) es la terna formada por la n-ésima densidad
    • de los números abundantes (es decir, para los que la suma de sus divisores propios es mayor que el número),
    • de los números perfectos (es decir, para los que la suma de sus divisores propios es mayor que el número) y
    • de los números deficientes (es decir, para los que la suma de sus divisores propios es menor que el número).

    Por ejemplo,

  • (graficas n) dibuja las gráficas de las k-ésimas densidades (para k entre 1 y n) de los números abundantes, de los números perfectos y de los números deficientes. Por ejemplo, (graficas 100) dibuja

    y (graficas 400) dibuja

Soluciones

El código se encuentra en GitHub.

Sumas de divisores propios

Definir la función

tal que (sumaDivisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 1 y n y b es la suma de los divisores propios de a. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Parejas de números y divisores

Definir la función

tal que (divisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 2 y n y b es un divisor propio de a. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Sumas de 4 primos

La conjetura de Waring sobre los números primos establece que todo número impar es primo o la suma de tres primos. La conjetura de Goldbach afirma que todo par mayor que 2 es la suma de dos números primos. Ambos ha estado abiertos durante más de 200 años. En este problema no se propone su solución, sino una tarea más simple: buscar una manera de expresar los enteros mayores que 7 como suma de exactamente cuatro números primos; es decir, definir la función

tal que (suma4primos n) es la lista de las cuádruplas crecientes (a,b,c,d) de números primos cuya suma es n (que se supone mayor que 7). Por ejemplo,

Comprobar con QuickCheck que todo entero mayor que 7 se puede escribir como suma de exactamente cuatro números primos.

Soluciones

El código se encuentra en GitHub.

Sucesión de sumas de dos números abundantes

Un número n es abundante si la suma de los divisores propios de n es mayor que n. El primer número abundante es el 12 (cuyos divisores propios son 1, 2, 3, 4 y 6 cuya suma es 16). Por tanto, el menor número que es la suma de dos números abundantes es el 24.

Definir la sucesión

cuyos elementos son los números que se pueden escribir como suma de dos números abundantes. Por ejemplo,

Soluciones

El código se encuentra en GitHub.

Suma de divisores

Definir la función

tal que (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,

Soluciones

El código se encuentra en GitHub.