Challenge: sum of squares. Let's break 299

[Thomas Okken]

(01-18-2018 09:32 PM)pier4r Wrote:  then in the video they said they tested all the sequences up to 299. From 25 to 299 they found a way and likely there will be always a way.

It doesn't say so in so many words, but that made me think that there were no solutions below 25, and that is not the case:

n = 15:
8 1 15 10 6 3 13 12 4 5 11 14 2 7 9

n = 16:
8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16

n = 23:
2 23 13 12 4 21 15 10 6 19 17 8 1 3 22 14 11 5 20 16 9 7 18

I cheated and wrote a simple brute-force backtracking algorithm in C++:

Code:

#include <stdio.h>
#include <math.h>
#include <time.h>

int main(int argc, char *argv[]) {
    int n;
    if (argc != 2 || sscanf(argv[1], "%d", &n) != 1 || n < 2) {
        fprintf(stderr, "Usage: %s <n>\nwhere n >= 2\n", argv[0]);
        return 1;
    }

    time_t start_time = time(NULL);

    int *seq = new int[n + 1];
    bool *used = new bool[n + 1];
    for (int i = 1; i <= n; i++) {
        seq[i] = 0;
        used[i] = false;
    }

    int i = 1;
    long iter = 0;

    top_loop:
    iter++;
    int a = seq[i];
    used[a] = false;
    if (++a > n)
        goto fail;
    seq[i] = a;
    used[a] = true;
    seq[++i] = 0;

    inner_loop:
    a = seq[i];
    used[a] = false;
    int b;
    b = (int) ceil(sqrt(a + seq[i - 1] + 1));
    a = b * b - seq[i - 1];
    inner_loop_2:
    iter++;
    if (a > n) {
        if (--i == 1)
            goto top_loop;
        else
            goto inner_loop;
    }
    if (used[a]) {
        a += (b << 1) + 1;
        b++;
        goto inner_loop_2;
    }
    used[a] = true;
    seq[i] = a;
    if (i < n) {
        seq[++i] = 0;
        goto inner_loop;
    }

    printf("%d", seq[1]);
    for (i = 2; i <= n; i++)
        printf(" %d", seq[i]);
    printf("\nTime: %lds Iterations: %ld\n", time(NULL) - start_time, iter);
    return 0;

    fail:
    printf("No solution.\n");
    printf("Time: %lds Iterations: %ld\n", time(NULL) - start_time, iter);
    return 2;
}

In a nutshell: the algorithm would have to be a lot smarter to make a dent in this problem. It starts to get painfully slow in the 60s -- on a 1.3 GHz i5, not a speed demon by today's standards, but still, imagine how this would fare on a calculator. The case n = 60 took 6,619,547,574 iterations...