Жак Арсак - Программирование игр и головоломок

Если после деления p на 2 результат оказывается нечетным, то мы вычитаем из этого результата a /2 + b . Обозначим новые значения a , b , p через а ', b ', p ' соответственно:

а ' = 2* а , p ' = p /2 − а /2 − b , b ' = a + b .

Для этих значений получаем:

a '* p ' = a * p − a 2− 2 a * b = а * р − ( а + b ) 2+ b 2= а * р − b ' 2+ b 2.

Это, наконец, дает

а '* p ' + b ' 2= а * р + b 2.

Инвариантной величиной цикла оказывается, таким образом, сумма ар + b 2, причем p остается четным. Это обеспечивается тем, что в случаях, когда p /2 нечетно, мы вычитаем нечетные b из нечетного p /2. Что касается b , то он нечетен потому, что он начинается со значения 1 и к нему прибавляются только четные значения а .

В начале а = 4, p (целая часть дроби ( n − 1)/4) четно, b = 1, так что ар + b 2= n .

Наконец, a , начиная с 4, умножается на 2 при каждом прохождении цикла; b начинается с 1, которое меньше соответствующего начального а = 4.

Тогда при переходе от a , b , p к a ', b ', p ' либо

b ' = b , а ' = 2* а , так что если b < а , то и b ' < а ';

либо

b ' = а + b , а ' = 2* а , что также сохраняет справедливость отношения а ' < b '.

Следовательно, вот ситуация, которую цикл оставляет инвариантной:

n = а * p + b 2;

а — степень двойки,

p четно,

b нечетно, b < а .

Кроме того, мы знаем, что при выходе из цикла p < а .

Если p равно нулю, то n = b 2. Тогда мы видим, что n — квадрат числа b , которое выводится, и все закончено.

Но n может оказаться полным квадратом и тогда, когда p не нуль. Попробуем рассмотреть все возможные случаи. Положим n = r 2( r нечетно). Соотношение

r 2= ар + b дает

r 2− b 2= ар .

Положим r + b = 2 u , r − b = 2 v ( r и b нечетны). Отсюда получаем 4 uv = ар .

Поскольку r = u + v , где r нечетно, получаем, что u и v не могут быть числами одинаковой четности, так что одно из них четно, а другое нечетно. Так как а является степенью двойки, то нечетный сомножитель относится к p . Выявим его, полагая р = s 2 t , где s нечетно, a t ≥ 1 ( p четно).

Напомним, что а = 2 k . В этих обозначениях 4 uv = ар = s 2 k + t , uv = s 2 k + t −2.

Возможные решения для пары u , v имеют вид пар

s '2 k + t -2, s ''

где s ' s " = s .

Покажем сначала, что s " — меньший из этих двух элементов пары. Вследствие t ≥ 1 имеем k − t ≤ k + t − 2.

Вследствие p < а последовательно выводим

s 2 t < 2 k ,

s ' s "2 t < 2 k .

s ' s " < 2 k - t ≤ 2 k + t -2≤ s ' 22 k + t -2

(потому что s ' нечетен и не меньше 1).

Следовательно, нужно взять u = s '2 k + t -2, v = s ".

Покажем теперь, что нужно обязательно взять 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− 2 ks = 2 k −1 s ' ( s ' − 2).

Вследствие р = s 2 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 = 2 s , b = 2 k − t − s = a /2 − p /2.

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

При t = 2 имеем

p = 4 s , 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 = а − 2 b , r = a − b ,

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

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

b = ар + b 2

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

ар = n − b 2

дает p = ( n − b 2)/ a < n / а .

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

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

4 q < n < 4 q +1.

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

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

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

2 2 q +1< n < 2 2 q +2,

то единственное значение a , удовлетворяющее условию a 2> n /2, есть a = 2 q +1, и для этого значения имеем a 2> n , что гарантирует остановку. Поскольку r = a − b , то а = r + b > r и, следовательно, a 2> n .

Во втором случае

r = 2 a − b и b < а , откуда а < 2 a − b = r .