0votos

Números sociables (en C# de preferencia de lo contrario cualquier lenguaje) en C

por josejuan hace 3 años

Con una pequeña modificación de mi solución de búsqueda en rango de amigos se pueden obtener todos los ciclos (por comodidad aquí limitados a cierta cota). En la solución se obvian los amigos (por ser muchos). Por debajo de 10^9 sólo hay unos pocos de ciclo 4 y uno sólo de ciclo 5.

Para resolver este problema de preferencia es mejor hacer primero el de los números amigos, del cual ya hay un desafio en esta página.

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
#include <stdio.h>  
#include <stdlib.h>  
 
int main(int argc, char **argv) {  
  
  int h = atoi(argv[1])  // hilos 
    , N = atoi(argv[2])  // hasta N 
    , maxc = atoi(argv[3]); 
  
  { // cota superior múltiplo del doble de hilos  
    int r = N % h;  
    if(r != 0) N += h - r;  
  }  
  
  int z, i, S = N / h, *q = (int *) malloc(sizeof(int) * (N + 1));  
  
  // del 1 al 12 hay un ciclo de tamaño 27720 (puede generalizarse haciendo "foldl lcm 1 [2..n]")  
 // mc = 12 -> sc = 27720  
#define MC 18  
#define SC 12252240 // foldl lcm 1 [2..MC]  
  int * r = (int *) malloc(sizeof(int) * SC);  
  for(z = 0; z < SC; z++) r[z] = 1;  
  for(z = 2; z <= MC; z++) for(i = z; i <= SC; i+=z) r[i - 1] += z;  
  
  // aplicamos todo (también paralelizable)  
  #pragma omp parallel for  
  for(z = 1; z <= N; z++) q[z] = r[(z - 1) % SC];  
  
  #pragma omp parallel for  
  for(z = 1; z <= MC; z++) q[z] -= z;  
  
  // cada hilo actualiza su rango  
  #pragma omp parallel for  
  for(z = 0; z < h; z++) {  
    int i = 1, j = z * S + 1, k = j + S - 1, jm = j >> 1, km = k >> 1;  
    // si es menor que MC ya está hecho  
    if(i <= MC) i = MC + 1;  
    for(; i < jm; i++ ) {  
      int jr = j % i, u = j;  
      if(jr != 0) u += i - jr;  
      if(u == j) u += i;  
      while(u <= k) { q [u] += i; u += i; }  
    }  
    for(; i <= km; i++ ) {  
      int u = i + i;  
      while(u <= k) { q [u] += i; u += i; }  
    }  
  }  
  
  for(i = 1; i <= N; i++) { 
    // único cambio respecto de la solución de amigables anterior (en otro desafío) 
    int p = i, c = 1; 
    for(;c < maxc;) { 
      if(q[p] <= N && q[p] > i) { 
        p = q[p]; 
        c += 1; 
      } else if(q[p] == i && c > 2) { // ignoramos los amigos pero estarían aquí 
        printf("size %i: ", c); 
        for(p = i, z = 1; z < c; z++, p = q[p]) 
          printf("%i, ", p);  
        printf("%i\n", p);  
        break; 
      } else { 
        break; 
   
  
  return 0;  
 
 
/* 
 
  $ gcc -O3 -fopenmp namigos.c -o namigos 
  $ [josejuan@centella Solveet]$ crono ./namigos 6 1000000000 10 
  size 5: 12496, 14288, 15472, 14536, 14264 
  size 4: 1264460, 1547860, 1727636, 1305184 
  size 4: 2115324, 3317740, 3649556, 2797612 
  size 4: 2784580, 3265940, 3707572, 3370604 
  size 4: 4938136, 5753864, 5504056, 5423384 
  size 4: 7169104, 7538660, 8292568, 7520432 
  size 4: 18048976, 20100368, 18914992, 19252208 
  size 4: 18656380, 20522060, 28630036, 24289964 
  size 4: 28158165, 29902635, 30853845, 29971755 
  size 4: 46722700, 56833172, 53718220, 59090084 
  size 4: 81128632, 91314968, 96389032, 91401368 
  size 4: 174277820, 205718020, 262372988, 210967684 
  size 4: 209524210, 246667790, 231439570, 230143790 
  size 4: 330003580, 363003980, 399304420, 440004764 
  size 4: 498215416, 506040584, 583014136, 510137384 
  Mem: 3956160 kbytes. Time: 3:17.14 
 
 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.