/*
This C program prints as quickly as possible the first n (TO_SHOW) happy numbers:
http://en.wikipedia.org/wiki/Happy_number

It needs 1/2 GB of RAM to run.
Code by leonardo maffi, V.1.0, Dec 24 2009.
*/

#include "stdio.h"
#include "stdlib.h"
#include "limits.h"

#define TO_SHOW (1*1000)


unsigned int *bit_arr;

#define BBITS       (sizeof(unsigned int) * 8)
#define BMASK(x)    (1 << ((x) % BBITS))
#define BTEST(p, x) ((p)[(x) / BBITS] & BMASK(x))
#define BFLIP(p, x) (p)[(x) / BBITS] ^= BMASK(x)

#define BLOCK \
        digit = n % 10; \
        n /= 10; \
        tot += squares[digit]; \
        if (!n) goto END;


int is_happy(unsigned int n) {
    static const unsigned int squares[11] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
    #define SEEN_LEN 100
    static unsigned int seen[SEEN_LEN];
    unsigned int n_seen = 0;

    while (!BTEST(bit_arr, n)) {
        seen[n_seen] = n;
        n_seen++;
        BFLIP(bit_arr, n);

        unsigned int tot = 0;
        unsigned int digit;

        BLOCK
        BLOCK
        BLOCK
        BLOCK
        BLOCK

        BLOCK
        BLOCK
        BLOCK
        BLOCK
        BLOCK

        END:
        n = tot;
    }

    // clear bit array
    unsigned int i;
    for (i = 0; i < n_seen; i++)
        BFLIP(bit_arr, seen[i]);

    return n == 1;
    #undef SEEN_LEN
}


int main() {
    #define DIGITS_LEN 20

    bit_arr = calloc(UINT_MAX / 8, 1);
    if (bit_arr == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }

    int n_shown = 0;
    unsigned int n = 1;
    char digits[DIGITS_LEN];
    digits[DIGITS_LEN - 1] = '\0';

    while (n_shown < TO_SHOW) {
        if (is_happy(n)) {
            unsigned int tmp = n;
            char *p = &(digits[DIGITS_LEN - 2]);
            do {
                int digit = tmp % 10;
                tmp /= 10;
                *p-- = '0' + digit;
            } while (tmp);

            puts(p + 1);
            n_shown++;
        }

        n++;
    }

    #undef DIGITS_LEN
    return EXIT_SUCCESS;
}