0votos

8 números primos en Haskell

por josejuan hace 5 meses

Los grupos hasta 6 primos se calculan instantáneamente, el grupo de 7 primos en 80 mS, el grupo de 8 primos solicitado se calcula en unos 560 mS, el grupo de 9 primos se calcula en 20 segundos y el de 10 primos no se encuentra.

Necesitas emplear algo de fuerza bruta para encontrar la solución (un numero), pero no te pases o tu algoritmo tardará horas en solucionar este problema. Se recomienda Python para solucionarlo.

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
114
115
116
117
118
119
120
import Data.Numbers.Primes 
import Data.List 
import qualified Data.Map as Map 
import System.Environment 
import System.Exit 
import Control.Applicative 
import Data.ByteString.Char8 (pack) 
 
{- 
 
  Sólo puede haber un máximo de 10 números como los indicados (uno por cada dígito). 
 
  Cuando vamos rastreando primos, podemos hacer 2^d particiones diferentes y además 
  en cada una de ellas, una de las particiones debe tener todos los dígitos iguales, 
  la otra parte, es la clave de agrupación. 
 
  Por ejemplo, dado el primo #12345 que es el 132241 está claro que ya no podemos hacer 
  particiones de 3 iguales, sólo de 1 (cualquiera) o de 2 (x3224x y 13xx41). 
 
  Así, la primera tarea que vamos a hacer es, dado un primo, sacar sus claves de tamaño 
  al menos K. 
 
  Para que tenga tamaño K, sólo nos sirven aquellos dígitos que se repitan al menos K 
  veces. Una vez esos grupos de dígitos, tomaremos todas las combinaciones de K en K que 
  podamos y ya las tendremos. 
 
-} 
 
clavesK :: Int ->Int ->[(String, Int)] 
clavesK k p = [(xx ds 0 is, p) | is <-xs] 
  where ds = show p 
        xs = concat [(filter ((k<=) . length) . subsequences) [i | (i, q) <-zip [(0::Int)..] ds, q == d] | d <-['0'..'9']] 
        xx    []  _         _              = [] 
        xx    xs  _        []              = xs 
        xx (x:xs) j iss@(i:is) | j < i     =  x : xx xs (j + 1) iss 
                               | j == i     = 'x': xx xs (j + 1) is 
                               | otherwise = error "bug" 
 
{- 
 
  Ahora sólo se trata de ir contanto cuantos primos metemos en cada clave hasta dar 
  con alguno que tenga el tamaño buscado. 
-} 
 
buscar :: Int ->Int ->[Int] ->Maybe (String, [Int]) 
buscar k sz ps = ins Map.empty $ concatMap (clavesK k) ps 
  where ins _ [] = Nothing 
        ins m ((k,p):kps) = let z = pack k 
                                m' = Map.insertWith (++) z [p] m 
                                r  = (Map.!) m' z 
                            in  if length r >= sz then Just (k, r) else ins m' kps 
 
{- 
 
  Como los grupos deben tener el mismo número de dígitos, podemos buscar en grupos 
  de primos que comparten nº de dígitos. 
-} 
 
buscarKSZ :: Int ->Int ->Maybe  (String, [Int]) 
buscarKSZ k sz = b 1 
  where b i = buscar k sz (p10 i) <|> b (i + 1) 
 
p10 :: Int ->[Int] 
p10 p = takeWhile (<u) $ dropWhile (<v) primes 
  where v = 10^(p - 1) 
        u = 10 * v 
 
-- Y ya está. 
main = do 
  [k,sz] <-map read <$> getArgs 
  let Just r@(y, _) = buscarKSZ k sz 
  print r 
  exitWith $ ExitFailure $ length $ filter ('x'==) y 
 
{- 
 
  Podemos buscar rápidamente todos hasta de 9 primos: 
 
[josejuan@centella centella]$ stack exec -- ghc -O3 ../prim8.hs 
[1 of 1] Compiling Main             ( ../prim8.hs, ../prim8.o ) 
Linking ../prim8 ... 
[josejuan@centella centella]$ k=1; for i in `seq 1 9`; do echo "== size $i ========"; time -f "%E, %M" ../prim8 $k $i; k=$?; done 
== size 1 ======== 
("x",[2]) 
Command exited with non-zero status 1 
0:00.46, 3604 
== size 2 ======== 
("x",[3,2]) 
Command exited with non-zero status 1 
0:00.04, 3696 
== size 3 ======== 
("x",[5,3,2]) 
Command exited with non-zero status 1 
0:00.00, 3628 
== size 4 ======== 
("x",[7,5,3,2]) 
Command exited with non-zero status 1 
0:00.00, 3672 
== size 5 ======== 
("x1",[71,61,41,31,11]) 
Command exited with non-zero status 1 
0:00.00, 3692 
== size 6 ======== 
("x3",[83,73,53,43,23,13]) 
Command exited with non-zero status 1 
0:00.00, 3776 
== size 7 ======== 
("56xx3",[56993,56773,56663,56443,56333,56113,56003]) 
Command exited with non-zero status 2 
0:00.08, 10952 
== size 8 ======== 
("x2x3x3",[929393,828383,626363,525353,424343,323333,222323,121313]) 
Command exited with non-zero status 3 
0:00.56, 35008 
== size 9 ======== 
("38x0x2x1",[38909291,38808281,38707271,38606261,38505251,38303231,38202221,38101211,38000201]) 
Command exited with non-zero status 3 
0:20.47, 660556 
 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.