Ir al contenido principal

Números automórficos

Un número n es automórfico si los últimos dígitos de su cuadrado son los dígitos de n. Por ejemplo, 5, 6, 76 y 890625 son números automórficos ya que 5² = 25, 6² = 36, 76² = 5776 y 890625² = 793212890625.

Definir la sucesión

automorficos :: [Integer]

tal que sus elementos son los números automórficos. Por ejemplo,

λ> take 11 automorficos
[1,5,6,25,76,376,625,9376,90625,109376,890625]
λ> automorficos !! 30
56259918212890625

Soluciones

import Data.List (isSuffixOf, nub, sort)

automorficos :: [Integer]
automorficos = filter esAutomorfico [1..]

esAutomorfico :: Integer -> Bool
esAutomorfico n = show n `isSuffixOf` show (n*n)

-- 2ª definición
-- =============

automorficos2 :: [Integer]
automorficos2 = nub (1 : concat [sort [a,b] |
                                 k <- [1..],
                                 let a = 5^(2^k) `mod` 10^k,
                                 let b = 10^k - a + 1])

-- Comparación de eficiencia
-- =========================

-- λ> automorficos !! 12
-- 7109376
-- (16.64 secs, 6,759,638,824 bytes)
-- λ> automorficos2 !! 12
-- 7109376
-- (0.00 secs, 0 bytes)

Referencias