0votos

Capi 2 Capi 10 en Haskell

por josejuan hace 3 años

No conozco ninguna propiedad que permita relacionar los capicúas en base 2 y base 10 por lo que no veo otra que tomar los de base 10 (hay mucho menos) y checar si lo es en base 2. Así, todos los speepup serían de la constante multiplicativa y el algoritmo exponencial en el número de dígitos (lineal en el máx N a revisar).

Un número es "Capi 2 Capi 10" si es capicúa tanto en representación binaria como decimal. El desafío consisten en enumerarlos de la forma más rápida posible.

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
reverseNum :: (Read a, Show a, Integral a) ⇒ a → a 
reverseNum = read ∘ reverse ∘ show 
 
reverses :: ℤ → ℤ → [(ℤ, ℤ)] 
reverses a b = [(n, reverseNum n) | n ← [a, a+1…a+b-1]] 
 
capis2and10 :: Int → [ℤ] 
capis2and10 maxP10 = 1: 3: 5: 7: 9: 33: 99: 313: 585: 717: concat (map (g ∘ (10^)) [1…maxP10] `using` parList rdeepseq) 
  where g p = concat ([h (d × p) p | d ← [1,3,5,7,9]] `using` parList rdeepseq) 
        w n = when (isCapi2 n) $ tell [n] 
        h q p = concat $ execWriterT $ do 
                  (a, b) ← lift $ reverses q p  
                  w (a × p × 10 + b) 
                  d ← lift [0…9] 
                  w (a × p × 100 + p × 10 × d + b) 
 
isCapi2 :: ℤ → 𝔹 
isCapi2 z = let s = integerLog2' z  
            in  and [testBit z (s - i) ≡ testBit z i | i ← [1…s ÷ 2]] -- no testea LSB == MSB 
 
{- 
33 
99 
313 
585 
717 
7447 
9009 
15351 
32223 
39993 
53235 
53835 
73737 
585585 
1758571 
1934391 
1979791 
3129213 
5071705 
5259525 
5841485 
13500531 
719848917 
910373019 
939474939 
1290880921 
7451111547 
10050905001 
18462126481 
32479297423 
75015151057 
110948849011 
136525525631 
1234104014321 
1413899983141 
1474922294741 
1792704072971 
1794096904971 
1999925299991 
5652622262565 
7227526257227 
7284717174827 
9484874784849 
34141388314143 
552212535212255 
933138363831339 
1793770770773971 
3148955775598413 
10457587478575401 
10819671917691801 
18279440804497281 
34104482028440143 
37078796869787073 
37629927072992673 
55952637073625955 
161206152251602161 
313558153351855313 
7036267126217626307 
9674868723278684769 
Mem: 28308 kbytes. Time: 23:48.05 
-} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.