/* 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; }