Как найти сумму квадратов первых целых чисел - Исправление недочетов и поиск решений вместе с Examum.ru

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given a positive integer n. The task is to find the sum of the sum of square of first n natural number.
Examples :

Input : n = 3
Output : 20
Sum of square of first natural number = 1
Sum of square of first two natural number = 1^2 + 2^2 = 5
Sum of square of first three natural number = 1^2 + 2^2 + 3^2 = 14
Sum of sum of square of first three natural number = 1 + 5 + 14 = 20

Input : n = 2
Output : 6

Method 1: O(n) The idea is to find sum of square of first i natural number, where 1 <= i <= n. And then add them all.
We can find sum of squares of first n natural number by formula: n * (n + 1)* (2*n + 1)/6
Below is the implementation of this approach:

C++

#include <bits/stdc++.h>

using namespace std;

int findSum(int n)

{

int sum = 0;

for (int i = 1; i <= n; i++)

sum += ((i * (i + 1) * (2 * i + 1)) / 6);

return sum;

}

int main()

{

int n = 3;

cout << findSum(n) << endl;

return 0;

}

Java

class GFG {

static int findSum(int n)

{

int sum = 0;

for (int i = 1; i <= n; i++)

sum += ((i * (i + 1)

* (2 * i + 1)) / 6);

return sum;

}

public static void main(String[] args)

{

int n = 3;

System.out.println( findSum(n));

}

Python3

def findSum(n):

summ = 0

for i in range(1, n+1):

summ = (summ + ((i * (i + 1)

* (2 * i + 1)) / 6))

return summ

n = 3

print(int(findSum(n)))

C#

using System;

public class GFG {

static int findSum(int n)

{

int sum = 0;

for (int i = 1; i <= n; i++)

sum += ((i * (i + 1) *

(2 * i + 1)) / 6);

return sum;

}

static public void Main()

{

int n = 3;

Console.WriteLine(findSum(n));

}

PHP

<?php

function findSum( $n)

{

$sum = 0;

for ($i = 1; $i <= $n; $i++)

$sum += (($i * ($i + 1) *

(2 * $i + 1)) / 6);

return $sum;

}

$n = 3;

echo findSum($n) ;

?>

Javascript

<script>

function findSum(n)

{

return (n * (n + 1) * (n + 1) * (n + 2)) / 12;

}

let n = 3;

document.write(findSum(n) + "<br>");

</script>

Time Complexity : O(n)
Auxiliary Space : O(1)
Method 2: O(1)
Mathematically, we need to find, Σ ((i * (i + 1) * (2*i + 1)/6), where 1 <= i <= n
So, lets solve this summation,

Sum = Σ ((i * (i + 1) * (2*i + 1)/6), where 1 <= i <= n
    = (1/6)*(Σ ((i * (i + 1) * (2*i + 1)))
    = (1/6)*(Σ ((i² + i) * (2*i + 1))
    = (1/6)*(Σ ((2*i³ + 3*i² + i))
    = (1/6)*(Σ 2*i³ + Σ 3*i² + Σ i)
    = (1/6)*(2*Σ i³ + 3*Σ i² + Σ i)
    = (1/6)*(2*(i*(i + 1)/2)² + 3*(i * (i + 1) * (2*i + 1))/6 + i * (i + 1)/2)
    = (1/6)*(i * (i + 1))((i*(i + 1)/2) + ((2*i + 1)/2) + 1/2)
    = (1/12) * (i * (i + 1)) * ((i*(i + 1)) + (2*i + 1) + 1)
    = (1/12) * (i * (i + 1)) * ((i² + 3 * i + 2)
    = (1/12) * (i * (i + 1)) * ((i + 1) * (i + 2))
    = (1/12) * (i * (i + 1)² * (i + 2))

Below is the implementation of this approach:

C++

#include <bits/stdc++.h>

using namespace std;

int findSum(int n)

{

return (n * (n + 1) * (n + 1) * (n + 2)) / 12;

}

int main()

{

int n = 3;

cout << findSum(n) << endl;

return 0;

}

Java

class GFG {

static int findSum(int n)

{

return (n * (n + 1) *

(n + 1) * (n + 2)) / 12;

}

public static void main(String[] args)

{

int n = 3;

System.out.println(findSum(n) );

}

Python3

def findSum(n):

return ((n * (n + 1) * (n + 1)

* (n + 2)) / 12)

n = 3

print(int(findSum(n)))

C#

using System;

class GFG {

static int findSum(int n)

{

return (n * (n + 1) * (n + 1)

* (n + 2)) / 12;

}

static public void Main()

{

int n = 3;

Console.WriteLine(findSum(n) );

}

PHP

<?php

function findSum($n)

{

return ($n * ($n + 1) *

($n + 1) * ($n +

2)) / 12;

}

$n = 3;

echo findSum($n) ;

?>

Javascript

<script>

function findSum($n)

{

return (n * (n + 1) *(n + 1) * (n + 2)) / 12;

}

n = 3;

document.write(findSum(n)) ;

</script>

Time Complexity : O(1)
Auxiliary Space : O(1)

Last Updated :
24 Dec, 2022

Like Article

Save Article

Источник

Онлайн калькуляторы

Calculatorium.ru — это бесплатные онлайн калькуляторы для самых разнообразных целей: математические калькуляторы,
калькуляторы даты и времени, здоровья, финансов. Инструменты для работы с текстом. Конвертеры. Удобное решение различных задач — в учебе, работе, быту.

Актуальная информация

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

Источник

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

Задача поиска суммы квадратов чисел — это классический пример упражнения для закрепления школьниками или студентами раздела программирования Циклы.

Условие задачи: Найти сумму квадратов первых N натуральных чисел.

Рассмотрим два различных способа (алгоритма) решения.

Вычисление суммы квадратов чисел с использованием операции умножения

Первый и самый очевидный способ решения — суммирование в отдельную переменную квадратов числа i в цикле от i = 1 до N.

Приведем алгоритм вычисления суммы квадратов первых N натуральных чисел на псевдокоде:

begin

sum := 0;

for i := 1 to n do

begin

j := i * i;

sum := sum + j;

end

Вывод sum;

end

Поясним код. Сначала объявляется переменная sum = 0 (строка 2) — в неё мы будем суммировать вычисленные квадраты натурального числа i. Затем в цикле for от 1 до N (строки 3-7) производится вычисление квадрата числа i и сохранение вычисленного результата в переменную j (строка 5), а после j прибавляется к sum (строка 6). В конце, когда все итерации цикла for будут выполнены — вычисление суммы будет завершено. Результат можно вывести на экран (строка или сохранить для дальнейшего использования.

Ниже представлена реализация алгоритма, написанного на псевдокоде. Данный код вы можете использовать при программировании на языках C (Си), C++, C#, Java. Всё будет работать.

int n = 3;

int sum = 0;

for (int i = 1; i <= n; i++)

{

int j = i * i;

sum = sum + j;

}

Шестую и седьмую строчки можно заменить одним эквивалентным, более компактным и удобным оператором:

Используя его, мы также избавляемся от необходимости объявления дополнительной переменной j.

Вычисление суммы квадратов чисел без использования операции умножения

Второй способ поиска суммы квадратов первых N натуральных чисел довольно своеобразен: он более громоздкий, чем первый, но зато имеет свою особенность.

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

int n = 3;

int k = 1;

int l = 0;

int sum = 0;

while (k < (n + n))

{

l = l + k;

sum = sum + l;

k = k + 2;

}

Спасибо за прочтение статьи!

Источник

10 / 9 / 4

Регистрация: 02.10.2016

Сообщений: 62

11.10.2016, 12:24. Показов 111909. Ответов 9

Формула есть $https://www.cyberforum.ru/cgi-bin/latex.cgi?{1}^{2}+{2}^{2}+{3}^{2}+[...]+{n}^{2}=frac{n(n+1)(2n+1)}{6}$
Подскажите как ее можно вывести, чтобы как говорится «не с потолка взял»?

543 / 486 / 104

Регистрация: 05.05.2014

Сообщений: 1,110

11.10.2016, 12:36

Диссидент

27483 / 17170 / 3784

Регистрация: 24.12.2010

Сообщений: 38,683

11.10.2016, 13:50

Сообщение было отмечено echs как решение

Решение

Соображения размерности подсказывают, что скорее всего сумма будет описываться кубическим многочленом.
Общий вид у него такой: S = An³ + Bn² + Cn + D
Подставляем n = 0 S = 0, n=1 S=1, n=2 S=5 n=3 S=14
Получаем 4 уравнения с 4-мя неизвестными. Но потом, конечно, надо проверить индукцией.

Регистрация: 23.10.2013

Сообщений: 5,076

Записей в блоге: 8

11.10.2016, 16:19

доказать, что
$https://www.cyberforum.ru/cgi-bin/latex.cgi?1^2+2^2+ ... +n^2=frac{n(n+1)(2n+1)}{6}$

доказательство методом математической индукции

шаг 1. при n = 1 имеем $https://www.cyberforum.ru/cgi-bin/latex.cgi?1^2=frac{1(1+1)(2*1+1)}{6}=1$ (верно)

шаг 2.
допустим, что наша формула верна при n = k, то есть
$https://www.cyberforum.ru/cgi-bin/latex.cgi?1^2+2^2+ ... +k^2=frac{k(k+1)(2k+1)}{6}$
и докажем, что она верна при n = k + 1
имеем

$https://www.cyberforum.ru/cgi-bin/latex.cgi?1^2+2^2+ ... +k^2+(k+1)^2=frac{k(k+1)(2k+1)}{6}+(k+1)^2=frac{(k+1)(2k^2+7k+6)}{6}=$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?frac{(k+1)(k+2)(2k+3)}{6}=frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$

что и требовалось доказать

10 / 9 / 4

Регистрация: 02.10.2016

Сообщений: 62

11.10.2016, 17:07

[ТС]

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

Регистрация: 23.10.2013

Сообщений: 5,076

Записей в блоге: 8

11.10.2016, 18:14

Выше уважаемый Байт указал путь по которому
выводится эта формула. Напишем эту систему уравнений
S = An³ + Bn² + Cn + D
…
D = 0
A + B + C + D = 1
8A + 4B + 2C + D = 5
27A + 9B+ 3C + D = 14
далее
A + B + C = 1
8A + 4B + 2C = 5
27A + 9B + 3C = 14
вычтем первое уравнение помноженное на 2 из второго
и первое уравнение помноженное на 3 из третьего
A + B + C = 1
6A + 2B = 3
24A + 6B = 11
вычтем второе уравнение помноженное на 3 из третьего
A + B + C = 1
6A + 2B = 3
6A = 2
решая эту систему получим
A = 1/3
B = 1/2
C = 1/6
D = 0
подставляя найденные значения в самое верхнее выражение
получим
S = (1/3)n³ + (1/2)n² + (1/6)n
это и есть искомая формула
(приведите ее к общему знаменателю, да разложите на множители)

Диссидент

27483 / 17170 / 3784

Регистрация: 24.12.2010

Сообщений: 38,683

11.10.2016, 18:21

Сообщение от echs

уважаемый Байт указал путь по которому выводится эта формула.

Должен признаться, что этот путь не самый лучший. В ссылке, приведенной уважаемым 8-BITOV в посте 2, рассматривается значительно более интересный и поучительный подход…

Регистрация: 23.10.2013

Сообщений: 5,076

Записей в блоге: 8

11.10.2016, 19:04

Байт
Вы предложили решение, которое проще, чем у Архимеда.
Кроме того можно написать программу, которая будет
выводить эти формулы в виде многочленов. Так, что
Самый лучший ответ я передам Вам!
я лишь реализовал сказанное Вами…

6354 / 4062 / 1510

Регистрация: 09.10.2009

Сообщений: 7,550

Записей в блоге: 4

12.10.2016, 02:11

Можно вывести, и не доказывать по индукции. Для этого нужно знать суммы всех степеней натуральных чисел, меньших чем 2, т.е. сумму арифметической прогрессии 1+2+3+…+n
Запишем такие кубы:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?left(0+1 right)^3=0^3+3 cdot 0^2 cdot 1+3 cdot 0 cdot 1^2+1^3\left(1+1 right)^3=1^3+3 cdot 1^2 cdot 1+3 cdot 1 cdot 1^2+1^3\left(2+1 right)^3=2^3+3 cdot 2^2 cdot 1+3 cdot 2 cdot 1^2+1^3\....................................................................\left(n+1 right)^3=n^3+3 cdot n^2 cdot 1+3 cdot n cdot 1^2+1^3$
Дальше складываем левые части между собой и правые. При этом происходит взаимное уничтожение левых кубов, кроме последнего, и правых первых слагаемых, кроме первого. Получаем в результате
,
откуда ваша сумма равна
$https://www.cyberforum.ru/cgi-bin/latex.cgi?frac{left(n+1 right)^3-left(n+1 right)-3frac{nleft(n+1 right)}{2}}{3}=frac{left(n+1 right)left(2n^2+4n+2-2-3n right)}{6}=frac{left(n+1 right)left(2n^2+nright)}{6}=frac{nleft(n+1 right)(2n+1)}{6}$

3971 / 2950 / 894

Регистрация: 19.11.2012

Сообщений: 6,063

12.10.2016, 05:45

Сообщение от jogano

Можно вывести, и не доказывать по индукции.

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

Источник

Мой основной вопрос заключается в следующем: как найти сумму квадратов $%n$% первых натуральных чисел?

Мои размышления привели меня к одной интересной теореме: Faulhaber’s formula. Известно, что $%1^k+2^k+ldots+n^k=P_{k+1}(n)$% — полином от $%n$% $%(k+1)$%-й степени (***). Для нашей задачи имеем:
$%1^2+2^2+ldots+n^2=a+bn+cn^2+dn^3.$% Далее решается незамысловатая СЛУ
$$left{
begin{aligned}
0=&a\
1^2=&a+bcdot1+ccdot1^2+dcdot1^3\
1^2+2^2=&a+bcdot2+ccdot2^2+dcdot2^3\
1^2+2^2+3^2=&a+bcdot3+ccdot3^2+dcdot3^3\
end{aligned}
right. $$

Откуда имею $%a=0,,b=frac16,,c=frac12,,d=frac13$%, т.е. $$P_3(n)=frac{n(n+1)(2n+1)}{6}.$$

Мои дополнительные вопросы:

1) А какие вы знаете способы нахождения суммы квадратов $%n$% первых натуральных чисел?

2) Как доказать факт *** ?

Источник