Number as sum of two squares

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
40:58:46
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

savinov's blog

Number as sum of two squares

By savinov, 13 years ago, translation, In English

Hi, everybody! Recently, I tried to solve a problem. In this problem I had to determine, is number N sum of two squares? i.e. N = a² + b²?, where a and b are integer. N < 10¹⁵. Firstly, I tried to brute-force a and check N - a² for a square, but got TL. Also I tried to factorize the number and check degree of prime divisors p = 4k + 3 and used Fermat-Euler theorem to check the fact. But also I got TL. I suppose this problem to solve with number of operations $\text{[math]}$ . And I'm interested in technical realization of it. Can anybody show how to write accurate brute-force or factorization for example on C/C++? And what advices can you give to write same programs, making as less operations as possible? It's the problem from acm.timus.ru link here Thanks in advance!

number theory, realization

savinov
13 years ago
23

Comments (22)

Show archived | Write comment?

wil93

13 years ago, # |

How can you use an algorithm that checks N = a²+b² in the problem you linked? It asks for the minimum number of squares that sum to N, am I right?

→ Reply

ibra

13 years ago, # ^ |

a little hint

http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem

→ Reply

Tranvick

13 years ago, # ^ |

← Rev. 3 →

+10

Any natural number can be represented as the sum of four integer squares. We check that N = a². If not, we check that N = a² + b². If this is not correct, we check that N = a² + b² + c². And the answer is 4, if this is also not correct.

→ Reply

Kostroma

13 years ago, # ^ |

+14

how can we check if N can be represented as a sum of three squares fast?

→ Reply

niklasb

13 years ago, # ^ |

← Rev. 2 →

The following question on MathOverflow might help: http://mathoverflow.net/questions/57981/testing-whether-an-integer-is-the-sum-of-two-squares

EDIT: Sorry, I misread your comment :)

→ Reply

OSt

13 years ago, # ^ |

← Rev. 2 →

-15

IMHO, in that problem more easy to check if N can be represented as sum of 1,2,4 squares. Else — 3. :-)

→ Reply

afix

13 years ago, # ^ |

← Rev. 2 →

27 = 1*1 + 1*1 + 3*3 + 4*4 = 1*1 + 1*1 + 5*5
27 != a*a
27 != a*a + b*b
Fail.

→ Reply

OSt

13 years ago, # ^ |

if N != (8*t+7)*4^k then there are 3 squares.

→ Reply

Kostroma

13 years ago, # ^ |

← Rev. 3 →

oh, don't you know the proof or some link with the proof?

→ Reply

riadwaw

13 years ago, # ^ |

+13

And now read your previos explanation.

→ Reply

Kostroma

13 years ago, # ^ |

← Rev. 3 →

-8

sorry, I've misunderstood you

→ Reply

Tranvick

13 years ago, # ^ |

int three_square(ll x){
	while (!(x&3)) x>>=2;
	return (x+1)%8;
}

It returns 0, if x is not a sum of three squares.

→ Reply

CherryTree

13 years ago, # ^ |

How come?

→ Reply

Tranvick

13 years ago, # ^ |

This is a very difficult method of pen and paper :)

→ Reply

wil93

13 years ago, # ^ |

I think that algorithm follows this: http://www.proofwiki.org/wiki/Integer_as_Sum_of_Three_Squares

→ Reply

jaineshp

9 years ago, # ^ |

-12

For sum of two squares, how can it be modified?

→ Reply

ha1vanka

9 years ago, # ^ |

+29

Don't answer him. This is one of the problems from a running contest.

→ Reply

jaineshp

9 years ago, # ^ |

-14

Sorry?

→ Reply

I_will_win_a_div1_round

9 years ago, # ^ |

-27

Motori

→ Reply

red_coder

13 years ago, # |

← Rev. 2 →

according to me we can run a loop in which 'i' goes from 1 to sqrt(N/2) and if N-i*i is a perfect square we are done....

for(int i=1; i*i<=N/2; i++) { if((N-i*i) is a perfect square) done; }

its complexity is O(sqrt(N)).....

→ Reply

savinov

13 years ago, # ^ |

How do you check number for square? I did the same and used sqrt() and got TL.

→ Reply

Oi.

13 years ago, # |

An arbitrary positive number n is expressible as the sum of two squares iff, given its prime factorization

n=p1^(a1)p2^(a2)p3^(a3)...pk^(ak),

none of pi^(ai) +1 is divisible by 4 (Conway and Guy 1996, p. 147). http://mathworld.wolfram.com/SquareNumber.html

→ Reply