Как усовершенствовать алгоритм для уравнения Диофанта?

Question

[Quintis]

Есть уравнение Диофанта -

x2 - 4 * y2 = n

из https://www.codewars.com/kata/554f76dca89983cc4000... .

Вот мой код для решения этого уравнения :

function solequa(n) {
  // your code
  let pt1 = 1 //pointer 1
  let pt2 = 1 // pointer 2
  let  result = 0
  const sqrtN = Math.sqrt(n)
  const diapason = [sqrtN , sqrtN+1]
  
  while (pt2 < n ) {
    result = pt1/pt2;
    console.log(pt1,pt2)
    const solve = pt1*pt1-4*pt2*pt2
    if (result < diapason[0]){
     pt1 =  pt1+ 1
    } else if (result > diapason[1]) {
      pt2 = pt2 + 1
    } else if (solve === n) {
      console.log("solved with " + pt1 + "  "+ pt2)
      return [pt1,pt2]
    } else {
      pt1 =  pt1+ 1
    }
  }
}

solequa(5)

Для малых чисел работает нормально но при solequa(16) алгоритм не может найти решение. Кто может помочь составить корректный алгоритм

Answer 1

[Wataru]

Логика вашего решения вообще непонятна. Какие-то жадные сдвиги одной из двух переменных на 1, да еще и ответ ровно один раз вернется, когда как в задаче надо найти все решения уравнения.

Там по вашей ссылке в задаче есть подсказка: уравнение можно переписать в виде (x-2y)(x+2y)=n

Отсюда получается решение: Перебирайте все делители n, не превосходащие корень. Пусть делитель d, тогда второй множитель будет n/d.

Осталось решить систему линейных уравнений:

x-2y=d
x+2y=n/d

Решается в уме - x=(d+n/d)/2, y=(n/d-d)/4

Отслось только учесть диофантовость уравнения - ответ должен быть неотрицательные целые числа. Значит, надо чтобы оба делителя d, n/d давали одинаковый остаток от деления на 4 и 2. Ну и d<=n/d, но это учтется перебором делителя до корня.

Вот и все решение - циклом переберите делитель до корня, убедитесь, что он и оставшийся множитель дают один и тот же остаток по модулю 4, вычислите x и y и выведите их.

Answer 2

[Sun_Day]

Во-первых, у вас в корне неверное решение, хотя бы потому что не соответствует условию:

find all integers
Тут же тест:

solEquaStr(90005) --> "[[45003, 22501], [9003, 4499], [981, 467], [309, 37]]"

Ваше решение вернет лишь первый и единичный случай. Нужно вернуть все.
Поэтому, цикл вайл тут тоже не подойдет.
Во-вторых, у вас неверное условие итерации. Нужно итерироваться iterator <= sqrt(N) (или pt1 <= sqrtN в вашем решении)
Нецелых чисел может быть очень много, особенно для больших чисел, поэтому по условию нужно вернуть целые числа(isInteger). Если при итерации не будет пары целых чисел, то решений нет, возвращаем пустой массив.

Ну и двигать поинтеры - тоже в корне неверно, нужно искать x,y.
x = (d + i) / 2;
y = (d - i) / 4

Решение выше вполне норм. Вот что-то похожее.

function solequa(n) {
    const sqrtN = Math.sqrt(n);
    const result = [];
    let x, y, d;
    for (let i = 1; i <= sqrtN; i++) {
        d = n / i;
        x = (d + i) / 2;
        y = (d - i) / 4
        if (Number.isInteger(x) && Number.isInteger(y)) {
            result.push([x, y]);
        }
    }
    return result;
}