Menu Close

Longitud de la parte periódica

La propiedad de la longitud de la parte periódica afirma que

Si p es un número primo distinto de 2 y de 5, entonces la longitud del período de 1/p es el menor entero positivo n tal que p divide a 10^n - 1.

El objetivo de este ejercicio es la verificación de dicha propiedad.

Las fracciones se representan por un par de enteros. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

   type Fraccion = (Integer,Integer)

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

 6/2  = 3                  se representa por (3,[],[])
 1/2  = 0.5                se representa por (0,[5],[])
 1/3  = 0.333333...        se representa por (0,[],[3])  
23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

   type Decimal = (Integer,[Integer],[Integer])

Definir, usando las funciones cocientesRestos y primerRepetido de los ejercicios anteriores, las funciones

   decimal :: Fraccion -> Decimal
   longitudPeriodo :: Fraccion -> Integer

tales que

  • (decimal f) es la representación decimal de la fracción f. Por ejemplo,
     decimal (6,2)          ==  (3,[],[])
     decimal (3,4)          ==  (0,[7,5],[])
     decimal (1,3)          ==  (0,[],[3])
     decimal (23,14)        ==  (1,[6],[4,2,8,5,7,1])
     decimal (247813,19980) ==  (12,[4,0],[3,0,5])
     decimal (1,101)        ==  (0,[],[0,0,9,9])
  • (longitudPeriodo f) es la longitud de la parte periódica de la representación decimal de la fracción f. Por ejemplo,
     longitudPeriodo (6,2)           ==  0
     longitudPeriodo (3,4)           ==  0
     longitudPeriodo (1,3)           ==  1
     longitudPeriodo (23,14)         ==  6
     longitudPeriodo (247813,19980)  ==  3
     longitudPeriodo (1,101)         ==  4
     longitudPeriodo (1,1229)        ==  1228

Comprobar con QuickCheck la propiedad de la longitud de la parte periódica; es decir, k es un número natural distinto de 0 y 2 y p es el primo k-ésimo, entonces la longitud del período de 1/p es el menor entero positivo n tal que p divide a 10^n - 1..

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck
 
type Fraccion = (Integer,Integer)
type Decimal = (Integer,[Integer],[Integer])
 
decimal :: Fraccion -> Decimal
decimal (n,d) 
  | snd y == 0 = (fst x, map fst xs, [])
  | otherwise  = (fst x, map fst xs, map fst (y:zs))
  where
    qrs         = cocientesRestos (n,d)
    Just (q,r)  = primerRepetido qrs
    (x:xs,y:ys) = break (==(q,r)) qrs
    zs          = takeWhile (/=(q,r)) ys
 
cocientesRestos :: Fraccion -> [(Integer,Integer)]
cocientesRestos (n,d) =
  (q,r) : cocientesRestos (10*r, d)
  where (q,r) = quotRem n d
 
primerRepetido :: Eq a => [a] -> Maybe a
primerRepetido xs = aux xs []
  where
    aux [] _                     = Nothing
    aux (x:xs') ys | x `elem` ys = Just x
                   | otherwise   = aux xs' (x:ys) 
 
longitudPeriodo :: Fraccion -> Int
longitudPeriodo (n,d) = length xs
  where (_,_,xs) = decimal (n,d)
 
-- La propiedad es
prop_LongitudPeriodo :: Int -> Property
prop_LongitudPeriodo k =
  k > 0 && k /= 2 
  ==>
  longitudPeriodo (1,p) ==
  head [n | n <- [1..], (10^n-1) `mod` p == 0]
  where p = primes !! k
 
-- La comprobación es
--    λ> quickCheck prop_LongitudPeriodo
--    +++ OK, passed 100 tests.

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

“En el desarrollo de la comprensión de los fenómenos complejos, la herramienta más poderosa de que dispone el intelecto humano es la abstracción. La abstracción surge del reconocimiento de las similitudes entre ciertos objetos, situaciones o procesos en el mundo real y de la decisión de concentrarse en estas similitudes e ignorar, por el momento, sus diferencias.”

Tony Hoare

2 soluciones de “Longitud de la parte periódica

  1. fercarnav
    import Data.Numbers.Primes
    import Data.List
     
    type Fraccion = (Integer,Integer)
     
    type Decimal = (Integer,[Integer],[Integer])
     
    decimal :: Fraccion -> Decimal
    decimal (a,b)
      | mod a b == 0 = (x, [], [])
      | solo2y5 b    = (x , xs , [] )
      | sin2o5 b     = (x, [], hastaquerepita xs z)
      | otherwise    = (x,genericTake (max2y5 b) xs, hastaquerepita ys 1)
      where (x:xs) = restos a b
            ys     = genericDrop (max2y5 b) xs
            z      = longitud b
     
    restos :: Integer -> Integer -> [Integer]
    restos a b | mod a b == 0 = [div a b]
    restos a b = div a b : restos (10*(mod a b)) b
     
    solo2y5 :: Integer -> Bool
    solo2y5 n = [x | x <- primeFactors n , not (x==2 || x==5)] == []
     
    con2y5 :: Integer -> [Integer]
    con2y5 n = [x | x <- primeFactors n , x==2  || x==5] 
     
    sin2o5 :: Integer -> Bool
    sin2o5 n = not (elem 2 xs || elem 5 xs)
      where xs = primeFactors n
     
    max2y5 :: Integer -> Integer
    max2y5 n = maximum (map (genericLength) (group (con2y5 n)))
     
    longitud :: Integer -> Integer
    longitud n = sum [1 | x <- show n]
     
    longitudPeriodo :: Fraccion -> Integer
    longitudPeriodo (a,b) = genericLength zs
      where (_, _, zs) = decimal (a,b)
     
    menorEntero :: Integer -> Integer
    menorEntero p = head [ x | x <- [1..], mod (10^x - 1) p == 0]
     
    prop_partePeriodica :: Int -> Property
    prop_partePeriodica k = k /= 0 && (abs k) /= 2 ==>
      longitudPeriodo (1,p) == menorEntero p
      where p = primes !! (abs k)
     
    hastaquerepita :: [Integer] -> Integer-> [Integer]
    hastaquerepita xs i
      | genericTake i xs == genericTake i (genericDrop i xs) = genericTake i xs
      | otherwise = hastaquerepita xs (i+1)
  2. Carlos
    import Data.Numbers.Primes
    import Data.List
    import Data.Maybe
    import Test.QuickCheck
     
    type Fraccion = (Integer,Integer)
    type Decimal = (Integer,[Integer],[Integer])
     
    cocientesRestos :: Fraccion -> [(Integer,Integer)]
    cocientesRestos (n,m) = (q,r) : cocientesRestos (10*r, m)
                      where (q,r) = quotRem n m
     
    primerRepetido :: Eq a => [a] -> Maybe a
    primerRepetido = go []
      where
        go _  [] = Nothing
        go rs (x:xs)
          | elem x rs = Just x
          | otherwise = go (x:rs) xs
     
    decimal :: Fraccion -> Decimal
    decimal f = (fst x, map fst ys, map fst zs)
      where 
        (x:xs) = cocientesRestos f
        a = fromJust (primerRepetido xs)
        (ys,zs) = fmap uncycle (break (==a) xs)
          where uncycle (a:x:xs) = a : takeWhile (/=a) (x:xs)
                uncycle [] = []
     
    longitudPeriodo :: Fraccion -> Integer
    longitudPeriodo (n,m) = genericLength zs
           where (_,_,zs) = decimal (n,m)
     
    prop_Periodo :: (Positive Int) -> Property
    prop_Periodo (Positive k) = k /= 2 ==> longitudPeriodo (1,p) == n
      where
        p = primes !! k
        n = fst $ head $ dropWhile (g . snd) $ map f [1..]
          where f n = (n, 10^n - 1)
                g x = mod x p /= 0

    *Main> quickCheck prop_Periodo
    +++ OK, passed 100 tests; 5 discarded.

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.