/*
Calculate terms for OEIS sequence A217166: a(n) is the least value of k such
that the decimal expansion of Lucas(k) contains n consecutive identical digits.
This program prints a table, with rows 'n k', for 2 <= lower_k <= k < upper_k.
The program can be run multiple times, for increasing ranges of k, and the
outputs concatenated into a single table.
Compile on Linux as, e.g.: clang -O3 -o a217166 a217166.c -lgmp -lm
Invoke on Linux as, e.g.: ./a217166 2 1000000 1
where the first two parameters are, respectively, lower and upper bounds
for k, and the third parameter is the greatest number of repeated digits found
so far; i.e., for k < lower_k.
Created by Nick Hobson (n@nickhobson.com), Feb 02, 2024.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <math.h>
#include <gmp.h>
#include <assert.h>

// uint8_t, uint32_t, or even uint64_t might be faster on some machines.
typedef uint16_t uint_T;

// Decimal digits are held in 'digit'. Element 0 holds a non-digit sentinel
// value. The number itself is held in elements 1 thru digit_count, with
// the least significant digit in element 1. (Using 'super-digits', to a base
// of a higher power of 10, would probably yield a modest performance
// improvement.)
struct num {
    size_t digit_count;
    uint_T *digit;
};

// Get two consecutive Lucas numbers using GMP. Convert to strings and load
// digits into rop1 and rop2.
static void nums_set_init(struct num *rop1, struct num *rop2,
                          const size_t max_digit_count, const unsigned long k)
{
    rop1->digit = calloc(max_digit_count, sizeof(*(rop1->digit)));
    rop2->digit = calloc(max_digit_count, sizeof(*(rop2->digit)));
    if (!rop1->digit || !rop2->digit) {
        fprintf(stderr, "Cannot allocate %zu elements of size %zu.\n",
                max_digit_count, sizeof(*(rop1->digit)));
        exit(EXIT_FAILURE);
    }

    mpz_t lk, lksub1;
    mpz_inits(lk, lksub1, NULL);
    mpz_lucnum2_ui(lk, lksub1, k);

    rop1->digit[0] = 10;  // Sentinel
    char *p = mpz_get_str(NULL, 10, lksub1);
    rop1->digit_count = strlen(p);
    for (size_t d = 0; d < rop1->digit_count; d++) {
        rop1->digit[rop1->digit_count - d] = p[d] - '0';
    }
    free(p);

    rop2->digit[0] = 10;  // Sentinel
    p = mpz_get_str(NULL, 10, lk);
    rop2->digit_count = strlen(p);
    for (size_t d = 0; d < rop2->digit_count; d++) {
        rop2->digit[rop2->digit_count - d] = p[d] - '0';
    }
    free(p);

    mpz_clears(lk, lksub1, NULL);
}

// Do rop += op, returning longest number of consecutive identical digits found
// in the updated value of rop.
static inline uint32_t num_iadd(struct num *rop, const struct num *op)
{
    uint32_t rep = 1, max_rep = 1;
    uint_T carry = 0;
    for (size_t d = 1; d < rop->digit_count + 2; d++) {
        rop->digit[d] += op->digit[d] + carry;
        if (rop->digit[d] < 10) {
            carry = 0;
        } else {
            rop->digit[d] -= 10;
            carry = 1;
        }
        // Check for repeating digits.
        if (rop->digit[d - 1] != rop->digit[d]) {
            rep = 1;
        } else {
            if (++rep > max_rep) {
                max_rep = rep;
            }
        }
    }
    assert(carry == 0);
    if (rop->digit[rop->digit_count + 1] != 0) {
        rop->digit_count += 1;
    }
    return max_rep;
}

int main(int argc, char *argv[])
{
    // Ensure stdout is line buffered even when redirected to a file.
    setvbuf(stdout, NULL, _IOLBF, 256);

    // No validation for input parameters, which should be integers.
    unsigned long lower_k = (argc > 1) ? strtoul(argv[1], NULL, 10) : 2;
    const unsigned long upper_k =
        (argc > 2) ? strtoul(argv[2], NULL, 10) : 400000;
    uint32_t max_rep = (uint32_t)((argc > 3) ? strtoul(argv[3], NULL, 10) : 1);
    if (lower_k < 2) {
        if (lower_k == 0) {
            puts("1 0");
        }
        lower_k = 2;
        max_rep = 1;
    }

    const long double phi = (1 + sqrtl(5)) / 2;
    const size_t max_digit_count = (size_t)(log10l(phi) * (upper_k + 1)) + 3;

    struct num a, b;
    // Initialise a, b to consecutive Lucas numbers L(lower_k - 2) and
    // L(lower_k - 1), respectively.
    unsigned long k = lower_k;
    nums_set_init(&a, &b, max_digit_count, k - 1);

    uint32_t loops = 0;
    while (k < upper_k) {
        uint32_t rep = num_iadd(&a, &b);
        while (max_rep < rep) {
            max_rep++;
            printf("%" PRIu32 " %lu\n", max_rep, k);
        }
        k++;
        rep = num_iadd(&b, &a);
        while (max_rep < rep) {
            max_rep++;
            if (k < upper_k) {
                printf("%" PRIu32 " %lu\n", max_rep, k);
            }
        }
        k++;
        // Report progress every 2^18 = 262,144 numbers checked.
        if (!(loops += (1U << 15))) {
            fprintf(stderr, "Reached: %lu\n", k - 1);
        }
    }
    free(b.digit);
    free(a.digit);

    return EXIT_SUCCESS;
}