Есть ли способ представить любое число в виде суммы из четырех квадратов?

Есть ли способ представить любое число в виде суммы из четырех квадратов.

Например, 29 можно представить в виде 5 ^ 2 + 2 ^ 2 + 0 ^ 2 + 0 ^ 2

Я пробовал следующий код, но некоторые числа, дающие 5terms, например, 23 как 4 ^ 2 + 2 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2

код, который я пробовал:

 x=0;
 while(num!=0){
          x=(int)Math.floor(Math.sqrt(num));
         num=num-(x*x);        
}

Ответ 1

В отличие от того, что сказал Богем, я решил 23 из 4 терминов следующим образом:

23 = 3^2 + 3^2 + 2^2 + 1^2

И 29 следующим образом:

29 = 4^2 + 3^2 + 2^2 + 0^2

Моя логика начиналась бы так:

Начните с квадратного корня из числа - 1. Например. SQRT(29) = 5 - 1 = 4; Это наш первый термин.
Возьмите значение из точки 1), соберите его и добавьте к нему снова квадратное значение из точки 1) и посмотрите, если оно больше N. Если это так, уменьшите второй член суммы на 1 и добавьте его квадрат к значению значение от 1).
Если сумма сумм предыдущих квадратов значений меньше N, найдите следующий термин значения и повторите 2) до тех пор, пока у вас не будет всего 4 члена, который добавит до N.

Примечание. Это для вашего простого случая. Для сложного случая, например, 323, это может не сработать.

323 = 17^2 + 4^2 + 3^2 + 3^2

Помните, что, поскольку вы находите x-член, значение термина меньше или равно значения x-1 (предыдущего).

Ответ 2

Вот вам код алгоритма

Это даст вам все возможные комбинации...

int n, t1, t2, t;
        n = 29;//Your number

        for (int i = (int) Math.sqrt(n / 4); i * i <= n; i++) {
            t1 = n - i * i;
            for (int j = (int) Math.sqrt(t1 / 3); j <= i && j * j <= t1; j++) {
                t2 = t1 - j * j;
                for (int k = (int) Math.sqrt(t2 / 2); k <= j && k * k <= t2; k++) {
                    t = (int) Math.sqrt(t2 - k * k);
                    if (t <= k && t * t == t2 - k * k) {
                        System.out.println("(" + i + "^2) + (" + j + "^2) + ("+ k + "^2) + ("+ t +"^2)");
                    }
                }
            }
        }

Ответ 3

После первоначального ответа неправильно, я думал, что я его код: Это решение работает.

Я тестировал этот код, и он выполняет в O (log n) время, вплоть до очень больших чисел (решает для n = Long.MAX_VALUE в 75 мс на старом macbook pro)

public static void main(String[] args) {
    long number = 827347833323423451L;
    LinkedList<Long> solution = new LinkedList<Long>();
    if (fourSquares(number, solution))
        System.out.println(number + " = sum of squares of: " + solution);
    else
        System.out.println(number + " could not be solved"); // never happens
}

public static boolean fourSquares(long number, LinkedList<Long> solution) {
    if (number == 0) {
        for (long i = solution.size(); i < 4; i++)
            solution.add(0L);
        return true;
    }

    if (solution.size() == 4)
        return false;

    for (long i = (long) Math.sqrt(number); i > 0; i--) {
        solution.add(i);
        if (fourSquares(number - i * i, solution))
            return true;
        solution.removeLast();
    }

    return false;
}

Вывод:

9223372036854775807 = sum of squares of: [3037000499, 76994, 671, 23]

Ответ 4

Итак, я не мог вывести это из головы и решить его на Java, используя динамическое программирование, в частности, memoization.

Здесь соответствующие биты:

private final Map<Integer, int[]> memo = new HashMap<Integer, int[]>();

/**
 * @param n
 *        the number
 * @return int[]
 */
public int[] solveFor(final int n) {
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    final int[] a = new int[4];
    a[0] = (int) Math.floor(Math.sqrt(n));
    if (sumOfSquares(a) < n) {
        int[] b = solveFor(n - a[0] * a[0]);
        while (a[0] > 0 && b[3] > 0) {
            // won't fit
            a[0]--;
            b = solveFor(n - a[0] * a[0]);
        }
        System.arraycopy(b, 0, a, 1, 3);
    }
    memo.put(n, a);
    return a;
}

На этом низком 2.4 ГГц i5 он может вычислять все разложения от 0 до 2 000 000 за менее чем 3 секунды.

Очевидным недостатком, конечно же, является то, что он может быстро исчерпать память, если его попросят вычислить для всех целых чисел до большого числа. Но если он просто попросил решить, скажем, 42 миллиона, он может выдать правильный ответ за пару миллисекунд.

Я также уверен, что его все-таки можно улучшить/оптимизировать, особенно часть, которая просто уменьшает первый член, если находит решение для остатка слишком длинным, чтобы вписаться в оставшиеся пространства, но я оставлю это как упражнение для людей, которые имеют лучшие навыки математики и больше свободного времени.:)

Ответ 5

это сложно реализовать, поскольку, если между ними возникает простое число, вы никогда не сможете его разбить на квадратный корень из 1; например,

взять 11,

3 ^ 2 --- теперь осталось 2, и он не имеет квадратного корня, а число меньше, чем это "1", а 1 ^ (n) всегда 1.. поэтому всегда остается напоминание..

возможно, вам нужно следовать каким-то алгоритмам, как говорят другие ответы...

Ответ 6

В коде нет ничего плохого.

23 просто требуется 5 терминов для решения.

Попробуйте подсчитать количество термов и завершить цикл, если достигнут предел 4.

Редакция:

См. мой другой (лучший) ответ