Number Theory

Test LaTeX, in general, test posting messages here. All the messages of this test forum will be deleted after a few days.
Ayan
Posts:1
Joined:Tue Mar 09, 2021 9:51 pm
Number Theory

Unread post by Ayan » Fri Jul 16, 2021 12:37 pm

Question:- How many numbers are there between 1 to 1000 which can be expressed by the difference of two square numbers?

Pls help to solve it.i have used brute force but getting wrong answer:(
Here is my Code in C++

The output is 327,as there is repetition i have used set to store the unique numbers only.

#include<iostream>
using namespace std;
int main()
{
int a[32];
set<int>s;
for(int i = 1;i <= 31;i++){
a=i*i;
}

for(int i = 1;i <= 30;i++){
for(int j = i+1;j <= 31;j++){
s.insert(abs(a-a[j]));
cout<<abs(a-a[j])<<endl;
}
}
cout << s.size() <<endl;
}
}

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Number Theory

Unread post by Anindya Biswas » Sat Jul 17, 2021 3:30 pm

If you want to post about programming or other computer science related topic, you should post here.
For number theory, post here.

Every odd number is difference of two squares, $2n+1=(n+1)^2-n^2$

Every even number that's divisible by $4$ is difference of two squares, $4n=(n+1)^2-(n-1)^2$.

Every number of the form $4n+2$ can't be a difference of two squares, for the sake of contradiction, let's assume,
$4n+2=a^2-b^2=(a+b)(a-b)$
Now, $a+b\equiv a-b\pmod{2}$
So, $a+b,a-b$ both must be even. Therefore, $4\mid (a+b)(a-b)$.
But $4\nmid 4n+2$, which is a contradiction.

So, use this code instead,

Code: Select all

include <iostream>
include <cmath>

using namespace std;

int main()
{
	int n=1000;
	int a=ceil(n/2);
	int b=floor(n/4);
	return a+b;
}
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply