A072841

A072841.c

/* https://oeis.org/A072841
 * This is free and unencumbered software released into the public domain.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAX(a, b) ((b) > (a) ? (b) : (a))

typedef struct bigint {
    size_t size;
    size_t fill;
    unsigned char v[];
} bigint;

bigint *
bigint_create(const char *s)
{
    size_t fill = s == NULL ? 0 : strlen(s);
    size_t size = MAX(fill, 256);
    bigint *b = malloc(sizeof(*b) + sizeof(b->v[0]) * fill);
    b->size = size;
    b->fill = fill;
    for (size_t i = 0; i < b->fill; i++)
        b->v[i] = s[b->fill - i - 1] - '0';
    return b;
}

static inline void
bigint_swap(bigint **a, bigint **b)
{
    bigint *swap = *a;
    *a = *b;
    *b = swap;
}

void
bigint_grow(bigint **b, size_t target)
{
    if ((*b)->size < target) {
        size_t new_size = (*b)->size * 2;
        while (new_size < target)
            new_size *= 2;
        *b = realloc(*b, sizeof(**b) + sizeof((*b)->v[0]) * new_size);
        (*b)->size = new_size;
    }
}

static inline void
bigint_free(bigint *b)
{
    free(b);
}

static inline void
bigint_clear(bigint *b)
{
    b->fill = 0;
}

static inline void
bigint_set(bigint **b, size_t i, unsigned char v)
{
    bigint_grow(b, i + 1);
    (*b)->v[i] = v;
    (*b)->fill = MAX((*b)->fill, i + 1);
}

static inline unsigned char
bigint_get(const bigint *b, size_t i)
{
    return i >= b->fill ? 0 : b->v[i];
}

static inline void
bigint_fixup(bigint *b)
{
    while (b->fill > 0 && b->v[b->fill - 1] == 0)
        b->fill--;
}

void
bigint_print(bigint *b, FILE *o)
{
    if (b->fill == 0)
        putchar('0');
    else
        for (long i = (long) b->fill - 1; i >= 0; i--)
            fputc(b->v[i] + '0', o);
    fputc('\n', o);
}

void
bigint_add(bigint **dst, bigint *a, bigint *b)
{
    assert(*dst != a);
    assert(*dst != b);
    bigint_clear(*dst);
    unsigned carry = 0;
    for (size_t i = 0; i < MAX(a->fill, b->fill) || carry > 0; i++) {
        carry += bigint_get(a, i) + bigint_get(b, i);
        bigint_set(dst, i, carry % 10);
        carry /= 10;
    }
    bigint_fixup(*dst);
}

void
bigint_mul(bigint **dst, bigint *a, bigint *b)
{
    assert(*dst != a);
    assert(*dst != b);
    if (b->fill < a->fill)
        bigint_swap(&a, &b);
    bigint_clear(*dst);
    for (size_t ai = 0; ai < a->fill; ai++) {
        unsigned carry = 0;
        for (size_t bi = 0; bi < b->fill; bi++) {
            unsigned char orig = bigint_get(*dst, bi + ai);
            unsigned result = a->v[ai] * b->v[bi] + carry + orig;
            bigint_set(dst, ai + bi, result % 10);
            carry = result / 10;
            for (size_t c = 1; carry > 0; c++) {
                carry += bigint_get(*dst, ai + bi + c);
                bigint_set(dst, ai + bi + c, carry % 10);
                carry /= 10;
            }
        }
    }
    bigint_fixup(*dst);
}

int
bigint_is_anagram(const bigint *a, const bigint *b)
{
    if (a->fill != b->fill)
        return 0;
    unsigned count_a[10] = {0};
    unsigned count_b[10] = {0};
    for (size_t i = 0; i < a->fill; i++)
        count_a[a->v[i]]++;
    for (size_t i = 0; i < b->fill; i++)
        count_b[b->v[i]]++;
    return memcmp(count_a, count_b, sizeof(count_a)) == 0;
}

int
main(void)
{
    bigint *c_1 = bigint_create("1");
    bigint *c_4 = bigint_create("4");
    bigint *c_9 = bigint_create("9");
    bigint *i = bigint_create("0");
    bigint *x = bigint_create(NULL);
    bigint *x2 = bigint_create(NULL);
    bigint *xp2 = bigint_create(NULL);
    bigint *tmp = bigint_create(NULL);
    for (;;) {
        bigint_add(&tmp, i, c_1);
        bigint_swap(&tmp, &i);
        bigint_mul(&x, i, c_9);
        bigint_add(&tmp, x, c_4);
        bigint_swap(&tmp, &x);
        bigint_add(&xp2, x, c_1);
        bigint_mul(&x2, x, x);
        bigint_mul(&tmp, xp2, xp2);
        bigint_swap(&tmp, &xp2);
        if (bigint_is_anagram(x2, xp2))
            bigint_print(x, stdout);
    }
    return 0;
}