Menor n tal que el primo n-ésimo cumple una propiedad
Sea p(n) el n-ésimo primo y sea r el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2. Por ejemplo,
|
1 2 |
si n = 3, entonces p(3) = 5 y r = ( 4^3 + 6^3) mod (5^2) = 5 si n = 7, entonces p(7) = 17 y r = (16^7 + 18^7) mod (17^2) = 238 |
Definir la función
|
1 |
menorPR :: Integer -> Integer |
tal que (menorPR x) es el menor n tal que el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2 es mayor que x. Por ejemplo,
|
1 2 3 4 5 6 |
menorPR 100 == 5 menorPR 345 == 9 menorPR 1000 == 13 menorPR (10^9) == 7037 menorPR (10^10) == 21035 menorPR (10^12) == 191041 |
Soluciones
|
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 |
import Data.Numbers.Primes (primes) -- 1ª solución -- =========== menorPR1 :: Integer -> Integer menorPR1 x = head [n | (n,p) <- zip [1..] primes , (((p-1)^n + (p+1)^n) `mod` (p^2)) > x] -- Segunda solución (usando el binomio de Newton) -- ============================================== -- Desarrollando por el binomio de Newton -- (p+1)^n = C(n,0)p^n + C(n,1)p^(n-1) +...+ C(n,n-1)p + 1 -- (p-1)^n = C(n,0)p^n - C(n,1)p^(n-1) +...+ C(n,n-1)p + (-1)^n -- Sumando se obtiene (según n sea par o impar) -- 2*C(n,0)p^n + 2*C(n,n-2)p^(n-1) +...+ 2*C(n,2)p^2 + 2 -- 2*C(n,0)p^n + 2*C(n,n-2)p^(n-1) +...+ 2*C(n,1)p^1 -- Al dividir por p^2, el resto es (según n sea par o impar) 2 ó 2*C(n,1)p -- (restoM n p) es el resto de de dividir (p-1)^n + (p+1)^n por p^2. restoM :: Integer -> Integer -> Integer restoM n p | even n = 2 | otherwise = 2*n*p `mod`(p^2) menorPR2 :: Integer -> Integer menorPR2 x = head [n | (n,p) <- zip [1..] primes, restoM n p > x] -- Comparación de eficiencia -- ghci> menorPR1 (3*10^8) -- 3987 -- (2.44 secs, 120291676 bytes) -- ghci> menorPR2 (3*10^8) -- 3987 -- (0.04 secs, 8073900 bytes) |