Программирование игр и головоломок

Арсак Жак

Покажем теперь, что нужно обязательно взять s' =1, s" = s. По выбору u и v

b = 2^{k+t– 2}s' - s" < а = 2^k.

Отсюда получаем:

s" > 2^{k+t– 2}s' - 2^k,

и, так

как t >= 1:

s" > 2^{k– 1}s' - 2^k,

s = s's" > 2^{k– 1}s'²– 2^ks = 2^{k– 1}s' (s' - 2).

Вследствие р = s2^t < а = 2^k выводим s < 2^{k– t} <= 2^{k– 1}.

Объединим два полученных неравенства:

2^{k– 1}s' (s' - 2) < x < 2^{k– 1}, поэтому s' (s' - 2) < 1.

Единственное нечетное число s', удовлетворяющее этому соотношению, это s' = 1. Следовательно, у нас остается единственная возможность:

u = 2^{k+t– 2}, v = s,

b = u– v = 2^{k+t– 2}– s < а = 2^k,

s > 2^{k+t– 2}– 2^k.

Так как s < 2^{k– t}, то t должно быть таким, чтобы

2^{k– t} > 2^{k+t– 2}– 2^k.

Поскольку t должно быть строго положительно, то его единственными возможными значениями являются t = 1 и t = 2.

При t = 1 имеем

p = 2s, b = 2^{k– t}– s = a/2 - p/2.

Следовательно, если 2b = а– p, то n — квадрат числа (а + p)/2 = а– b.

При t = 2 имеем

p = 4s, b = 2^k– s = a– p/4.

Следовательно,

если p = 4(a– b), то n — квадрат числа a + p/4 = 2а– b.

Этим исчерпываются случаи, когда n может быть полным квадратом.

Можно спросить себя, могут ли эти различные случаи действительно осуществляться. Заметим, что при вступлении в цикл у нас b = 1, a = 4. После этого b может быть изменено добавлением а, т. е. кратным числа 4. Следовательно, b остается сравнимым с 1 по модулю 4. В трех возможных случаях:

p = 0, r = b,

p = а– 2b, r = a– b,

p = 4 (a– b), r = 2a– b,

первый случай — единственный, в котором квадратный корень из n сравним с 1 по модулю 4; два других дают квадратный корень, сравнимый с 3 по модулю 4. При выходе из цикла равенство

b = ар + b²

с учетом соотношений p < a, b < a дает n < 2a² и, следовательно, при выходе из цикла a² > n/2. Равенство

ар = n– b²

дает p = (n– b²)/a < n/а.

Если окажется, что n/а < a, то непременно p < а и цикл закончен. Чтобы цикл остановился, необходимо, чтобы a² > n/2, и цикл заведомо останавливается, если a³ > n.

Следовательно, все зависит от положения n по отношению к степеням двойки. Существует такое целое n, что

4^q < n < 4^q+1.

Возможны два случая. Во-первых, может выполняться неравенство

4^q = 2^2q < n < 2^2q+1,

и тогда для k = q число a² = 2^2q > n/2 может быть значением остановки, но в этом нет уверенности. С другой стороны, если