Dígitos en la factorización

El enunciado del problema 652 de Números y algo más es el siguiente

Si factorizamos los factoriales de un número en función de sus divisores primos y sus potencias, ¿Cuál es el menor número n tal que entre los factores primos y los exponentes de estos, n! contiene los dígitos del cero al nueve? Por ejemplo

  • 6! = 2⁴x3²x5¹, le faltan los dígitos 0,6,7,8 y 9
  • 12! = 2¹⁰x3⁵x5²x7¹x11¹, le faltan los dígitos 4,6,8 y 9

Definir la función

tal que (digitosDeFactorizacion n) es el conjunto de los dígitos que aparecen en la factorización de n. Por ejemplo,

Usando la función anterior, calcular la solución del problema.

Comprobar con QuickCheck que si n es mayor que 100, entonces

Soluciones

La solución en Maxima

El algoritmo binario del mcd

El máximo común divisor (mcd) de dos números enteros no negativos se puede calcular mediante un algoritmo binario basado en las siguientes propiedades:

  1. Si a,b son pares, entonces mcd(a,b) = 2*mcd(a/2,b/2)
  2. Si a es par y b impar, entonces mcd(a,b) = mcd(a/2,b)
  3. Si a es impar y b par, entonces mcd(a,b) = mcd(a,b/2)
  4. Si a y b son impares y a > b, entonces mcd(a,b) = mcd((a-b)/2,b)
  5. Si a y b son impares y a < b, entonces mcd(a,b) = mcd(a,(b-a)/2)
  6. mcd(a,0) = a
  7. mcd(0,b) = b
  8. mcd(a,a) = a

Por ejemplo, el cálculo del mcd(660,420) es

Definir la función

Definir la función

tal que (mcd a b) es el máximo común divisor de a y b calculado mediante el algoritmo binario del mcd. Por ejemplo,

Comprobar con QuickCheck que, para los enteros no negativos, las funciones mcd y gcd son equivalentes.

Soluciones

Parte libre de cuadrados y parte cuadrada de un número

La parte libre de cuadrados de un número n es el producto de todos sus divisores primos con exponente impar en la factorización prima de n. Por ejemplo, la parte libre de cuadrados de 360 es 10 ya que 360 = 2³3²5 y 2.5 = 10; además, 360 = 10.6²

La parte cuadrada de un número n es el mayor número cuadrado que divide a n. Por ejemplo, la parte cuadrada de 360 es 6.

Definir las funciones

tales que

  • (parteLibre x) es la parte libre de x. Por ejemplo,

  • (parteCuadrada x) es la parte cuadrada de x. Por ejemplo,

Soluciones

Referencias

2016 es un número práctico

Un entero positivo n es un número práctico si todos los enteros positivos menores que él se pueden expresar como suma de distintos divisores de n. Por ejemplo, el 12 es un número práctico, ya que todos los enteros positivos menores que 12 se pueden expresar como suma de divisores de 12 (1, 2, 3, 4 y 6) sin usar ningún divisor más de una vez en cada suma:

En cambio, 14 no es un número práctico ya que 6 no se puede escribir como suma, con sumandos distintos, de divisores de 14.

Definir la función

tal que (esPractico n) se verifica si n es un número práctico. Por ejemplo,

Soluciones

Referencias

Basado en el artículo de Gaussianos Feliz Navidad y Feliz Año (número práctico) 2016.

Otras referencias

Factorizable respecto de una lista

Definir la función

tal que (factorizable x ys) se verifica si x se puede escribir como producto de potencias de elementos de ys. Por ejemplo,

Soluciones

Los números de Smith

Un número de Smith es un número natural compuesto que cumple que la suma de sus dígitos es igual a la suma de los dígitos de todos sus factores primos (si tenemos algún factor primo repetido lo sumamos tantas veces como aparezca). Por ejemplo, el 22 es un número de Smith ya que

y el 4937775 también lo es ya que

Definir las funciones

tales que

  • (esSmith x) se verifica si x es un número de Smith. Por ejemplo,

  • smith es la lista cuyos elementos son los números de Smith. Por ejemplo,

Soluciones

Productos de N números consecutivos

La semana pasada se planteó en Twitter el siguiente problema

Se observa que

¿Existen ejemplos de otros productos de cuatro enteros consecutivos iguales a un producto de tres enteros consecutivos?

Definir la función

tal que (esProductoDeNconsecutivos n x) es (Just m) si x es el producto de n enteros consecutivos a partir de m y es Nothing si x no es el producto de n enteros consecutivos. Por ejemplo,

Para ejemplos mayores,

Usando la función esProductoDeNconsecutivos resolver el problema.

Soluciones

Primos gemelos próximos a múltiplos de 6

Un par de números primos (p,q) es un par de números primos gemelos si su distancia de 2; es decir, si q = p+2. Por ejemplo, (17,19) es una par de números primos gemelos.

Se dice que un par de números (x,y) está próximo a un múltiplo de 6 si es de la forma (6*n-1,6*n+1). Por ejemplo, (17,19) está cerca de un múltiplo de 6 porque (17,19) = (6*3-1,6*3+1).

Definir las funciones

tales que

  • (primosGemelos n) es la lista de los primos gemelos menores que n. Por ejemplo,

  • (primosGemelosNoProximosAmultiplosDe6 n) es la lista de los primos gemelos menores que n que no están próximos a un múltiplo de 6. Por ejemplo,

Soluciones

Números muy divisibles por 3

Se dice que un número n es muy divisible por 3 si es divisible por 3 y sigue siendo divisible por 3 si vamos quitando dígitos por la derecha. Por ejemplo, 96060 es muy divisible por 3 porque 96060, 9606, 960, 96 y 9 son todos divisibles por 3.

Definir las funciones

tales que

  • (muyDivPor3 n) se verifica si n es muy divisible por 3. Por ejemplo,

  • (numeroMuyDivPor3CifrasC k) es la cantidad de números de k cifras muy divisibles por 3. Por ejemplo,

Soluciones

Próximos a múltiplos de 6

Se dice que un par de números (x,y) está próximo a un múltiplo de 6 si es de la forma (6*n-1,6*n+1). Por ejemplo, (17,19) está cerca de un múltiplo de 6 porque (17,19) = (6*3-1,6*3+1).

Definir la función

tal que (proximosAmultiplosDe6 (x,y)) se verifica si el par (x,y) está próximo a un múltiplo de 6. Por ejemplo,

Soluciones

Entero positivo con ciertas propiedades

El 6 de octubre, se propuso en el blog Gaussianos el siguiente problema

Demostrar que para todo entero positivo n, existe otro entero positivo que tiene las siguientes propiedades:

  1. Tiene exactamente n dígitos.
  2. Ninguno de sus dígitos es 0.
  3. Es divisible por la suma de sus dígitos.

Definir la función

tal que (especiales n) es la lista de los números enteros que cumplen las 3 propiedades anteriores para n. Por ejemplo,

En el primer ejemplo, 12 es un número especial para 2 ya que tiene exactamente 2 dígitos, ninguno de sus dígitos es 0 y 12 es divisible por la suma de sus dígitos.

Soluciones

Con mínimo común denominador

Los números racionales se pueden representar como pares de enteros:

Definir la función

tal que (reducida xs) es la lista de los números racionales donde cada uno es igual al correspondiente elemento de xs y el denominador de todos los elementos de (reducida xs) es el menor número que cumple dicha condición; es decir, si xs es la lista

entonces (reducida xs) es

tales que

y d es el menor posible. Por ejemplo,

Soluciones

Perímetro más frecuente de triángulos rectángulos

El grado perimetral de un número p es la cantidad de tres triángulos rectángulos de lados enteros cuyo perímetro es p. Por ejemplo, el grado perimetral de 120 es 3 ya que sólo hay 3 triángulos rectángulos de lados enteros cuyo perímetro es 120: {20,48,52}, {24,45,51} y {30,40,50}.

Definir la función

tal que (maxGradoPerimetral n) es el par (m,ps) tal que m es el máximo grado perimetral de los números menores o iguales que n y ps son los perímetros, menores o iguales que n, cuyo grado perimetral es m. Por ejemplo,

Soluciones

Números de suma prima hereditarios por la derecha

Decimos que un número es de suma prima si la suma de todos sus dígitos es un número primo. Por ejemplo el número 562 es de suma prima pues la suma de sus dígitos es el número primo 13; sin embargo, el número 514 no es de suma prima pues la suma de sus dígitos es 10, que no es primo.

Decimos que un número es de suma prima hereditario por la derecha si es de suma prima y los números que se obtienen eliminando sus últimas cifras también son de suma prima. Por ejemplo 7426 es de suma prima hereditario por la derecha pues 7426, 742, 74 y 7 son todos números de suma prima.

Definir la constante

cuyo valor es la lista infinita de los números de suma prima hereditarios por la derecha. Por ejemplo,

Soluciones

Orden de divisibilidad

El orden de divisibilidad de un número x es el mayor n tal que para todo i menor o igual que n, los i primeros dígitos de n es divisible por i. Por ejemplo, el orden de divisibilidad de 74156 es 3 porque

Definir la función

tal que (ordenDeDivisibilidad x) es el orden de divisibilidad de x. Por ejemplo,

Soluciones

Números con la misma cantidad de anteriores con 1 que sin 1

Una propiedad del número 24 es que entre los números menores o iguales que 24 hay la misma cantidad de números con el dígito 1 que sin el 1; en efecto, los que tienen 1 son

y los que no lo tienen son

Diremos que un número es especial si cumple dicha propiedad.

Definir la sucesión

cuyos elementos son los números especiales. Por ejemplo,

Soluciones

Menor número triangular con más de n divisores

La sucesión de los números triangulares se obtiene sumando los números naturales.

Así, el 7º número triangular es

Los primeros 10 números triangulares son

Los divisores de los primeros 7 números triangulares son:

Como se puede observar, 28 es el menor número triangular con más de 5 divisores.

Definir la función

tal que (menorTriangularConAlMenosNDivisores n) es el menor número triangular que tiene al menos n divisores. Por ejemplo,

Soluciones

Mayor capicúa producto de dos números de n cifras

Un capicúa es un número que es igual leído de izquierda a derecha que de derecha a izquierda.

Definir la función

tal que (mayorCapicuaP n) es el mayor capicúa que es el producto de dos números de n cifras. Por ejemplo,

Soluciones

2015 y los números con factorización capicúa

Un número tiene factorización capicúa si puede escribir como un producto de números primos tal que la concatenación de sus dígitos forma un número capicúa. Por ejemplo, el 2015 tiene factorización capicúa ya que 2015 = 13·5·31, los factores son primos y su concatenación es 13531 que es capicúa.

Definir la sucesión

formada por los números que tienen factorización capicúa. Por ejemplo,

Usando conFactorizacionesCapicuas escribir expresiones cuyos valores sean las respuestas a las siguientes preguntas y calcularlas

  1. ¿Qué lugar ocupa el 2015 en la sucesión?
  2. ¿Cuál fue el anterior año con factorización capicúa?
  3. ¿Cuál será el siguiente año con factorización capicúa?

Soluciones

Enumeración de los pares de números naturales

Los pares de los números naturales se pueden ordenar por la suma de sus componentes y entre los pares con la misma suma elegir antes al que tiene mayos su primera componente.

Definir la función

tal que pares es la lista de los pares de números naturales con el orden anterior. por ejemplo,

Usando la definición de pares, definir la función

tal que (posicion p) es la posición del par p en la lista pares. Por ejemplo,

Finalmente, comprobar con QuickCheck que para cualquier par (x,y) de números naturales, la (posicion (x,y)) es igual a (y + (x+y+1)*(x+y) div 2).

Nota. En la comprobación usar

Soluciones

2015, suma de dígitos y número de divisores

Una propiedad del 2015 es que la suma de sus dígitos coincide con el número de sus divisores; en efecto, la suma de sus dígitos es 2+0+1+5=8 y tiene 8 divisores (1, 5, 13, 31, 65, 155, 403 y 2015).

Definir la sucesión

formada por los números n tales que la suma de los dígitos de n coincide con el número de divisores de n. Por ejemplo,

Usar la sucesión para responder las siguientes cuestiones

  • ¿Cuántos años hasta el 2015 inclusive han cumplido la propiedad?
  • ¿Cuál fue el anterior al 2015 que cumplió la propiedad?
  • ¿Cuál será el siguiente al 2015 que cumplirá la propiedad?

Nota: La sucesión especiales es la misma que la A057531 de la OEIS (On-Line Encyclopedia of Integer Sequences).

Soluciones

Números que sumados a su siguiente primo dan primos

Introducción

La Enciclopedia electrónica de sucesiones de enteros (OEIS por sus siglas en inglés, de On-Line Encyclopedia of Integer Sequences) es una base de datos que registra sucesiones de números enteros. Está disponible libremente en Internet, en la dirección http://oeis.org.

La semana pasada Antonio Roldán añadió una nueva sucesión a la OEIS, la A249624 que sirve de base para el problema de hoy.

Enunciado

Soluciones

Último dígito no nulo del factorial

Enunciado

Soluciones

Parte impar de un número

Enunciado

Soluciones

Laberinto numérico

Enunciado

Soluciones

Divide si todos son múltiplos

Ejercicio. Definir la función

tal que (divideSiTodosMultiplos x ys) es justo la lista de los cocientes de los elementos de ys entre x si todos son múltiplos de x y Nothing en caso contrario. Por ejemplo,

Soluciones

Mayor sucesión del problema 3n+1

Enunciado

Soluciones

Referencia

El ejercicio está basado en The 3n + 1 problem de UVa Online Judge.