This Is Why We Code

I think there is some optimizations you can do, first the obvious : you compute phi 4 times for each value, you should store the previous results in 2 variables, then phi should compute faster by using the primes factors of $n$ , as you have to test divisibility $\sqrt{n}$ times in the worst case, instead of computing n times the gcd. The formula tu use is $\phi (n) = \sum (p - 1)p^{i - 1}$ where p are primes factors of n and i their power.

I have come with two algorithms using this formula and storing the previous value of $\phi$ The first one use this fact : if p divide n then $\boxed{ \phi (n) = (p - \delta) \phi (n / p) }$ where $\delta$ is 1 if p doesn't divide n / p, else 0.

 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

#include <stdio.h>
#include <stdlib.h>
#define U unsigned
#define SIZE 100000003
typedef U long big;

big     *euler_list;

big     phi(big n)
{
    big p;
    div_t   rq;

    if ((n & 1) == 0)
        return euler_list[n >> 1] * (1 + ((n & 2) == 0));
    p = 3;
    while (p * p <= n)
    {
        rq = div(n, p);
        if (rq.rem == 0)
            return euler_list[rq.quot] * (p - (rq.quot % p != 0));
        p += 2;
    }
    return n - 1;
}           

int     main()
{
    big *end;
    big *ph;
    big n = 2;

    euler_list = malloc(SIZE * sizeof(*euler_list));
    euler_list[1] = 1;
    ph = euler_list + n;
    end = euler_list + SIZE;
    while (ph < end)
    {
            *ph = phi(n);
        if (*ph == *(ph - 1) && *(ph - 1) == *(ph - 2))
            printf("a = %ld\n", n - 2);
        //printf("phi[%lld] = %lld\n", n, *ph);
        ph++;
        n++;
    }
    return 0;
}

Another method is to fill the array by multiplying each multiple of a prime p by p - 1 and multiplying by p each multiple of a power $\geq 2$ . This is faster because we travel the array in simple and predictable way, there is no cache miss nor division test. The p values are found when a 1 is encountered in the array (meaning p is not multiple of a previous prime hence p is prime)

 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

#include <stdio.h>
#include <stdlib.h>
#define U unsigned
#define SIZE 100000003
typedef U long  big;


int     main()
{
    big *euler_list;
    big n;
    big k;
    big km;
    big m;

    n = SIZE;
    euler_list = malloc(SIZE * sizeof(*euler_list));
    while (n--)
        euler_list[n] = 1;

    n = 2;
    do
    {
        k = n;
        m = n - 1;
        while (k < SIZE)
        {
            km = 0;
            while ((km += k) < SIZE)
                euler_list[km] *= m;
            m = n;
            k *= n;
        }
        do {
//          printf("phi[%ld] = %ld\n", n, euler_list[n]);
            if ( euler_list[n] == euler_list[n - 1]
            && euler_list[n] == euler_list[n - 2] && n != 2)
                printf("a = %ld\n", n - 2);
            n++;
        } while (n < SIZE && euler_list[n] != 1);
    } while (n < SIZE);
    return 0;
}

As nobody has 80 Gigabytes of ram, we cannot compute the full $10^{10}$ using 64 bits integers. But by storing the primes $\leq 10^{5}$ and their power $\leq 10^{10}$ , and using chunks of 1000000 integer, we can construct $\phi$ and reconstruct the n's by using the previous code. We reconstruct the n's as if they have not been fully reconstructed, let say $m \le n$ , we know that $n / m$ must be a prime outside the list, and we finish $phi$ construction by multiplying by $n / m - 1$

Yes, I may have overthink this one :)