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)

1	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])

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])

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

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

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

1 2	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])

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

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.

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 Comentarios

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)

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)

Responder

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

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.

Responder

Longitud de la parte periódica

Soluciones

Otras soluciones

Pensamiento

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Otras soluciones

Pensamiento

Se puede imprimir o compartir con

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico