Числа до 100 как сумма четырех квадратов
Перейти к содержимому

Числа до 100 как сумма четырех квадратов

  • автор:

Суммы квадратов, суммы кубов.

Еще в древнем Египте была известна формула для суммы последовательных натуральных чисел: $$ 1+2+\ldots+n=\frac2 $$ (чтобы убедиться в этом, сложите первое слагаемое с последним, второе с предпоследним и т. д.).

Найдите формулу для суммы а) квадратов $1^2+2^2+\ldots+n^2$; б) кубов $1^3+2^3+\ldots+n^3$; в) четвертых степеней $1^4+2^4+\ldots+n^4$.

Подсказка 1

Начните эксперимента: вычислите первые несколько сумм ($1^2+2^2$, $1^2+2^2+3^2$ и т. д. хотя бы до $n=5$). После этого попробуйте найти закономерность.

Подсказка 2

Экспериментальные данные полезно записать в виде таблицы.

$n$ 1 2 3 4 5 6 7
$1^<\phantom1>+\ldots+n^<\phantom1>$ 1 3 6 10 15 28 35
$1^2+\ldots+n^2$ 1 5 14 30 55 91 140
$1^3+\ldots+n^3$ 1 9 36 100 225 784 1225
$1^4+\ldots+n^4$ 1 17 98 354 979 2275 4676

Попробуйте найти связь между числами в (одном столбце, но) разных строках.

Подсказка 3

Если у чисел в двух строках постоянно появляются общие делители (например, 10 и 30 делятся на 10, 15 и 55 на 5, 28 и 91 на 7. ), то полезно изучить отношение этих чисел. Что за последовательности получаются? (Удобно добавить в таблицу соответствующие строки.)

Решение

Как и предлагалось в последнем указании, изучим отношение первых двух строк.

$n$ 1 2 3 4 5 6 7
$1^<\phantom1>+\ldots+n^<\phantom1>$ 1 3 6 10 15 21 28
$1^2+\ldots+n^2$ 1 5 14 30 55 91 140
$S_2/S_1$ 1 5/3 7/3 3 11/3 13/3 5

Теперь нетрудно заметить закономерность: с увеличением $n$ на 1 частное увеличивается на $2/3$, т. е. это частное равно $(2n+1)/3$. Вместе с формулой для $1+2+\ldots+n$ это дает (гипотетический) ответ $$ 1^2+2^2+\ldots+n^2=\frac2\cdot\frac3=\frac6. $$

С суммами кубов дело обстоит даже проще, чем с квадаратами — глядя на таблицу естественно предположить, что $S_3=S_1^2$, т. е. $$ 1^3+2^3+\ldots+n^3=\frac4. $$

Заметно сложнее угадать формулу для суммы четвертых степеней. В отличие от предыдущих случаев, у $S_4(n)$ практически не видно общих делителей с $S_1(n)$ (кроме двойки). Зато можно заметить, что 14 и 98 делятся на 7, 55 и 979 на 11. Посмотрим на отношение $S_4/S_2$.

$n$ 1 2 3 4 5 6
$S_2$ 1 5 14 30 55 91
$S_4$ 1 17 98 354 979 2275
$S_4/S_2$ 1 17/5 7 59/5 89/5 25

Видно, что после домножения этого отношения на 5 получится последовательность целых чисел: 5, 17, 35, 59, 89, 125. Тут уже нельзя сказать, что разность соседних чисел неизменна. Все же посмотрим на эти разности: 12, 18, 24, 30. — закономерность сразу видна!

Итак, стало понятно, какие должны быть ответы, но как их доказать?

Задумаемся над тем, что вообще значит, что какое-то выражение $P(n)$ дает формулу для суммы $1^2+\ldots+n^2$? Это значит, что $P(1)=1$, $P(2)=P(1)+2^2$ и т. д., $P(n)=P(n-1)+n^2$. То есть все сводится к быть может утомительному, но прямолинейному вычислению: $$\begin \frac6+n^2&=&\frac6=\\ &=&\frac6=\frac6. \end$$ Аналогичным образом (говоря формально, «по индукции») можно доказать найденные выше формулы для $S_3(n)$ и $S_4(n)$.

Послесловие

Видимо наиболее наглядный способ вычислить сумму $1+2+\ldots+n$ — геометрический: об этой сумме можно думать как о треугольном числе, т. е. площади «пиксельного» (составленного из единичных квадратиков) равнобедренного прямоугольного «треугольника» со стороной $n$. Из двух таких треугольников легко составить прямоугольник размера $n\times(n+1)$, откуда и получается ответ $n(n+1)/2$ (половина площади прямоугольника).

Подобным образом можно вычислить и сумму $1^2+2^2+\ldots+n^2$: ее можно проинтерпретировать как объем пирамиды из кубиков (нижний слой которой состоит из $n^2$ кубиков, следующий из $(n-1)^2$ кубиков и т. д.), после чего сложить из 6 таких пирамид параллелепипед $n\times(n+1)\times(2n+1)$. Как это сделать, можно посмотреть на сайте «Математические этюды».

Есть геометрические доказательства и у позволяющего вычислить сумму кубов замечательного равенства $1^3+2^3+\ldots+n^3=(1+2+\ldots+n)^2$. Одно из них можно посмотреть на youtube-канале Think Twice, см. также подборку «доказательств без слов» в Кванте №11 за 2017 год.

Заметим, однако, что формула для суммы четвертых степеней не раскладывается (в отличие от предыдущих) на простые линейные множители. Видимо из-за этого ее не получается найти методами геометрического суммирования и открыта она была примерно на 1 000 лет позже, чем формула для суммы кубов (известная уже в античности).

Чтобы продвинуться дальше, полезно задуматься, что мы вообще надеемся увидеть в качестве ответа. Не любое алгебраическое выражение можно разложить на достаточно простые множители, но всегда можно, наоборот, раскрыть все скобки и привести подобные. В изученных нами случаях получаются следующие многочлены от $n$: $$\begin 1^<\phantom1>+2^<\phantom1>+\ldots+n^<\phantom1>&=&\frac12n^2+\frac12n;\\ 1^2+2^2+\ldots+n^2&=&\frac13n^3+\frac12n^2+\frac16n;\\ 1^3+2^3+\ldots+n^3&=&\frac14n^4+\frac12n^3+\frac14n^2;\\ 1^4+2^4+\ldots+n^4&=&\frac15n^5+\frac12n^4+\frac13n^3-\frac1n.\\ \end$$ Практически сразу возникает гипотеза, что вообще для любого $k$ сумма $1^k+2^k+\ldots+n^k$ равна многочлену от $n$, который начинается с $\frac1n^$ (в этом выражении изучавшие анализ сразу узнают первообразную того, что мы суммируем), дальше идет $\frac12n^k$ и члены еще меньших степеней.

С алгебраической точки зрения это очень естественный переход — но самого языка алгебры, «выражений с буквами» и преобразования таких выражений, не существовало до работ Франсуа Виета (конца 16 века)! А до появления такого языка гипотезу выше практически невозможно не то что доказать — сформулировать.

В первой половине 17 века Иоганн Фаульхабер смог найти формулы для сумм $1^k+2^k+\ldots+n^k$ до $k=17$ (интересную попытку реконструкции рассуждений Фаульхабера опубликовал Дональд Кнут). Вот несколько из таких формул: $$\begin S_2(n)&=&\frac13n^3+\frac12n^2+\frac16n;\\ S_3(n)&=&\frac14n^4+\frac12n^3+\frac14n^2;\\ S_4(n)&=&\frac15n^5+\frac12n^4+\frac13n^3&-&\frac1n;\\ S_5(n)&=&\frac16n^6+\frac12n^5+\frac5n^4&-&\frac1n^2;\\ S_6(n)&=&\frac17n^7+\frac12n^6+\frac12n^5&-&\frac16n^3&+&\frac1n;\\ S_7(n)&=&\frac18n^8+\frac12n^7+\frac7n^6&-&\frac7n^4&+&\frac1n^2. \end$$ Коэффициенты при $n^$ и при $n^k$ обсуждались выше. Подумав некоторое время вы наверняка угадаете формулу для коэффициентов при $n^$ и $n^$, а быть может, и для коэффициента при $n^$.

фрагмент «Ars Conjectandi» Я. Бернулли

Возникает надежда на общую (работающую для произвольного $k$) формулу для $S_k(n)$. И такую формулу нашел в конце 17 века Якоб Бернулли. В нее входит последовательность так называемых чисел Бернулли ($B^0=1$, $B^1=1/2$, $B^2=1/6$. ), а саму формулу можно записать символически очень коротко: $$ S_k(n)=\frac-B^>. $$ Понимать эту запись следует следующим образом. Нужно раскрыть формально в выражении $(n+B)^$ скобки, после чего начать воспринимать $B^m$ не как степень переменной $B$, а как $m$-е число Бернулли. Например: $$\begin S_2(n)&=&\frac3=\\ &=&\frac3= \frac13\left(n^3+\frac32n^2+\frac36n\right). \end$$ Если поверить в эту (крайне странную, на первый взгляд) процедуру, то будет ясно и как вычислять числа Бернулли: при подстановке $n=1$ получается равенство $1=\frac<(1+B)^-B^>$, позволяющее найти $B^k$, если числа Бернулли с меньшими номерами уже известны. В таблице ниже приведены несколько первых чисел Бернулли.

Замечательным образом те же самые числа Бернулли возникают и в квадратурных формулах для вычисления приближенных значений интегралов, и при вычислении бесконечных сумм типа $1+\frac14+\frac19+\frac1+\ldots=\frac<\pi^2>6$ (т. е. значений знаменитой дзета-функции), и в комбинаторике, и в теории чисел, и в топологии.

Литература

  1. Д. Пойа. Математика и правдоподобные рассуждения (М.: Наука, 1975)
    http://ilib.mccme.ru/djvu/polya/rassuzhdenija.htm https://mathedu.ru/text/poya_matematika_i_pravdopodobnye_rassuzhdeniya_1975
    Мало где можно прочитать не о конкретной области математики, а о том, как вообще решать новую для себя математическую задачу . Подсказки и решение выше по существу следуют главе 7 этой замечательной книги.
  2. Интервью с академиком И. М. Гельфандом // Квант, 1989, № 1, 3–12
    http://kvant.mccme.ru/1989/01/akademik_izrail_moiseevich_gel.htm
    В решении выше сделана попытка объяснить, как некоторые формулы для сумм степеней мог бы искать любой человек. Интересующимся математикой может быть интересно прочитать, как такую задачу решал в школьные годы один из выдающихся математиков 20 века (собственно про это — небольшой фразмент на стр. 8–9, но все интервью интересное).
  3. В. С. Абрамович. Суммы одинаковых степеней натуральных чисел // Квант, 1973, № 5, 22–25
    http://kvant.mccme.ru/1973/05/summy_odinakovyh_stepenej_natu.htm
    Можно прочитать доказательство формулы для суммы степеней (из конца послесловия), использующее, по сути, только бином Ньютона.
  4. Г. А. Мерзон. Алгебра, геометрия и анализ сумм степеней последовательных чисел // Матем. просв., сер. 3, вып. 21 (2017), 104–118.
    https://mccme.ru/free-books/matpros_21.html
    Можно прочитать больше о разных взглядах на задачу о суммировании степеней.
  5. Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика (М.: Мир, 1998)
    В учебнике, написанном по лекциям знаменитого Дональда Кнута, обсуждается и задача о суммировании степеней и числа Бернулли.

Быстрое возведение чисел от 1 до 100 в квадрат

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

*квадраты до сотни

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

Правило 1 (отсекает 10 чисел)

Для чисел, оканчивающихся на 0.
Если число заканчивается на 0, умножить его не сложнее, чем однозначное число. Стоит лишь дописать пару нулей.

70 * 70 = 4900. 

В таблице отмечены красным.

Правило 2 (отсекает 10 чисел)

Для чисел, оканчивающихся на 5.
Чтобы возвести в квадрат двузначное число, оканчивающееся на 5, нужно умножить первую цифру (x) на (x+1) и дописать к результату “25”.

75 * 75 = 7 * 8 = 56 … 25 = 5625. 

В таблице отмечены зеленым.

Правило 3 (отсекает 8 чисел)

Для чисел от 40 до 50.

XX * XX = 1500 + 100 * вторую цифру + (10 - вторая цифра)^2 

Достаточно трудно, верно? Давайте разберем пример:

43 * 43 = 1500 + 100 * 3 + (10 - 3)^2 = 1500 + 300 + 49 = 1849. 

В таблице отмечены светло-оранжевым.

Правило 4 (отсекает 8 чисел)

Для чисел от 50 до 60.

XX * XX = 2500 + 100 * вторую цифру + (вторая цифра)^2 

Тоже достаточно трудно для восприятия. Давайте разберем пример:

53 * 53 = 2500 + 100 * 3 + 3^2 = 2500 + 300 + 9 = 2809. 

В таблице отмечены темно-оранжевым.

Правило 5 (отсекает 8 чисел)

Для чисел от 90 до 100.

XX * XX = 8000+ 200 * вторую цифру + (10 - вторая цифра)^2 

Похоже на правило 3, но с другими коэффициентами. Давайте разберем пример:

93 * 93 = 8000 + 200 * 3 + (10 - 3)^2 = 8000 + 600 + 49 = 8649. 

В таблице отмечены темно-темно-оранжевым.

Правило №6 (отсекает 32 числа)

Необходимо запомнить квадраты чисел до 40. Звучит дико и трудно, но на самом деле до 20 большинство людей знают квадраты. 25, 30, 35 и 40 поддаются формулам. И остается лишь 16 пар чисел. Их уже можно запомнить при помощи мнемоники (о которой я также хочу рассказать позднее) или любыми другими способами. Как таблицу умножения 🙂
В таблице отмечены синим.

Вы можете запомнить все правила, а можете запомнить выборочно, в любом случае все числа от 1 до 100 подчиняются двум формулам. Правила же помогут, не используя эти формулы, быстрее посчитать больше 70% вариантов. Вот эти две формулы:

Формулы (осталось 24 числа)

Для чисел от 25 до 50

XX * XX = 100(XX - 25) + (50 - XX)^2 
37 * 37 = 100(37 - 25) + (50 - 37)^2 = 1200 + 169 = 1369 

Для чисел от 50 до 100

XX * XX = 200(XX - 50) + (100 - XX)^2 
67 * 67 = 200(67 - 50) + (100 - 67)^2 = 3400 + 1089 = 4489 

Конечно не стоит забывать про обычную формулу разложения квадрата суммы (частный случай бинома Ньютона):

(a+b)^2 = a^2 + 2ab + b^2. 56^2 = 50^2 + 2*50*6 + 6*2 = 2500 + 600 + 36 = 3136. 

UPDATE
Произведения чисел, близких к 100, и, в частности, их квадраты, также можно вычислять по принципу «недостатков до 100»:

Словами: из первого числа вычитаем «недостаток» второго до сотни и приписываем двузначное произведение «недостатков».

Для квадратов, соответственно, еще проще.

92*92 = (92-8)*100+8*8 = 8464 

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

Кстати, думаю, все читатели хабры знают, что 64^2 = 4096, а 32^2 = 1024.
Многие квадраты чисел запоминаются на ассоциативном уровне. Например, я легко запомнил 88^2 = 7744, из-за одинаковых чисел. У каждого наверняка найдутся свои особенности.

Две уникальные формулы я впервые нашел в книге «13 steps to mentalism», которая мало связана с математикой. Дело в том, что раньше (возможно, и сейчас) уникальные вычислительные способности были одним из номеров в сценической магии: фокусник рассказывал байку о том, как он получил сверхспособности и в доказательство этого моментально возводит числа до сотни в квадрат. В книге так же указаны способы возведения в куб, способы вычитания корней и кубических корней.

Если тема быстрого счета интересна — буду писать еще.
Замечания об ошибках и правки прошу писать в лс, заранее спасибо.

  • Счет в уме
  • возведение в квадрат
  • тренировка памяти

Сумма четырех квадратов

Author24 — интернет-сервис помощи студентам

Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел или, что тоже самое, в виде четырех квадратов неотрицательных целых чисел(т. Лагранжа). Дано натуральное n; указать неотрицательные целые a^2+b^2+c^2+d^2=n.
Помогите решить задачу пожалуйста!

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

Разложение числа на сумму четырех квадратов
Известно, что любое натуральное число можно представить в виде суммы не более чем четырёх квадратов.

Сумма квадратов 😉
Можно ли заданное натуральное число М представить в виде суммы двух квадратов натуральных чисел? .

сумма двух квадратов
Есть начальное и конечное число n i m нужно вывести все натуральные числа в входящие в диапазон от.

Сумма квадратов 3-х чисел
Дано натуральное N<=1000. Найти все тройки натуральных чисел a, b ,c (a<=b<=c), удовлетворяющих.

Заблокирован

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

4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28

Красивая теорема, спасибо.
Четыре вложенных цикла имхо жестковато. Навскидку, я бы заполнил массив всех чисел от 0 до n, которые являются суммой двух квадратов, с запоминанием их составляющих — то есть, все Пифагоровы тройки с максимальным числом от 0 до n. А потом просто искал бы 2 элемента этого массива, которые в сумме дадут n — по теореме они обязательно найдутся. Мне кажется, это должно быть оптимальнее брутфорса.

Добавлено через 2 часа 36 минут
UPD конечно я Пифагора приплел зря, имелись в виду не его тройки, а просто числа, представимые в виде суммы двух квадратов. Но похоже я был излишне оптимистичен в своих прогнозах, что таких чисел до n существенно меньше чем n — https://oeis.org/A001481 Алгоритм работать будет, но массив будет длинный.

Эксперт С++

3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
///////////////////////////////////////////////////////////////////////////////////////// //Известно, что любое натуральное число можно представить в виде суммы не более чем четырех //квадратов натуральных чисел или, что то же самое, в виде четырех квадратов неотрицательных //целых чисел(т. Лагранжа). Дано натуральное n; указать неотрицательные целые a^2+b^2+c^2+d^2=n. ///////////////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include ///////////////////////////////////////////////////////////////////////////////////////// typedef unsigned long long T_int; typedef std::vector  T_int > T_numbers; ///////////////////////////////////////////////////////////////////////////////////////// T_int get_max_sqrt( T_int m ) { return static_cast T_int > ( sqrt ( double( m ) ) ); } ///////////////////////////////////////////////////////////////////////////////////////// bool successfully_set_max_sqrt_from_and_print ( int ind, T_numbers & numbers, T_int & R ) { T_int N = numbers[ ind ] = get_max_sqrt( R ); R -= N * N; bool bool_res = R == 0; if( bool_res ) { std::copy ( numbers.begin (), numbers.end (), std::ostream_iterator T_int > ( std::cout, "\t" ) ); T_int sum = std::inner_product ( numbers.begin (), numbers.end (), numbers.begin (), 0 ); std::cout  <"->\t"   ::endl; } return bool_res; } ///////////////////////////////////////////////////////////////////////////////////////// void print_number_as_sum_of_four_squares( T_int n )  successfully_set_max_sqrt_from_and_print( 2, numbers, R )  if( A == 0 ) { std::cout  <"Квадраты не найдены."  ::endl; }//if }//for } ///////////////////////////////////////////////////////////////////////////////////////// int main() { std::locale::global(std::locale("")); srand(unsigned(time(0))); for(;;) { T_int n = rand() * rand(); std::cout  ::endl  ::endl  ::endl  ::endl  <"n = "   ::endl; print_number_as_sum_of_four_squares( n ); system("pause"); }//for }

4817 / 2278 / 287
Регистрация: 01.03.2013
Сообщений: 5,947
Записей в блоге: 28

Mr.X, я научился драгэндропить ваши коды в онлайн-компилятор, комментарить нужные строчки чтобы программа запускалась и выводила результат. Если я правильно понял ваш алгоритм, он в цикле от максимального целого корня из исходного числа до 1 отнимает от n квадрат этого числа, а остаток пытается разложить в сумму трех квадратов по простому правилу — выделяя каждый раз из остатка максимальный полный квадрат. Выглядит как хорошее решение, хотя я пока не понял, гарантирует ли этот алгоритм нахождение разложения. Я пробовал без цикла, выделять просто из исходного числа максимальный квадрат, и из его остатка и т.д. И на числах от 1 до 22 это у меня работало, а на 23 отказало

Эксперт С++

3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867

ЦитатаСообщение от _Ivana Посмотреть сообщение

гарантирует ли этот алгоритм
Да, ваши догадки оправдались, моя предыдущая программа не все числа считает.
Вот эта все вроде бы:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286
///////////////////////////////////////////////////////////////////////////////////////// //Известно, что любое натуральное число можно представить в виде суммы не более чем четырех //квадратов натуральных чисел или, что то же самое, в виде четырех квадратов неотрицательных //целых чисел(т. Лагранжа). Дано натуральное n; указать неотрицательные целые a^2+b^2+c^2+d^2=n. ///////////////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include #include ///////////////////////////////////////////////////////////////////////////////////////// typedef std::string T_str; typedef long long T_int; typedef std::vector  T_int > T_numbers; ///////////////////////////////////////////////////////////////////////////////////////// T_int get_max_sqrt( T_int m ) { return static_cast T_int > ( sqrt ( double( m ) ) ); } ///////////////////////////////////////////////////////////////////////////////////////// bool successfully_set_max_sqrt_for_ind ( int ind, T_numbers & numbers, T_int & R ) { T_int N = numbers[ ind ] = get_max_sqrt( R ); R -= N * N; return R == 0; } ///////////////////////////////////////////////////////////////////////////////////////// void for_num_set_power_of_two_and_factor ( T_int n, T_int & _222, T_int & factor ) { _222 = 1; factor = n; while( factor % 2 == 0 ) { _222 *= 2; factor /= 2; }//while } ///////////////////////////////////////////////////////////////////////////////////////// bool successfully_for_num_set_four_squares ( T_int num, T_numbers & numbers )  }//for return false; } ///////////////////////////////////////////////////////////////////////////////////////// bool successfully_print_number_as_sum_of_four_squares( T_int num ) { T_int _222 = 0; T_int factor = 0; for_num_set_power_of_two_and_factor ( num, _222, factor ); T_numbers n(4); T_numbers m(4); bool bool_res = successfully_for_num_set_four_squares ( _222, n ) && successfully_for_num_set_four_squares ( factor, m ); if( bool_res ) { T_numbers res(4); if( _222 == 1 ) { res = m; } else if( factor == 1 ) { res = n; } else { res.assign( 4, 0 ); res[0] = abs ( std::inner_product ( n.begin (), n.end (), m.begin (), T_int () ) ); T_numbers n1 = n; n1[0] *= -1; n1[2] *= -1; T_numbers m1 = m; std::swap( m1[0], m1[1] ); std::swap( m1[2], m1[3] ); res[1] = abs ( std::inner_product ( n1.begin (), n1.end (), m1.begin (), T_int () ) ); T_numbers n2 = n1; n2[1] = n[2]; n2[2] = -n[3]; n2[3] = n[1]; T_numbers m2 = m1; m2[0] = m[2]; m2[2] = m[1]; m2[3] = m[3]; res[2] = abs ( std::inner_product ( n2.begin (), n2.end (), m2.begin (), T_int () ) ); T_numbers n3 = n2; n3[1] = n[3]; n3[2] = -n[1]; n3[3] = n[2]; T_numbers m3 = m2; m3[0] = m[3]; m3[2] = m[2]; m3[3] = m[1]; res[3] = abs ( std::inner_product ( n3.begin (), n3.end (), m3.begin (), T_int () ) ); }//else std::copy ( res.begin (), res.end (), std::ostream_iterator T_int > ( std::cout, "\t" ) ); std::cout  <"->\t"  ::inner_product ( res.begin (), res.end (), res.begin (), T_int () )  ::endl; }//if return bool_res; } ///////////////////////////////////////////////////////////////////////////////////////// void print_prompt_and_input_val_in_segment ( T_int & val, T_int L, T_int R ) { static const T_str R_str = std::to_string( R ); bool bool_res = true; do { std::cout  <"n ( "   <".."   <" )\t=\t"; T_str str_val; std::cin >> str_val; while ( str_val.size() > 1 && str_val.front() == '0' ) { str_val.erase( 0, 1 ); } bool_res = str_val.size()  R_str.size() || str_val.size() == R_str.size() && str_val  R_str; if( bool_res ) { std::istringstream ssin( str_val ); ssin >> val; bool_res = val >= L; }//if } while( !bool_res ); } ///////////////////////////////////////////////////////////////////////////////////////// int main() { std::locale::global(std::locale("")); const T_int LEFT_BOUND = 1; const T_int RIGHT_BOUND = std::numeric_limits T_int >::max(); for(;;) { T_int n = 0; print_prompt_and_input_val_in_segment ( n, LEFT_BOUND, RIGHT_BOUND ); successfully_print_number_as_sum_of_four_squares( n ); std::cout  ::endl  ::endl  ::endl  ::endl; }//for }

О теореме Лагранжа

Статья, посвящённая поиску решений теоремы Лагранжа о сумме четырёх квадратов с примерами на Си.

Небольшая статья, в которой последовательно строится поиск решения теоремы Лагранжа о том, что любое натуральное число можно представить в виде суммы квадратов четырёх целых чисел. Статья сопровождается примерами программ на языке Си. Последний пример не только весьма эффективен, но и полностью базируется на целочисленной арифметике.

Измышления о теореме Лагранжа с примерами программ

Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов неотрицательных целых чисел (теорема Лагранжа).

Ввести натуральное N и найти для него такие целые неотрицательные $$x,y,z$$ и $$t$$, чтобы $$x^2+y^2+z^2+t^2=N$$.

 1  #include  2    3  void main()  4  int N, x, y, z, t;  5    6  scanf("%d", &N);  7  for(x=1; x*x N; x++)  8  for(y=0; y*y N; y++)  9  for(z=0; z*z N; z++)  10  for(t=0; t*t N; t++)  11  if(x*x+y*y+z*z+t*t == N)  12  printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N);  13  > 

Кстати, оператор if внутри циклов выполнится $$(sqrt(N)+1)^4$$ раз (больше, чем $$N^2$$). Проверим это:

 1  #include  2    3  void main()  4  int N, x, y, z, t;  5  long int loops = 0;  6    7  scanf("%d", &N);  8  for(x=1; x*x N; x++)  9  for(y=0; y*y N; y++)  10  for(z=0; z*z N; z++)  11  for(t=0; t*t N; t++)  12  loops++;  13  if(x*x+y*y+z*z+t*t == N)  14  printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N);  15  >  16  printf("%ld\n", loops);  17  > 

Для N=20 получим число 625=5 4 , для 10000 — 104060401

Что-то не так: слишком много одинаковых вариантов. Заметим, что (например, для N==11) это всё перестановки одного и того же сочетания. Как добиться, чтобы выводилась только одна перестановка? Из всех перестановок упорядочена (например, по возрастанию) только одна, так что можно смело рассматривать только варианты $$x

 1  #include  2    3  void main()  4  int N, x, y, z, t;  5  long int loops = 0;  6    7  scanf("%d", &N);  8  for(x=1; x*x N; x++)  9  for(y=0; y x; y++)  10  for(z=0; z y; z++)  11  for(t=0; t z; t++)  12  loops++;  13  if(x*x+y*y+z*z+t*t == N)  14  printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N);  15  >  16  printf("%ld\n",loops);  17  > 

В этом алгоритме сложность пониже: для 20 — 70, для 10000 — 4598126, для 100000 — 428761520 (уже можно дождаться конца ). Как и следовало ожидать, это число сочетаний с повторениями $$C_k^m$$, где $$m=sqrt(N)+1$$, а $$k=4$$.

На самом деле мы всё ещё «решаем не ту задачу», потому что находим все решения, а не одно — первое попавшееся. Поскольку в Си нет удобного способа выйти сразу из всех циклов после нахождения первого же сочетания, проще всего оформить весь алгоритм в виде функции. Другой вариант — ввести дополнительное условие в цикл.

 1  #include  2    3  void main()  4  int N, x, y, z, t, todo;  5    6  scanf("%d", &N);  7  todo = 1;  8  for(x=1; x*x N && todo; x++)  9  for(y=0; y x && todo; y++)  10  for(z=0; z y && todo; z++)  11  for(t=0; t z && todo; t++)  12  todo = x*x+y*y+z*z+t*t != N;  13  x--; y--; z--; t--;  14  printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N);  15  > 
  • условие выхода формируется и записывается в переменную todo, а сам условный оператор оказался не нужен;
  • все слагаемые увеличились на 1 перед проверкой условия, так что эту единицу пришлось из них вычесть.

В дальнейшем мы для простоты переключимся на задачу поиска всех решений: метод превращения её решения в решение задачи «поиск первого» нам уже известен.

Между тем алгоритм всё ещё остаётся сильно избыточным. Чтобы в этом убедиться, добавим вывод x,y,z и t в предпоследнюю программу.

 1  #include  2    3  void main()  4  int N, x, y, z, t;  5  long int loops = 0;  6    7  scanf("%d", &N);  8  for(x=1; x*x N; x++)  9  for(y=0; y x; y++)  10  for(z=0; z y; z++)  11  for(t=0; t z; t++)  12  loops++;  13  printf("%2d %2d %2d %2d\n", x, y, z, t);  14  if(x*x+y*y+z*z+t*t == N)  15  printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N);  16  >  17  printf("%ld\n", loops);  18  > 

Вот что получится для числа 10:

10 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 2 0 0 0 2 1 0 0 2 1 1 0 2 1 1 1 2 2 0 0 2 2 1 0 2 2 1 1 2²+2²+1²+1²=10 2 2 2 0 2 2 2 1 2 2 2 2 3 0 0 0 3 1 0 0 3²+1²+0²+0²=10 3 1 1 0 3 1 1 1 3 2 0 0 3 2 1 0 3 2 1 1 3 2 2 0 3 2 2 1 3 2 2 2 3 3 0 0 3 3 1 0 3 3 1 1 3 3 2 0 3 3 2 1 3 3 2 2 3 3 3 0 3 3 3 1 3 3 3 2 3 3 3 3 35

Изрядная часть строк в начале, и ещё большая — в конце — представляют собой набор чисел, которые вообще не могут быть решением. В самом деле, если «3 1 0 0» — решение, то все последующие сочетания («3 1 1 0», «3 1 1 1», «3 2 0 0» и т. д.) проверять вообще не надо: сумма их квадратов заведомо больше.

Разберёмся с этим путём отсечения заведомо неподходящих частей цикла (пока только некоторых).

 1  #include  2    3  void main()  4  int N, x, y, z, t;  5  long int loops = 0;  6    7  scanf("%d", &N);  8  for(x=1; x*x N; x++)  9  for(y=0; y x && x*x+y*y N; y++)  10  for(z=0; z y && x*x+y*y+z*z N; z++)  11  for(t=0; t z && x*x+y*y+z*z+t*t N; t++)  12  loops++;  13  if(x*x+y*y+z*z+t*t == N)  14  printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N);  15  >  16  printf("%ld\n", loops);  17  > 

Оценка сложности улучшилась, хотя и не слишком радикально (20: 70 → 32, 10000: 4598126 → 1426253, 100000: 428761520 → 132866304, т. е. при больших N раза в три).

Дело в том, что мы всё ещё рассматриваем «ненужные» варианты слагаемых — на этот раз только те, чьи суммы квадратов заведомо меньше N. Рассмотрим наш пример для числа 10. Если «2 1 1 1» не является решением в силу того, что сумма квадратов этих чисел меньше 10, то не являются решениями и «2 1 1 0», «2 1 0 0» и другие предыдущие сочетания алгоритме.

И вот тут мы подходим к самому интересному месту рассуждений. А как вообще сделать так, чтобы не проверять в цикле ненужные предыдущие сочетания?

Очевидно, недостаточно одной проверки, а не получился ли у нас такой кандидат в решения, после которого поиск не имеет смысла. Верхнюю и нижнюю границы такого набора надо научиться вычислять (или подбирать по предыдущему набору).

Поможет в этом следующее соображение. Будем обозначать целую часть некоторого $$k$$ в виде $$|__k__|$$. Если $$N$$ — полный квадрат, то «$$sqrt(N)$$ 0 0 0» — правильный ответ. Если нет, то всё равно $$x$$ не может быть больше $$sqrt(N)$$, потому что $$(|__sqrt(N)__|+1)^2>N$$. А каково наименьшее возможное значение $$x$$? Вспомним, что в наиболее эффективном алгоритме (выдающем ровно одно размещение из нескольких возможных) x, y, z, t нестрого упорядочены по убыванию. Следовательно, если $$x$$ настолько мало, что $$4x^2

Это даёт нам нижнюю оценку для $$x$$: $$x>=sqrt(N)/4$$.

  1. $$(sqrt(N))/4
  2. $$(sqrt(N-x^2))/3
  3. $$(sqrt(N-x^2-y^2))/2
  4. $$sqrt(N-x^2-y^2-z^2)

Последнее неравенство примечательно. Если немного подумать, станет очевидно, что внутренний цикл — лишний: если x, y и z уже посчитаны, единственное t, которое надо проверить — это $$|__sqrt(N-x^2-y^2-z^2)__|$$. Иначе говоря, ответ есть только когда $$N-x^2-y^2-z^2$$ — это полный квадрат, не превосходящий $$z^2$$ (чтобы не нарушать порядок).

Получившееся решение (с верхними и нижними границами слагаемых) выглядит так:

 1  #include  2  #include  3    4  void main()  5  int N, x, y, z, t;  6  long int loops = 0;  7    8  scanf("%d", &N);  9  for(x=(int)(sqrt(N)/4); x*x N; x++)  10  for(y=(int)(sqrt((N-x*x))/3); y x && x*x+y*y N; y++)  11  for(z=(int)(sqrt((N-x*x-y*y))/2); z y && x*x+y*y+z*z N; z++)  12  if(N-x*x-y*y-z*z z*z)  13  loops++;  14  t=(int)(sqrt(N-x*x-y*y-z*z));  15  if(x*x+y*y+z*z+t*t == N)  16  printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N);  17  >  18  printf("%ld\n", loops);  19  > 

Хотелось бы поточнее оценить сложность этого алгоритма, потому что она невероятно понизилась! В самом деле:

  • 20: 70 → 32 → 3
  • 10000: 4598126 → 1426253 → 7442
  • 100000: 428761520 → 132866304 → 229493
  • <!>» width=»16″ height=»16″ /> 1000000: 7194448</li>
<li><img decoding=%d", &N); 8 for(x=1; (x+1)*(x+1) < N/4; x++); 9 for(; x*x N; x++) 10 for(y=0; (y+1)*(y+1) < (N-x*x)/3; y++); 11 for(; y x && x*x+y*y N; y++) 12 for(z=0; (z+1)*(z+1) < (N-x*x-y*y)/2; z++); 13 for(; zy && x*x+y*y+z*z N; z++) 14 if(N-x*x-y*y-z*z z*z) 15 loops++; 16 for(t=0; (t+1)*(t+1) < (N-x*x-y*y-z*z); t++); 17 if(x*x+y*y+z*z+t*t == N) 18 printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N); 19 > 20 > 21 > 22 printf("%ld\n", loops); 23 >

    Избавляться от вещественной арифметики надо не только потому, что она медленная, но и потому, что она не по-настоящему вещественная. В самом деле, не всякий алгоритм вычисления квадратного корня гарантирует, что $$sqrt(100)$$ — это $$10.0$$, а не $$9.99999(9)…$$, ведь это одинаковые вещественные числа. Однако преобразование (int) вполне способно превратить 10.0 в 10, а 9.9999999 — в 9.

    • Для $$x=k$$: $$y^2=(N-k^2)/3=N/3-k^2/3$$
    • Для $$x=k+1$$: $$y^2=(N-(k+1)^2)/3=N/3-k^2/3-2k/3-1/3=m-(2k+1)/3$$

    Осталось придумать, откуда начинать подбор внутренних переменных y, z и t перед самым первым запуском цикла, а также когда значение внешних переменных (y и z соответственно) скачкообразно меняется на следующем витке более внешнего цикла (по x и по y).

    Поскольку подбор теперь идёт в убывающую сторону, можно начать со значения соответствующей внешней переменной:

     1  #include  2    3  void main()  4  int N, x, y, z, t;  5  int miny, minz;  6  long int loops = 0;  7    8  scanf("%d", &N);  9  for(x=1; x*x*4 < N; x++);  10  for(miny=x; x*x N; x++)  11  while(miny && (miny-1)*(miny-1)*3 >= N-x*x) miny--;  12  for(y=minz=miny; y x && x*x+y*y N; y++)  13  while(minz && (minz-1)*(minz-1)*2 >= N-x*x-y*y) minz--;  14  for(z=t=minz; z y && x*x+y*y+z*z N; z++)  15  while(t*t > N-x*x-y*y-z*z) t--;  16  loops++;  17  if(x*x+y*y+z*z+t*t == N)  18  printf("%d²+%d²+%d²+%d² = %d\n", x, y, z, t, N);  19  >  20  >  21  >  22  printf("%ld\n", loops);  23  > 

    пришлось дополнительно отследить нулевые значения переменных на случай, когда левая часть неравенства вида $$2(minz-1)^2>=N-x^2-y^2$$ увеличится после уменьшения $$minz$$.

    FrBrGeorge/News/2017-02-01 (последним исправлял пользователь FrBrGeorge 2017-02-02 16:05:54)

    • Неизменяемая страница
    • Комментарии
    • Информация
    • Прикреплённые файлы
    • Content license
    • MoinMoin Powered
    • Python Powered
    • GPL licensed
    • Page.execute = 0.283s
    • Page.execute|1 = 0.207s
    • getACL = 0.026s
    • i18n_init = 0.043s
    • init = 0.044s
    • loadLanguage = 0.002s
    • load_multi_cfg = 0.039s
    • run = 0.718s
    • send_page = 0.692s
    • send_page_content = 0.395s
    • send_page_content|1 = 0.249s
    • send_page|1 = 0.260s
    • total = 0.762s

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *