Patching my last SysRPL program for the division-by-4 stuff discussed above: change these lines ...
Code:
1GETLAM INDEX@
BEGIN
... to ...
Code:
1GETLAM DUPTWO #AND
#0=SKIP #2*
INDEX@
BEGIN
(full patched program: 415.5 bytes, #016Ah)
22 takes about 6.12_s now. What a speedup. 24 is obviously unchanged at 150_s (dunno what's taking so long there, perhaps it has to dig deep into the recursion before it can reject everything), 26 takes 10 seconds. 28 took ages with 3967_s. 30 is back down to 5.7_s, and 32 bounces up again (still running).
(05-05-2021 06:29 PM)Albert Chan Wrote: With this, I confirmed there is no solution for 16 ≤ n ≤ 44
Make that 16 ≤ n ≤ 56. I brought out the big guns too, rewrote my SysRPL program in C (code below) and ran it on my laptop, an XPS 13 9343 equipped with i5-5300U. Not exactly a speed demon, and the code is probably not perfect either, but it seems to do the job better than your script language. (Or is my full GCD partitioning worth that much? I doubt it, because there are still a few prime*2 numbers in there which it literally can't handle better than your simpler partitioning.) Up to 56 it took a handful of minutes per base at most. I aborted 58 after about two and a half hours, 60 went through in less than five seconds (highly composite number to the rescue! A perfect fit for GCD partitioning) with no results either. Haven't tried 62.
Since this program needs to handle quite big integers (> 350 bits if my math is right), I implemented my own unsigned near-infinite-length integers. The routines to operate on them are just the bare minimum for this program (addition, multiplication, modulo, and division all between an infinite-length integer and a short one, creating 0, checking for 0, disposal). Bitsets are still only 64 bits (unsigned long long), which limits the base to < 66, but I expect those wouldn't take me much to move to infinite length too: only needs AND, OR, leftshift by short integer, NOT on specified width. Alternatively I could invert part of the logic (switching not_taken back to taken) and avoid the NOT operation where zero-extension is harmful. It would be replaced by a combined ANDNOT, i.e. an AND operation which inverts one parameter; the other one would still put an upper bound on the length of the result when all 1-bits have to be stored.
Type sizes for the infinite-length integers are chosen such that 14 triggers all codepaths already (well, except errors of course); since the program returns the correct result on this case, it should have a good chance at being bug-free. Maybe performance could be improved by increasing these sizes and relying on the compiler's optimized code to handle operations on integers larger than the processor's wordsize.
Code:
#include <assert.h>
#include <malloc.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned int singledata_t;
typedef unsigned long long doubledata_t;
static_assert (sizeof(singledata_t) * 2 == sizeof(doubledata_t));
typedef struct {
unsigned int len;
singledata_t data[];
} nearinflen_uint_t;
#define NEARINFLEN_UINT_MALLOC(len) ((nearinflen_uint_t *) \
malloc(sizeof(nearinflen_uint_t) + sizeof(singledata_t) * (len)))
#define NEARINFLEN_UINT_SHIFT (sizeof(singledata_t) * 8)
static inline nearinflen_uint_t *nearinflen_uint_zero() {
nearinflen_uint_t *n = NEARINFLEN_UINT_MALLOC(1);
assert(n != NULL);
n->len = 1;
n->data[0] = 0;
return n;
}
static inline bool nearinflen_uint_iszero(nearinflen_uint_t *n) {
int i;
for (; i<n->len; ++i)
if (n->data[i] != 0) return false;
return true;
}
static inline void nearinflen_uint_release(nearinflen_uint_t *n) {
free(n);
}
static nearinflen_uint_t *nearinflen_uint_add(nearinflen_uint_t *n, singledata_t m) {
nearinflen_uint_t *res = NEARINFLEN_UINT_MALLOC(n->len + 1);
assert(res != NULL);
unsigned int i = 0;
doubledata_t carry = m;
for (; i < n->len && carry != 0; ++i) {
carry += n->data[i];
res->data[i] = (singledata_t) carry;
carry >>= NEARINFLEN_UINT_SHIFT;
}
if (carry != 0) {
res->data[n->len] = (singledata_t) carry;
res->len = n->len + 1;
} else {
res->len = n->len;
memcpy(res->data + i, n->data + i, sizeof(singledata_t) * (n->len - i));
}
return res;
}
static nearinflen_uint_t *nearinflen_uint_mul(nearinflen_uint_t *n, singledata_t m) {
nearinflen_uint_t *res = NEARINFLEN_UINT_MALLOC(n->len + 1);
assert(res != NULL);
unsigned int i = 0;
doubledata_t carry = 0;
for (; i < n->len; ++i) {
carry += ((doubledata_t) n->data[i]) * m;
res->data[i] = (singledata_t) carry;
carry >>= NEARINFLEN_UINT_SHIFT;
}
if (carry != 0) {
res->data[n->len] = (singledata_t) carry;
res->len = n->len + 1;
} else res->len = n->len;
return res;
}
static singledata_t nearinflen_uint_div2(nearinflen_uint_t *n, singledata_t m,
nearinflen_uint_t **res) {
if (res != NULL) {
*res = NEARINFLEN_UINT_MALLOC(n->len);
assert(*res != NULL);
memset((*res)->data, 0, sizeof(singledata_t) * n->len);
}
unsigned int i = n->len - 1;
doubledata_t rem = n->data[i];
if (m > rem) {
if (i == 0) {
if (res != NULL) (*res)->len = 1;
return n->data[0];
}
--i;
rem = (rem << NEARINFLEN_UINT_SHIFT) | n->data[i];
}
if (res != NULL) (*res)->len = i + 1;
doubledata_t m_shifted = m, bit = 1;
for (; rem >= m_shifted; bit <<= 1, m_shifted <<= 1);
while (bit != 1 || i != 0) {
if (bit == 1) {
bit <<= NEARINFLEN_UINT_SHIFT;
m_shifted <<= NEARINFLEN_UINT_SHIFT;
--i;
rem = (rem << NEARINFLEN_UINT_SHIFT) | n->data[i];
}
bit >>= 1;
m_shifted >>= 1;
if (rem >= m_shifted) {
rem -= m_shifted;
if (res != NULL) (*res)->data[i] |= bit;
}
}
return (singledata_t) rem;
}
typedef unsigned long long bitset_t;
typedef struct output_digit_t output_digit_t;
struct output_digit_t {
singledata_t digit;
output_digit_t *next;
};
singledata_t base;
bitset_t *valid_digits;
static void try_digits(nearinflen_uint_t *n, singledata_t i, bitset_t not_taken) {
bitset_t valid = not_taken & valid_digits[i];
singledata_t digit = i - nearinflen_uint_div2(n, i, NULL);
for (; digit < base; digit += i) {
bitset_t digit_bitset = 1 << (digit - 1);
if ((valid & digit_bitset) == 0) continue;
nearinflen_uint_t *tmp = nearinflen_uint_add(n, digit);
if (i + 1 != base) {
nearinflen_uint_t *tmp2 = nearinflen_uint_mul(tmp, base);
nearinflen_uint_release(tmp);
try_digits(tmp2, i + 1, not_taken & ~digit_bitset);
continue;
}
/* this destroys digit and n, but we cannot have
two results that only differ in the last digit anyway,
so print and break out */
nearinflen_uint_release(n);
digit = nearinflen_uint_div2(tmp, base, &n);
bool last;
output_digit_t *out = NULL, *prev;
do {
last = nearinflen_uint_iszero(n);
prev = out;
out = malloc(sizeof(output_digit_t));
assert(out != NULL);
out->next = prev;
out->digit = digit;
nearinflen_uint_release(tmp);
tmp = n;
digit = nearinflen_uint_div2(tmp, base, &n);
} while (!last);
nearinflen_uint_release(tmp);
do {
last = out->next == NULL;
printf("%u%c", out->digit, last ? '\n' : ';');
prev = out;
out = out->next;
free(prev);
} while (!last);
break;
}
nearinflen_uint_release(n);
}
static inline singledata_t gcd(singledata_t big, singledata_t small) {
do {
singledata_t tmp = big % small;
big = small;
small = tmp;
} while (small != 0);
return big;
}
int main(int argc, char **argv) {
if (argc < 2) {
printf("Usage: %s <num>\n", argv[0]);
return 1;
}
base = (singledata_t) atoi(argv[1]);
if (base < 2 || base > 65) {
printf("Invalid input, must be an integer between 2 and 65\n");
return 1;
}
if ((base & 1) != 0) return 0;
valid_digits = calloc(base, sizeof(bitset_t));
assert(valid_digits != NULL);
singledata_t *gcd_by_pos = calloc(base, sizeof(singledata_t));
assert(gcd_by_pos != NULL);
singledata_t i = 1;
bitset_t bit = 1;
for (; i < base; ++i, bit <<= 1) {
singledata_t tmp = gcd(i, base & 2 != 0 ? base * 2 : base);
gcd_by_pos[i] = tmp;
valid_digits[tmp] |= bit;
}
for (i = 1; i < base; ++i) valid_digits[i] = valid_digits[gcd_by_pos[i]];
free(gcd_by_pos);
nearinflen_uint_t *zero = nearinflen_uint_zero();
try_digits(zero, 1, ~((bitset_t) 0));
free(valid_digits);
return 0;
}
Search
Member List
Calendar
Help
