0votos

Número apocalíptico. (con recursividad en cualquier lenguaje) en C

por josejuan hace 4 años

Se pueden hacer unas cuentas mejoras, pero así va bien. Hasta N=1.000 en 0,00078 segundos. A partir de 29.785 son todos apocalípticos hasta 1.000.000 (usando 9 minutos) ¿cual será el siguiente *NO* apocalíptico? :D

Todo numero natural n que cumple que 2^n contiene la secuencia 666 es un numero apocalíptico. Los primeros números apocalípticos son 157 192, 218, 220, 222, …., etc, ya que 2^157 = 182687704666362864775460604089535377456991567872

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
#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <time.h> 
#include <sys/time.h> 
 
void apocalipticos(int maxN, int mostrarPotencia) { 
    int maxD = (int) ceil(maxN * 0.30103); 
    int n = 9, maxi = 2; 
    char *d = (char *) malloc(maxD); 
    { int i; for(i = 3; i < maxD; i++) d[i] = 0; d[0] = 2; d[1] = 1; d[2] = 5; } 
    char sd [] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    char sc [] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; 
    char mx [] = {0, 0, 0, 0, 0, 0, 7, 0, 0, 0}; 
    while(++n <= maxN) { 
        char carry = 0; 
        int i; 
        char apoca = 0; 
        char counter = 1; 
        for(i = 0; i <= maxi; i++) { 
            char ss = (d[i] << 1) + carry; 
            char digit = sd[ss]; 
            carry = sc[ss]; 
            d[i] = digit; 
            counter = (mx[digit] & counter) + 1; 
            apoca |= counter & 4; 
        if(carry > 0) 
            d[++maxi] = carry; 
        if(apoca) { 
            printf("%i\n", n); 
            if(mostrarPotencia) { 
                int i; for(i = maxi; i >= 0; i--) putchar('0' + d[i]); putchar('\n'); 
 
int main(int argc, char **argv) { 
    struct timespec t1, t2; 
    clock_gettime(CLOCK_MONOTONIC,  &t1); 
    apocalipticos(atoi(argv[1]), atoi(argv[2])); 
    clock_gettime(CLOCK_MONOTONIC,  &t2); 
    double t = (t2.tv_sec - t1.tv_sec) + (double) (t2.tv_nsec - t1.tv_nsec) * 1e-9; 
    fprintf(stderr, "Seconds: %f\n", t); 
    return 0; 
 
 
/* NOTA: 
 *      Haciendo una pequeña modificación, se puede mejorar para buscar los NO apocalípticos 
        for(i = 0; i <= maxi && !apoca; i++) {              <<< CHANGE 
            ... 
        for(; i <= maxi; i++) {                             <<< ADD 
            char ss = (d[i] << 1) + carry;                  <<< ADD 
            char digit = sd[ss];                            <<< ADD 
            carry = sc[ss];                                 <<< ADD 
            d[i] = digit;                                   <<< ADD 
        ... 
        if(!apoca) {                                        <<< CHANGE 
 *      Los tiempos (en segundos) vienen a ser (ajustadas las constantes a mi equipo) 
 *              P[x] = 0.0548722424 * (x * 1e-4)^2 + 0.0595877576 * (x * 1e-4) - 0.0211114 
 *      Los últimos *NO* apocalípticos cuando buscamos hasta N = 1.000.000 son 
                [josejuan@centella Solveet]$ ./a.out 1000000 0 | tail 
                Seconds: 551.440500 
                23097 
                23253 
                24422 
                24441 
                25026 
                25357 
                25896 
                26051 
                26667 
                29784 
 *      Es decir, desde el 29.785 hasta el 1.000.000 todos son apocalípticos ¡¿serán todos apocalípticos?! 
 *      ¿cuando será el siguiente *NO* apocalíptico?. 
 */ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.