1votos

Un primo, un cuadrado de un primo y un cubo de un primo en progresión aritmética. en C

por josejuan hace 6 años

5623, 6241, 6859 es lo mejor que he podido encontrar (ver notas)

El número 23, el número 25 y el número 27 son respectivamente un número primo, un cuadrado de un número primo y un cubo de un número primo. Estos tres números además están en progresión aritmética con una diferencia común igual a dos.

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
/* 
    Se pide encontrar 
 
        "p", "q" y "r" primos y "d" > 2 natural 
 
    tales que 
 
        [1] p + d = q^2 
        [2] q^2 + d = r^3 
 
    pero 
 
        [3] p + 2d = r^3 
 
    restando [1] a [3] tenemos 
 
        d = r^3 - q^2 
 
    supuesto "r", "q" > 2 el producto de impares es impar 
    y la resta de impares siempre es par, por tanto es 
 
        2 n = r^3 - q^2 
 
    no es una propiedad muy destacable, pero al menos divide 
    por dos el número de iteraciones del bucle más interno. 
 
    El algoritmo, busca sobre los cubos de primos, buscando 
    el cuadrado primo predecesor, de encontrarlo, se revisa 
    si a la distancia adecuada hay un primo. 
 
    Se codifica el cuadrado y el primo en un byte, tirando a 
    la basura 6 bits. Se pueden usar un par de bitArrays para 
    poder abarcar cuatro veces más de números. 
 
    El proceso de búsqueda es paralelizable (eg. CUDA). 
 
    En mi prueba (un solo core Pentium a 1,2 GHz) reviso los 
    primeros 1024 cubos perfectos (es decir 10^9 primos). 
 
    En mi humilde Pentium tarda 50 segundos en encontrar 
 
        5623, 6241, 6859 
 
        5623 es primo 
        79 x 79 = 6241 y 79 es primo 
        19 x 19 x 19 = 6859 y 19 es primo 
 
        6241 - 5623 = 618 
        6859 - 6241 = 618 
 
    realmente lo que tarda es la criba de eratóstenes, lo demás 
    le lleva nada. Pero es probable que existan números más 
    próximos cuanto más grandes se hace y que el problema sea 
    difícil (y no fácil). 
 
    Aunque igual hay alguna propiedad por ahí... 
 
*/ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
 
#define MAXQ 32                // máx núms a rastrear 
#define MAXC (MAXQ * MAXQ)        // máximo primo que es elevado al cubo 
#define MAX2 (MAXQ * MAXQ * MAXQ)    // máximo primo que es elevado al cuadrado 
#define MAXP (MAXC * MAXC * MAXC)    // máximo primo 
 
int main(int argc, char **argv) { 
 
    uint n, z; 
    char *P = (char *) malloc(MAXP); 
    // bits 
    //    0 - primo 
    //    1 - cuadrado de primo 
 
    memset(P, 0, MAXP); 
 
    printf("Eratóstenes...\n"); 
 
    // eratóstenes 
    for(n = 2; n < MAX2; n++) 
        if(P[n] == 0) 
            for(z = n + n; z < MAXP; z += n) 
                P[z] = 1; 
 
    printf("Squares...\n"); 
 
    // cuadrados, primos 
    for(n = 2; n < MAX2; n++) 
        if((P[n] & 1) == 0) 
            P[n * n] |= 2; 
 
    printf("Searching (máx cube %i)...\n", MAXC); 
 
    // revisando diferencias entre cubos y cuadrados 
    uint mind = 1000; 
    for(n = 2; n < MAXC; n++) 
        if((P[n] & 1) == 0) { 
            uint nnn = n * n * n; // cubo de un primo 
            uint d = 4; 
            while(d < mind) { 
                uint h = nnn - d; 
                if(h <= d) 
                    break; 
                if(P[h] & 2) // cuadrado de un primo a distancia d 
                    if((P[h - d] & 1) == 0) { // primo a distancia d 
                        printf("%i, %i, %i (%i)\n", h - d, h, nnn, d); 
                        mind = d; 
                        break; 
                d += 2; 
 
    return 0; 
1 comentario
0votos

Escrito por jneira hace 6 años

+1.. también puede haber elegancia en los loops y los arrays

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.