StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Instead of enumerating the space of numbers, enumerate the different "signatures" of numbers that are lucky. and then print all the differnet combination of those.</p> <p>This can be done with trivial backtracking:</p> <pre><code>#define _GNU_SOURCE #include <assert.h> #include <limits.h> #include <stdbool.h> #include <stdint.h> #include <stdio.h> #define bitsizeof(e) (CHAR_BIT * sizeof(e)) #define countof(e) (sizeof(e) / sizeof((e)[0])) #define BITMASK_NTH(type_t, n) ( ((type_t)1) << ((n) & (bitsizeof(type_t) - 1))) #define OP_BIT(bits, n, shift, op) \ ((bits)[(unsigned)(n) / (shift)] op BITMASK_NTH(typeof(*(bits)), n)) #define TST_BIT(bits, n) OP_BIT(bits, n, bitsizeof(*(bits)), & ) #define SET_BIT(bits, n) (void)OP_BIT(bits, n, bitsizeof(*(bits)), |= ) /* fast is_prime {{{ */ static uint32_t primes_below_1M[(1U << 20) / bitsizeof(uint32_t)]; static void compute_primes_below_1M(void) { SET_BIT(primes_below_1M, 0); SET_BIT(primes_below_1M, 1); for (uint32_t i = 2; i < bitsizeof(primes_below_1M); i++) { if (TST_BIT(primes_below_1M, i)) continue; for (uint32_t j = i * 2; j < bitsizeof(primes_below_1M); j += i) { SET_BIT(primes_below_1M, j); } } } static bool is_prime(uint64_t n) { assert (n < bitsizeof(primes_below_1M)); return !TST_BIT(primes_below_1M, n); } /* }}} */ static uint32_t prime_checks, found; static char sig[10]; static uint32_t sum, square_sum; static void backtrack(int startdigit, int ndigits, int maxdigit) { ndigits++; for (int i = startdigit; i <= maxdigit; i++) { sig[i]++; sum += i; square_sum += i * i; prime_checks++; if (is_prime(sum) && is_prime(square_sum)) { found++; } if (ndigits < 18) backtrack(0, ndigits, i); sig[i]--; sum -= i; square_sum -= i * i; } } int main(void) { compute_primes_below_1M(); backtrack(1, 0, 9); printf("did %d signature checks, found %d lucky signatures\n", prime_checks, found); return 0; } </code></pre> <p>When I run it it does:</p> <pre><code> $ time ./lucky did 13123091 signature checks, found 933553 lucky signatures ./lucky 0.20s user 0.00s system 99% cpu 0.201 total </code></pre> <p>Instead of found++ you want to generate all the distinct permutations of digits that you can build with that number. I also precompute the first 1M of primes ever.</p> <p>I've not checked if the code is 100% correct, you may have to debug it a bit. But the rought idea is here, and I'm able to generate all the lucky permutation below 0.2s (even without bugs it should not be more than twice as slow).</p> <p>And of course you want to generate the permutations that verify A <= B. You may want to ignore generating partitions that have more digits than B or less than A too. Anyway you can improve on my general idea from here.</p> <p>(Note: The blurb at the start is because I cut and paste code I wrote for project euler, hence the very fast is_prime that works for N <= 1M ;) )</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload