Definitions

As used here, all unprimeable numbers   (positive integers)   are always expressed in base ten.



───── Definition from OEIS ─────:

Unprimeable numbers are composite numbers that always remain composite when a single decimal digit of the number is changed.



───── Definition from Wiktionary   (referenced from Adam Spencer's book) ─────:

(arithmetic)   that cannot be turned into a prime number by changing just one of its digits to any other
digit.   (sic)



Unprimeable numbers are also spelled:   unprimable.

All one─ and two─digit numbers can be turned into primes by changing a single decimal digit.



Examples

190   isn't unprimeable,   because by changing the zero digit into a three yields   193,   which is a prime.



The number   200   is unprimeable,   since none of the numbers   201, 202, 203, ··· 209   are
prime, and all the other numbers obtained by changing a single digit to
produce   100, 300, 400, ··· 900,   or   210, 220, 230, ··· 290   which are all even.



It is valid to change   189   into   089   by changing the   1   (one)   into
a   0   (zero),   which then the leading zero can be removed,   and then treated as if
the   "new"   number is   89.



Task

   show the first   35   unprimeable numbers   (horizontally, on one line, preferably with a title)
   show the   600th   unprimeable number
   (optional) show the lowest unprimeable number ending in a specific decimal digit   (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
   (optional) use commas in the numbers where appropriate


Show all output here, on this page.



Also see

   the     OEIS     entry:   A118118 (unprimeable)
   with some useful counts to compare unprimeable number
   the Wiktionary entry (reference from below):   (arithmetic definition) unprimeable
   from the Adam Spencer book   (page 200):   Adam Spencer's World of Numbers       (Xoum Publishing)


#include <assert.h>
#include <locale.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
typedef struct bit_array_tag {
    uint32_t size;
    uint32_t* array;
} bit_array;
 
bool bit_array_create(bit_array* b, uint32_t size) {
    uint32_t* array = calloc((size + 31)/32, sizeof(uint32_t));
    if (array == NULL)
        return false;
    b->size = size;
    b->array = array;
    return true;
}
 
void bit_array_destroy(bit_array* b) {
    free(b->array);
    b->array = NULL;
}
 
void bit_array_set(bit_array* b, uint32_t index, bool value) {
    assert(index < b->size);
    uint32_t* p = &b->array[index >> 5];
    uint32_t bit = 1 << (index & 31);
    if (value)
        *p |= bit;
    else
        *p &= ~bit;
}
 
bool bit_array_get(const bit_array* b, uint32_t index) {
    assert(index < b->size);
    uint32_t* p = &b->array[index >> 5];
    uint32_t bit = 1 << (index & 31);
    return (*p & bit) != 0;
}
 
typedef struct sieve_tag {
    uint32_t limit;
    bit_array not_prime;
} sieve;
 
bool sieve_create(sieve* s, uint32_t limit) {
    if (!bit_array_create(&s->not_prime, limit/2))
        return false;
    for (uint32_t p = 3; p * p <= limit; p += 2) {
        if (bit_array_get(&s->not_prime, p/2 - 1) == false) {
            uint32_t inc = 2 * p;
            for (uint32_t q = p * p; q <= limit; q += inc)
                bit_array_set(&s->not_prime, q/2 - 1, true);
        }
    }
    s->limit = limit;
    return true;
}
 
void sieve_destroy(sieve* s) {
    bit_array_destroy(&s->not_prime);
}
 
bool is_prime(const sieve* s, uint32_t n) {
    assert(n <= s->limit);
    if (n == 2)
        return true;
    if (n < 2 || n % 2 == 0)
        return false;
    return bit_array_get(&s->not_prime, n/2 - 1) == false;
}
 
// return number of decimal digits
uint32_t count_digits(uint32_t n) {
    uint32_t digits = 0;
    for (; n > 0; ++digits)
        n /= 10;
    return digits;
}
 
// return the number with one digit replaced
uint32_t change_digit(uint32_t n, uint32_t index, uint32_t new_digit) {
    uint32_t p = 1;
    uint32_t changed = 0;
    for (; index > 0; p *= 10, n /= 10, --index)
        changed += p * (n % 10);
    changed += (10 * (n/10) + new_digit) * p;
    return changed;
}
 
// returns true if n unprimeable
bool unprimeable(const sieve* s, uint32_t n) {
    if (is_prime(s, n))
        return false;
    uint32_t d = count_digits(n);
    for (uint32_t i = 0; i < d; ++i) {
        for (uint32_t j = 0; j <= 9; ++j) {
            uint32_t m = change_digit(n, i, j);
            if (m != n && is_prime(s, m))
                return false;
        }
    }
    return true;
}
 
int main() {
    const uint32_t limit = 10000000;
    setlocale(LC_ALL, "");
    sieve s = { 0 };
    if (!sieve_create(&s, limit)) {
        fprintf(stderr, "Out of memory\n");
        return 1;
    }
    printf("First 35 unprimeable numbers:\n");
    uint32_t n = 100;
    uint32_t lowest[10] = { 0 };
    for (uint32_t count = 0, found = 0; n < limit && (found < 10 || count < 600); ++n) {
        if (unprimeable(&s, n)) {
            if (count < 35) {
                if (count != 0)
                    printf(", ");
                printf("%'u", n);
            }
            ++count;
            if (count == 600)
                printf("\n600th unprimeable number: %'u\n", n);
            uint32_t last_digit = n % 10;
            if (lowest[last_digit] == 0) {
                lowest[last_digit] = n;
                ++found;
            }
        }
    }
    sieve_destroy(&s);
    for (uint32_t i = 0; i < 10; ++i)
        printf("Least unprimeable number ending in %u: %'u\n" , i, lowest[i]);
    return 0;
}