Definir la sucesión
|
1 |
sumasDeDosPrimos :: [Integer] |
cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,
|
1 2 3 4 |
λ> take 23 sumasDeDosPrimos [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31] λ> sumasDeDosPrimos !! (5*10^5) 862878 |
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, …
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, …
Definir la función
|
1 |
factorizacionesH :: Integer -> [[Integer]] |
tal que factorizacionesH n es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,
|
1 2 3 4 |
factorizacionesH 25 == [[5,5]] factorizacionesH 45 == [[5,9]] factorizacionesH 441 == [[9,49],[21,21]] factorizacionesH 80109 == [[9,9,989],[9,69,129]] |
Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque la factorización, como para el 441, puede no ser única).
Read More «Factorizaciones de números de Hilbert»
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, …
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197, …
Definir la sucesión
|
1 |
primosH :: [Integer] |
tal que sus elementos son los primos de Hilbert. Por ejemplo,
|
1 2 |
take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! (3*10^4) == 313661 |
El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el teorema de Navidad de Fermat.
Definir las funciones
|
1 2 3 |
representaciones :: Integer -> [(Integer,Integer)] primosImparesConRepresentacionUnica :: [Integer] primos4nM1 :: [Integer] |
tales que
representaciones n es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo.|
1 2 3 4 5 6 |
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] representaciones 100000147984 == [(0,316228)] length (representaciones (10^10)) == 6 length (representaciones (4*10^12)) == 7 |
primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,|
1 2 |
λ> take 20 primosImparesConRepresentacionUnica [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193] |
primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,|
1 2 |
λ> take 20 primos4nM1 [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193] |
El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y² (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).
Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de
primosImparesConRepresentacionUnica y de primos4nM1 son iguales.
Read More «El teorema de Navidad de Fermat»
Los números de Fibonacci se definen mediante las ecuaciones
|
1 2 3 |
F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), si n > 1 |
Los primeros números de Fibonacci son
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones
|
1 2 3 4 5 6 |
P(0) = 0 P(1) = 1 P(2) = 1 P(3) = 2 P(4) = 4 P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4 |
Los primeros números de Pentanacci son
|
1 |
0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ... |
Definir las funciones
|
1 2 |
pentanacci :: Integer -> Integer pentanaccis :: [Integer] |
tales que
pentanacci n es el n-ésimo número de Pentanacci. Por ejemplo,|
1 2 3 4 5 6 |
λ> pentanacci 14 3525 λ> pentanacci (10^5) `mod` 10^30 482929150584077921552549215816 λ> length (show (pentanacci (10^5))) 29357 |
pentanaccis es la lista de los números de Pentanacci. Por ejemplo,|
1 2 |
λ> take 15 pentanacci [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
module Numeros_de_Pentanacci where import Data.List (genericIndex, zipWith5) import Test.Hspec (Spec, hspec, it, shouldBe) import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs) -- 1ª solución -- =========== pentanacci1 :: Integer -> Integer pentanacci1 0 = 0 pentanacci1 1 = 1 pentanacci1 2 = 1 pentanacci1 3 = 2 pentanacci1 4 = 4 pentanacci1 n = sum [pentanacci1 (n-k) | k <- [1..5]] pentanaccis1 :: [Integer] pentanaccis1 = [pentanacci1 n | n <- [0..]] -- 2ª solución -- =========== pentanaccis2 :: [Integer] pentanaccis2 = 0 : 1 : 1 : 2 : 4 : zipWith5 f (r 0) (r 1) (r 2) (r 3) (r 4) where f a b c d e = a+b+c+d+e r n = drop n pentanaccis2 pentanacci2 :: Integer -> Integer pentanacci2 n = pentanaccis2 `genericIndex` n -- 3ª solución -- =========== pentanaccis3 :: [Integer] pentanaccis3 = p (0, 1, 1, 2, 4) where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e) pentanacci3 :: Integer -> Integer pentanacci3 n = pentanaccis3 `genericIndex` n -- 4ª solución -- =========== pentanaccis4 :: [Integer] pentanaccis4 = 0: 1: 1: 2: 4: p pentanaccis4 where p (a:b:c:d:e:xs) = (a+b+c+d+e): p (b:c:d:e:xs) pentanacci4 :: Integer -> Integer pentanacci4 n = pentanaccis4 `genericIndex` n -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "ej1" $ take 15 pentanaccis1 `shouldBe` [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] it "ej2" $ take 15 pentanaccis2 `shouldBe` [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] it "ej3" $ take 15 pentanaccis3 `shouldBe` [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] it "ej4" $ take 15 pentanaccis4 `shouldBe` [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] -- La verificación es -- λ> verifica -- -- 4 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_pentanaccis :: NonNegative Int -> Bool prop_pentanaccis (NonNegative n) = all (== pentanaccis1 !! n) [pentanaccis1 !! n, pentanaccis2 !! n, pentanaccis3 !! n] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=25}) prop_pentanaccis -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> pentanacci1 25 -- 5976577 -- (4.64 secs, 1,865,626,496 bytes) -- λ> pentanacci2 25 -- 5976577 -- (0.00 secs, 578,584 bytes) -- -- λ> length (show (pentanacci2 (10^5))) -- 29357 -- (1.16 secs, 2,543,272,136 bytes) -- λ> length (show (pentanacci3 (10^5))) -- 29357 -- (1.00 secs, 2,560,881,608 bytes) -- λ> length (show (pentanacci4 (10^5))) -- 29357 -- (1.03 secs, 2,592,078,744 bytes) |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
from itertools import count, islice from sys import set_int_max_str_digits from timeit import Timer, default_timer from typing import Iterator set_int_max_str_digits(30000) # 1ª solución # =========== def pentanacci1(n: int) -> int: if n == 0: return 0 if n == 1: return 1 if n == 2: return 1 if n == 3: return 2 if n == 4: return 4 return sum((pentanacci1(n-k) for k in range(1, 6))) def pentanaccis1() -> Iterator[int]: return (pentanacci1(n) for n in count()) # 2ª solución # =========== def pentanaccis2() -> Iterator[int]: seq = [0, 1, 1, 2, 4] while True: yield seq[0] seq.append(sum(seq)) seq.pop(0) def nth(i: Iterator[int], n: int) -> int: return list(islice(i, n, n+1))[0] def pentanacci2(n: int) -> int: return nth(pentanaccis2(), n) # Verificación # ============ def test_pentanacci() -> None: assert pentanacci1(14) == 3525 assert list(islice(pentanaccis1(), 15)) == \ [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525] assert pentanacci2(14) == 3525 assert list(islice(pentanaccis2(), 15)) == \ [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525] print("Verificado") # La verificación es # >>> test_pentanacci() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es def test_pentanacci_equiv() -> bool: return list(islice(pentanaccis1(), 25)) == list(islice(pentanaccis2(), 25)) # La comprobación es # >>> test_pentanacci_equiv() # True # Comparación de eficiencia # ========================= # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('pentanacci1(28)') # 8.24 segundos # >>> tiempo('pentanacci2(28)') # 0.00 segundos |