Números equidigitales

PorJosé A. Alonso 18-enero-202125-enero-2021

Un número equidigital es un número natural que tiene el mismo número de dígitos que el número de dígitos en su factorización prima, incluidos los exponentes mayores que 1. Por ejemplo,

10 es equidigital ya que tiene 2 dígitos al igual que su factorización prima (2 x 5).
25 es equidigital ya que tiene 2 dígitos al igual que su factorización prima (5^2).
121 es equidigital ya que tiene 3 dígitos al igual que su factorización prima (11^2).
175 es equidigital ya que tiene 3 dígitos al igual que su factorización prima (5^2 x 7).
1125 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (3^2 x 5^3).
2021 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (43 x 47).
3072 es equidigital ya que tiene 4 dígitos al igual que su factorización prima (3 x 2^10).

Definir las funciones

   esEquidigital :: Int -> Bool
   equidigitales :: [Int]

1 2	esEquidigital :: Int -> Bool equidigitales :: [Int]

tal que

(esEquidigital x) se verifica si x es un número equidigital. Por ejemplo.

     esEquidigital 10    ==  True
     esEquidigital 11    ==  True
     esEquidigital 2021  ==  True
     esEquidigital 2022  ==  False

esEquidigital 10 == True

esEquidigital 11 == True

esEquidigital 2021 == True

esEquidigital 2022 == False

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

     λ> take 20 equidigitales
     [2,3,5,7,10,11,13,14,15,16,17,19,21,23,25,27,29,31,32,35]
     λ> equidigitales !! 755
     2021
     λ> equidigitales !! 100000
     405341

λ> take 20 equidigitales

[2,3,5,7,10,11,13,14,15,16,17,19,21,23,25,27,29,31,32,35]

λ> equidigitales !! 755

2021

λ> equidigitales !! 100000

405341

Comprobar con QuickChek que el conjunto de los números equidigitales es infinito; es decir, para cada entero n existe un equidigital mayor que n.

Soluciones

import Data.Numbers.Primes
import Data.List
import Test.QuickCheck

esEquidigital :: Int -> Bool
esEquidigital x =
  nDigitos x == nDigitosFactorizacion x

-- (nDigitos n) es el número de dígitos de n. Por ejemplo,
--    nDigitos 2021  ==  4
nDigitos :: Int -> Int
nDigitos = length . show

-- (nDigitosFactorizacion x) es el número de dígitos en la factorización
-- prima de x, incluyendo los exponentes mayores que 1. Por ejemplo,
--    nDigitosFactorizacion 3000  ==  5
--    nDigitosFactorizacion 2021  ==  4
--    nDigitosFactorizacion 3072  ==  4
nDigitosFactorizacion :: Int -> Int
nDigitosFactorizacion x =
  sum [nDigitos y + aux n | (y,n) <- factorizacion x]
  where aux 1 = 0
        aux n = nDigitos n

-- (factorizacion x) es la factorización prima de x expresada como una
-- lista de pares que son las bases y los exponentes. Por ejemplo,
--    factorizacion 3000  ==  [(2,3),(3,1),(5,3)]
--    factorizacion 2021  ==  [(43,1),(47,1)]
--    factorizacion 3072  ==  [(2,10),(3,1)]
factorizacion :: Int -> [(Int,Int)]
factorizacion x =
  [(y, 1 + length ys) | (y:ys) <- group (primeFactors x)]

equidigitales :: [Int]
equidigitales = filter esEquidigital [1..]

-- La propiedad es
prop_equidigitales :: Int -> Property
prop_equidigitales n =
  n > 0 ==> any esEquidigital [n+1..]

-- La comprobación es
--    λ> quickCheck prop_equidigitales
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes

import Data.List

import Test.QuickCheck

esEquidigital :: Int -> Bool

esEquidigital x =

nDigitos x == nDigitosFactorizacion x

-- (nDigitos n) es el número de dígitos de n. Por ejemplo,

-- nDigitos 2021 == 4

nDigitos :: Int -> Int

nDigitos = length . show

-- (nDigitosFactorizacion x) es el número de dígitos en la factorización

-- prima de x, incluyendo los exponentes mayores que 1. Por ejemplo,

-- nDigitosFactorizacion 3000 == 5

-- nDigitosFactorizacion 2021 == 4

-- nDigitosFactorizacion 3072 == 4

nDigitosFactorizacion :: Int -> Int

nDigitosFactorizacion x =

sum [nDigitos y + aux n | (y,n) <- factorizacion x]

where aux 1 = 0

aux n = nDigitos n

-- (factorizacion x) es la factorización prima de x expresada como una

-- lista de pares que son las bases y los exponentes. Por ejemplo,

-- factorizacion 3000 == [(2,3),(3,1),(5,3)]

-- factorizacion 2021 == [(43,1),(47,1)]

-- factorizacion 3072 == [(2,10),(3,1)]

factorizacion :: Int -> [(Int,Int)]

factorizacion x =

[(y, 1 + length ys) | (y:ys) <- group (primeFactors x)]

equidigitales :: [Int]

equidigitales = filter esEquidigital [1..]

-- La propiedad es

prop_equidigitales :: Int -> Property

prop_equidigitales n =

n > 0 ==> any esEquidigital [n+1..]

-- La comprobación es

-- λ> quickCheck prop_equidigitales

-- +++ OK, passed 100 tests.

6 Comentarios

import Data.List
import Test.QuickCheck
import Data.Numbers.Primes

esEquidigital :: Integer -> Bool
esEquidigital n
  | isPrime n = True
  | otherwise = length (show n) == sum (map (\x -> length (show x)) (aux (primeFactors n)))

-- aux xs es una función que aplicada a la lista de factores primos de un
-- número n devuelve otra lista en la que aparece al lado de cada factor su
-- exponente correspondiente de la factorización.

aux :: [Integer] -> [Integer]
aux []     = []
aux (x:xs)
  | lps == 1  = x : aux (xs \\ ps)
  | otherwise = x : ((fromIntegral lps) : aux (xs \\ ps))
  where ps  = takeWhile (== x) (x:xs)
        lps = length ps

equidigitales :: [Integer]
equidigitales = filter esEquidigital [1..]

propEquidigitales :: Integer -> Bool
propEquidigitales n = not (null (filter esEquidigital [n..]))

-- La comprobación es:
-- λ> quickCheck propEquidigitales
-- +++ OK, passed 100 tests.

import Data.List

import Test.QuickCheck

import Data.Numbers.Primes

esEquidigital :: Integer -> Bool

esEquidigital n

| isPrime n = True

| otherwise = length (show n) == sum (map (\x -> length (show x)) (aux (primeFactors n)))

-- aux xs es una función que aplicada a la lista de factores primos de un

-- número n devuelve otra lista en la que aparece al lado de cada factor su

-- exponente correspondiente de la factorización.

aux :: [Integer] -> [Integer]

aux [] = []

aux (x:xs)

| lps == 1 = x : aux (xs \\ ps)

| otherwise = x : ((fromIntegral lps) : aux (xs \\ ps))

where ps = takeWhile (== x) (x:xs)

lps = length ps

equidigitales :: [Integer]

equidigitales = filter esEquidigital [1..]

propEquidigitales :: Integer -> Bool

propEquidigitales n = not (null (filter esEquidigital [n..]))

-- La comprobación es:

-- λ> quickCheck propEquidigitales

-- +++ OK, passed 100 tests.

Responder

-- Otra forma de definir esEquidigital es la siguiente:

esEquidigital :: Integer -> Bool
esEquidigital n
  | isPrime n = True
  | otherwise = length (show n) == longFact n

longFact :: Integer -> Int
longFact = sum . (map aux) . fact

aux :: (Int, Int) -> Int
aux (x,y)
  | y == 1    = lsx
  | otherwise = lsx + lsy
    where lsx = length (show x)
          lsy = length (show y)

fact :: Integer -> [(Int, Int)]
fact n = [(fromIntegral (head xs), length xs) | xs <- group (primeFactors n)]

-- Otra forma de definir esEquidigital es la siguiente:

esEquidigital :: Integer -> Bool

esEquidigital n

| isPrime n = True

| otherwise = length (show n) == longFact n

longFact :: Integer -> Int

longFact = sum . (map aux) . fact

aux :: (Int, Int) -> Int

aux (x,y)

| y == 1 = lsx

| otherwise = lsx + lsy

where lsx = length (show x)

lsy = length (show y)

fact :: Integer -> [(Int, Int)]

fact n = [(fromIntegral (head xs), length xs) | xs <- group (primeFactors n)]

Responder

-- Un número equidigital es un número natural que tiene el mismo número de
-- dígitos que el número de dígitos en su factorización prima, incluidos los
-- exponentes mayores que 1.

esEquidigital :: Int -> Bool
esEquidigital n = genericLength (listaDigitos' n) ==
                  genericLength (listaDigitosPrimos n)

-- Usamos la función ya definida para números compuestos persistentes:

listaDigitos' :: Int -> [Int]
listaDigitos' n | n < 10  = [n]
                | n >= 10 = listaDigitos' (n `div` 10) ++ [n `mod` 10]

-- La siguiente función serviría para construir pares de los factores primos y su
-- exponente, mas no nos hará falta puesto que aunque no en orden, una lista de
-- los factores primos y sus exponentes al final tendrá la misma longitud que
-- 2*(longitud de la lista de factores primos emparejados con sus exponentes), y
-- será más eficiente.

-- listaParPrimos n = zip (map head (group (primeFactors n)))
--                        (map length (group (primeFactors n)))

listaFactoresExp :: Int -> [Int]
listaFactoresExp n = filter (/= 1) ((map head (group (primeFactors n))) ++
                                   (map genericLength (group (primeFactors n))))

listaDigitosPrimos :: Int -> [Int]
listaDigitosPrimos n = foldl (++) []
                       (map listaDigitos' (listaFactoresExp n))


equidigitales :: [Int]
equidigitales = filter esEquidigital [1..]


-- Comprobar con QuickChek que el conjunto de los números equidigitales es
-- infinito; es decir, para cada entero n existe un equidigital mayor que n.

prop_equidigitales :: Int -> Property
prop_equidigitales n = n >= 0 ==> any esEquidigital [n+1..]

-- λ> quickCheck prop_equidigitales
-- +++ OK, passed 100 tests.

-- Un número equidigital es un número natural que tiene el mismo número de

-- dígitos que el número de dígitos en su factorización prima, incluidos los

-- exponentes mayores que 1.

esEquidigital :: Int -> Bool

esEquidigital n = genericLength (listaDigitos' n) ==

genericLength (listaDigitosPrimos n)

-- Usamos la función ya definida para números compuestos persistentes:

listaDigitos' :: Int -> [Int]

listaDigitos' n | n < 10 = [n]

| n >= 10 = listaDigitos' (n `div` 10) ++ [n `mod` 10]

-- La siguiente función serviría para construir pares de los factores primos y su

-- exponente, mas no nos hará falta puesto que aunque no en orden, una lista de

-- los factores primos y sus exponentes al final tendrá la misma longitud que

-- 2*(longitud de la lista de factores primos emparejados con sus exponentes), y

-- será más eficiente.

-- listaParPrimos n = zip (map head (group (primeFactors n)))

-- (map length (group (primeFactors n)))

listaFactoresExp :: Int -> [Int]

listaFactoresExp n = filter (/= 1) ((map head (group (primeFactors n))) ++

(map genericLength (group (primeFactors n))))

listaDigitosPrimos :: Int -> [Int]

listaDigitosPrimos n = foldl (++) []

(map listaDigitos' (listaFactoresExp n))

equidigitales :: [Int]

equidigitales = filter esEquidigital [1..]

-- Comprobar con QuickChek que el conjunto de los números equidigitales es

-- infinito; es decir, para cada entero n existe un equidigital mayor que n.

prop_equidigitales :: Int -> Property

prop_equidigitales n = n >= 0 ==> any esEquidigital [n+1..]

-- λ> quickCheck prop_equidigitales

-- +++ OK, passed 100 tests.

Responder

import Data.List           (group)
import Test.QuickCheck     (quickCheck)
import Data.Numbers.Primes (primeFactors)

-- (factorizacion n) es la lista de las bases y exponentes de la
-- factorización prima de n. Por ejemplo,
--    factorizacion 10    ==  [(2,1),(5,1)]
--    factorizacion 25    ==  [(5,2)]
--    factorizacion 121   ==  [(11,2)]
--    factorizacion 175   ==  [(5,2),(7,1)]
--    factorizacion 1125  ==  [(3,2),(5,3)]
--    factorizacion 2021  ==  [(43,1),(47,1)]
--    factorizacion 3072  ==  [(2,10),(3,1)]
factorizacion :: Int -> [(Int,Int)]
factorizacion = map (\xs@(y:_) -> (y,length xs)) . group . primeFactors

-- (numDigFactP n) es el número de dígitos de la factorización prima de
-- n, incluidos los exponentes mayores que 1. Por ejemplo,
--    numDigFactP 10    ==  2
--    numDigFactP 25    ==  2
--    numDigFactP 121   ==  3
--    numDigFactP 175   ==  3
--    numDigFactP 1125  ==  4
--    numDigFactP 2021  ==  4
--    numDigFactP 3072  ==  4
numDigFactP :: Int -> Int
numDigFactP = sum . map aux . factorizacion
  where aux (b,1) = length (show b)
        aux (b,e) = length (show b) + length (show e)

esEquidigital :: Int -> Bool
esEquidigital n = length (show n) == numDigFactP n

equidigitales :: [Int]
equidigitales = filter esEquidigital [1..]

-- Propiedad
-- =========

-- La propiedad es
prop_equidigitales :: Int -> Bool
prop_equidigitales n = any esEquidigital [n+1..]

-- La comprobación es
--    λ> quickCheck prop_equidigitales
--    +++ OK, passed 100 tests.

import Data.List (group)

import Test.QuickCheck (quickCheck)

import Data.Numbers.Primes (primeFactors)

-- (factorizacion n) es la lista de las bases y exponentes de la

-- factorización prima de n. Por ejemplo,

-- factorizacion 10 == [(2,1),(5,1)]

-- factorizacion 25 == [(5,2)]

-- factorizacion 121 == [(11,2)]

-- factorizacion 175 == [(5,2),(7,1)]

-- factorizacion 1125 == [(3,2),(5,3)]

-- factorizacion 2021 == [(43,1),(47,1)]

-- factorizacion 3072 == [(2,10),(3,1)]

factorizacion :: Int -> [(Int,Int)]

factorizacion = map (\xs@(y:_) -> (y,length xs)) . group . primeFactors

-- (numDigFactP n) es el número de dígitos de la factorización prima de

-- n, incluidos los exponentes mayores que 1. Por ejemplo,

-- numDigFactP 10 == 2

-- numDigFactP 25 == 2

-- numDigFactP 121 == 3

-- numDigFactP 175 == 3

-- numDigFactP 1125 == 4

-- numDigFactP 2021 == 4

-- numDigFactP 3072 == 4

numDigFactP :: Int -> Int

numDigFactP = sum . map aux . factorizacion

where aux (b,1) = length (show b)

aux (b,e) = length (show b) + length (show e)

esEquidigital :: Int -> Bool

esEquidigital n = length (show n) == numDigFactP n

equidigitales :: [Int]

equidigitales = filter esEquidigital [1..]

-- Propiedad

-- =========

-- La propiedad es

prop_equidigitales :: Int -> Bool

prop_equidigitales n = any esEquidigital [n+1..]

-- La comprobación es

-- λ> quickCheck prop_equidigitales

-- +++ OK, passed 100 tests.

Responder

También podríamos emplear Lean para formalizar la demostración de que el conjunto de los números equidigitales es infinito. Una prueba, aunque bastante mejorable, sería:

-- ---------------------------------------------------------------------
-- Probar que el conjunto de los números equidigitales es infinito; es 
-- decir, para cada entero n existe un equidigital mayor que n.
-- ---------------------------------------------------------------------

import data.nat.prime
import init.data.string.basic

open nat
open string
open list

@[simp] 
def factAux : (ℕ × ℕ) → list ℕ → list (ℕ × ℕ)
| pp    []       := [pp]
| (a,b) (c :: l) := 
  if a = c then factAux (a,b+1) l else (a,b) :: (factAux (c,1) l)

def factorizacion (n : ℕ) :=
factAux (head (factors n),1) (tail (factors n))

@[simp]
def sumAux : list (ℕ × ℕ) → ℕ
| [] := 0
| ((a,1) :: l) := length (to_string a) + sumAux l
| ((a,b) :: l) := length (to_string a) + length (to_string b) + sumAux l

def equidigital (n : ℕ) :=  
length (to_string n) = sumAux (factorizacion n)

lemma primo_equidigital (p : ℕ) :
prime p → equidigital p :=
begin
  intro hp,
  unfold equidigital,
  unfold factorizacion,
  rw (factors_prime hp),
  simp,
end

lemma aux {n : ℕ} (p : ℕ) :
n ≤ p ∧ prime p → 
n ≤ p ∧ equidigital p :=
and.imp_right (primo_equidigital p)

example (n : ℕ) : ∃ (p : ℕ),
  n ≤ p ∧ equidigital p :=
begin
  apply Exists.imp aux,
  exact exists_infinite_primes n,
end

-- ---------------------------------------------------------------------

-- Probar que el conjunto de los números equidigitales es infinito; es

-- decir, para cada entero n existe un equidigital mayor que n.

-- ---------------------------------------------------------------------

import data.nat.prime

import init.data.string.basic

open nat

open string

open list

@[simp]

def factAux : (ℕ × ℕ) → list ℕ → list (ℕ × ℕ)

| pp [] := [pp]

| (a,b) (c :: l) :=

if a = c then factAux (a,b+1) l else (a,b) :: (factAux (c,1) l)

def factorizacion (n : ℕ) :=

factAux (head (factors n),1) (tail (factors n))

@[simp]

def sumAux : list (ℕ × ℕ) → ℕ

| [] := 0

| ((a,1) :: l) := length (to_string a) + sumAux l

| ((a,b) :: l) := length (to_string a) + length (to_string b) + sumAux l

def equidigital (n : ℕ) :=

length (to_string n) = sumAux (factorizacion n)

lemma primo_equidigital (p : ℕ) :

prime p → equidigital p :=

begin

intro hp,

unfold equidigital,

unfold factorizacion,

rw (factors_prime hp),

simp,

end

lemma aux {n : ℕ} (p : ℕ) :

n ≤ p ∧ prime p →

n ≤ p ∧ equidigital p :=

and.imp_right (primo_equidigital p)

example (n : ℕ) : ∃ (p : ℕ),

n ≤ p ∧ equidigital p :=

begin

apply Exists.imp aux,

exact exists_infinite_primes n,

end

Responder

import Data.List
import Data.Numbers.Primes


agrupar :: Int -> [[Int]]
agrupar n = group (primeFactors n)

factorizacion :: [[Int]] -> [(Int,Int)]
factorizacion [] = []
factorizacion (xs:xss) = [(head xs, length xs)]++factorizacion xss

factorizacionPrima :: Int -> [(Int,Int)]
factorizacionPrima n = factorizacion (agrupar n)

numeroel :: [(Int,Int)] -> Int
numeroel [] = 0
numeroel (x:xs) | snd (x) == 1 = length (show (fst (x))) + numeroel xs
                | otherwise = length (show (fst (x))) + length (show (snd (x))) + numeroel xs

numeroElFact :: Int -> Int
numeroElFact n = numeroel (factorizacionPrima n)

esEquidigital :: Int -> Bool
esEquidigital x = length (show x) == numeroElFact x

equidigitales :: [Int]
equidigitales = [x | x<-[1..], esEquidigital x]

prop_equidigitales :: Int -> Property
prop_equidigitales n =
  n > 0 ==> any esEquidigital [n+1..]

import Data.List

import Data.Numbers.Primes

agrupar :: Int -> [[Int]]

agrupar n = group (primeFactors n)

factorizacion :: [[Int]] -> [(Int,Int)]

factorizacion [] = []

factorizacion (xs:xss) = [(head xs, length xs)]++factorizacion xss

factorizacionPrima :: Int -> [(Int,Int)]

factorizacionPrima n = factorizacion (agrupar n)

numeroel :: [(Int,Int)] -> Int

numeroel [] = 0

numeroel (x:xs) | snd (x) == 1 = length (show (fst (x))) + numeroel xs

| otherwise = length (show (fst (x))) + length (show (snd (x))) + numeroel xs

numeroElFact :: Int -> Int

numeroElFact n = numeroel (factorizacionPrima n)

esEquidigital :: Int -> Bool

esEquidigital x = length (show x) == numeroElFact x

equidigitales :: [Int]

equidigitales = [x | x<-[1..], esEquidigital x]

prop_equidigitales :: Int -> Property

prop_equidigitales n =

n > 0 ==> any esEquidigital [n+1..]

Responder

Números equidigitales

Soluciones

6 Comentarios

Leave a Reply to Inés Mora CaroCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Leave a Reply to Inés Mora CaroCancel reply

Entradas recientes

Buscar

Correo electrónico