0votos

numeros amigos en Haskell

por josejuan hace 5 años

La estrategia difiere si se quieren comparar dos números cualesquiera o si se quieren obtener listas de parejas de amigos. Aquí sólo una función (bastante trivial) que calcula las series de potencias de la factorización de cada número. Aun así, corre bastante rápido. Para obtener listas de amigos (consecutivos), se pueden cachear las sumas parciales de las series de potencias (de cada primo).

Escribir una función que determine si dos números dados son amigos:

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
-- La mejor solución difiere si se quieren comparar dos amigos 
-- arbitrarios o se quieren encontrar muchos amigos. 
 
-- Si sólo se desea saber si *DOS* números son o no amigos, 
-- parece fácil hacer una comparación directa 
amigos a b = amidivs a == b &&      -- Son amigos si la suma de divisores (menos él) 
             a == amidivs b         -- es igual al otro número y al revés. 
 
 
-- La suma de divisores menos él 
amidivs n = sumdivs n - n 
 
 
-- Para sumar los divisores se ve fácilmente que una forma rápida 
-- a partir de los factores primos es 
sumdivs = product . map f . group . primeFactors 
          where f xs@(x:_) = (x^(1 + length xs) - 1) `div` (x - 1) 
 
-- Y ya está. 
 
{- 
    `sumdivs` viene del hecho de que, por ejemplo, si es 
 
        N = 2^2 3^1 5^2 
 
    Las sumas las podemos ir agrupando así 
     
        2^0 3^0 5^0 
        2^0 3^0 5^1 
        2^0 3^0 5^2 
            2^0 3^0 (5^0 + 5^1 + 5^2) 
        2^0 3^1 5^0 
        2^0 3^1 5^1 
        2^0 3^1 5^2 
            2^0 3^1 (5^0 + 5^1 + 5^2) 
                2^0 (3^0 + 3^1) (5^0 + 5^1 + 5^2) 
        2^1 3^0 5^0 
        2^1 3^0 5^1 
        2^1 3^0 5^2 
            2^1 3^0 (5^0 + 5^1 + 5^2) 
        2^1 3^1 5^0 
        2^1 3^1 5^1 
        2^1 3^1 5^2 
            2^1 3^1 (5^0 + 5^1 + 5^2) 
                2^1 (3^0 + 3^1) (5^0 + 5^1 + 5^2) 
 
    Es decir, TODOS los divisores suman 
     
        (p1^0 + p1^1 + ... + p1^n1) * 
        (p2^0 + p2^1 + ... + p2^n2) * 
            ... 
        (pZ^0 + pZ^1 + ... + pZ^nZ) 
     
    y cada sumando es una serie de potencias con suma 
     
        (pI^(nI + 1) - 1) / (pI - 1) 
 
-} 
 
 
 
-- Por otro lado, seguro que existen propiedades adicionales 
-- que permiten acelerar (en media) el chequeo de propiedades. 
 
-- Por ejemplo, parece que la distancia entre dos números amigos 
-- está acotada por su valor, lo que quiere decir que para 
-- amigos MUY distantes, se podría asegurar que NO son amigos. 
 
{- 
    Para calcular muchos números amigos, lo mejor será utilizar 
    algún tipo de caché para resultados (ej. cálculo de sumas 
    de potencias será más rápido al acumular la siguiente potencia 
    de cada primo que calcular la serie cada vez, porque lo primero 
    requiere una multiplicación y una suma, mientras que lo segundo 
    requiere 3 sumas, una exponenciación y una división. 
     
    De todos modos, se puede usar la misma función así: 
-} 
amigable a = if b > a && amidivs b == a 
                then Just (a, b) 
                else Nothing 
             where b = amidivs a 
 
 
 
 
 
 
 
 
 
-- Un ejemplo completo paralelizado podría ser: 
import System.Environment 
import Data.Numbers.Primes (primeFactors) 
import Data.List 
import System.Clock 
import Control.Concurrent.ParallelIO 
import Data.Maybe 
 
sumdivs :: Integer -> Integer 
sumdivs = product . map f . group . primeFactors 
          where f xs@(x:_) = (x^(1 + length xs) - 1) `div` (x - 1) 
 
amidivs n = sumdivs n - n 
 
amigos a b = amidivs a == b && a == amidivs b 
 
amigable a = if b > a && amidivs b == a 
                then Just (a, b) 
                else Nothing 
             where b = amidivs a 
 
 
diffTime :: TimeSpec -> TimeSpec -> Double 
diffTime a b = t b - t a  
  where t z = fromIntegral (sec z) + 1e-9 * fromIntegral (nsec z)  
 
printTime :: String -> TimeSpec -> TimeSpec -> IO ()  
printTime msg a b = putStrLn $ msg ++ show (diffTime a b)  
 
escribirAmigos :: Integer -> Integer -> IO () 
escribirAmigos a b = (mapM_ print . catMaybes . map amigable) [a..b] 
 
main = do 
    (n: -- hasta que número buscar amigos 
     s: -- en cuantos hilos dividir el trabajo 
     _) <- getArgs >>= return . map read 
    t0 <- getTime Realtime 
    let w = n `div` s 
    parallel_ $ map (uncurry escribirAmigos) [((k - 1) * w, k * w) | k <- [1..s]] 
    t1 <- getTime Realtime 
    printTime "tiempo: " t0 t1 
 
 
{- 
 
Por ejemplo, obtener las primeras 183 parejas de amigos usando 8 cores toma 94 segundos. 
    **pero si quieres calcular listas de amigos lo mejor es cachear potencias !!!** 
 
(0,1) 
(220,284) 
(1184,1210) 
(2620,2924) 
(5020,5564) 
(6232,6368) 
(10744,10856) 
(12285,14595) 
(15002464,15334304) 
(17296,18416) 
(63020,76084) 
(66928,66992) 
(67095,71145) 
(69615,87633) 
(20014808,21457192) 
(79750,88730) 
(100485,124155) 
(20022328,22823432) 
(122265,139815) 
(122368,123152) 
(141664,153176) 
(142310,168730) 
(171856,176336) 
(176272,180848) 
(185368,203432) 
(196724,202444) 
(280540,365084) 
(308620,389924) 
(319550,430402) 
(5123090,5504110) 
(356408,399592) 
(5147032,5843048) 
(437456,455344) 
(469028,486178) 
(503056,514736) 
(35115795,43266285) 
(522405,525915) 
(5232010,5799542) 
(600392,669688) 
(609928,686072) 
(624184,691256) 
(635624,712216) 
(643336,652664) 
(667964,783556) 
(10254970,10273670) 
(726104,796696) 
(5357625,5684679) 
(802725,863835) 
(5385310,5812130) 
(879712,901424) 
(898216,980984) 
(5459176,5495264) 
(947835,1125765) 
(20308995,20955645) 
(998104,1043096) 
(15363832,16517768) 
(1077890,1099390) 
(1154450,1189150) 
(1156870,1292570) 
(1175265,1438983) 
(1185376,1286744) 
(10533296,10949704) 
(35361326,40117714) 
(1280565,1340235) 
(35373195,40105845) 
(10572550,10854650) 
(1328470,1483850) 
(35390008,39259592) 
(1358595,1486845) 
(5726072,6369928) 
(10596368,11199112) 
(5730615,6088905) 
(1392368,1464592) 
(10634085,14084763) 
(1466150,1747930) 
(1468324,1749212) 
(1511930,1598470) 
(35472592,36415664) 
(5864660,7489324) 
(1669910,2062570) 
(25596544,25640096) 
(1798875,1870245) 
(10992735,12070305) 
(2082464,2090656) 
(30724694,32174506) 
(15938055,17308665) 
(6329416,6371384) 
(2236570,2429030) 
(6377175,6680025) 
(11173460,13212076) 
(30830696,31652704) 
(11252648,12101272) 
(25966832,26529808) 
(16137628,16150628) 
(2652728,2941672) 
(2723792,2874064) 
(2728726,3077354) 
(2739704,2928136) 
(26090325,26138475) 
(2802416,2947216) 
(2803580,3716164) 
(11498355,12024045) 
(11545616,12247504) 
(6955216,7418864) 
(6993610,7158710) 
(11693290,12361622) 
(3276856,3721544) 
(21448630,23030090) 
(7275532,7471508) 
(11905504,13337336) 
(7288930,8221598) 
(3606850,3892670) 
(7489112,7674088) 
(16871582,19325698) 
(3786904,4300136) 
(3805264,4006736) 
(31536855,32148585) 
(7577350,8493050) 
(7677248,7684672) 
(17041010,19150222) 
(7800544,7916696) 
(7850512,8052488) 
(12397552,13136528) 
(4238984,4314616) 
(4246130,4488910) 
(4259750,4445050) 
(17257695,17578785) 
(31818952,34860248) 
(4482765,5120595) 
(4532710,6135962) 
(12707704,14236136) 
(4604776,5162744) 
(22227075,24644925) 
(22249552,25325528) 
(8262136,8369864) 
(22508145,23111055) 
(32205616,34352624) 
(8619765,9627915) 
(17754165,19985355) 
(8666860,10638356) 
(22608632,25775368) 
(17844255,19895265) 
(8754130,10893230) 
(8826070,10043690) 
(17908064,18017056) 
(18056312,18166888) 
(37363095,45663849) 
(9071685,9498555) 
(18194715,22240485) 
(9199496,9592504) 
(9206925,10791795) 
(32642324,35095276) 
(13671735,15877065) 
(9339704,9892936) 
(32685250,34538270) 
(9363584,9437056) 
(9478910,11049730) 
(13813150,14310050) 
(9491625,10950615) 
(13921528,13985672) 
(9660950,10025290) 
(37784810,39944086) 
(28118032,28128368) 
(23358248,25233112) 
(9773505,11791935) 
(18655744,19154336) 
(23389695,25132545) 
(37848915,39202605) 
(14311688,14718712) 
(23628940,27428276) 
(14426230,18087818) 
(14443730,15882670) 
(28608424,29603576) 
(14654150,16817050) 
(33501825,36136575) 
(38400512,38938288) 
(38637016,40678184) 
(38663950,43362050) 
(38783992,41654408) 
(24472180,30395276) 
(38807968,40912232) 
(34256222,35997346) 
(34364912,34380688) 
(34765731,36939357) 
tiempo: 94.02136509993579 
 
-} 
3 comentarios
0votos

Escrito por Seba_lujan hace 5 años

Excelente solucion!!
Muy optimizada creo es mas que la mia, con la obtencion de factores primos acotas mas aun el conj de operaciones!
¿Podrias expliar un poco la solucion paralelizada?
0votos

Escrito por josejuan hace 5 años

Hola Sebas,

la paralelización se basa en que, dado un número n, sólo puede ser amigable con su suma de divisores (excepto él), es decir, la función amigable toma un n, calcula su quizás amigo m y luego mira si éste m es también amigo de n. Como este cálculo sólo depende de n, se divide el rango de números a obtener entre el número de hilos y símplemente se ejecutan en paralelo. No se si es ésto lo que querías que explicara.

Un saludo!
0votos

Escrito por Seba_lujan hace 5 años

Excelente solucion!!
Muy optimizada creo es mas que la mia, con la obtencion de factores primos acotas mas aun el conj de operaciones!
¿Podrias expliar un poco la solucion paralelizada?

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.