savinov's blog

By savinov, 10 years ago, translation,

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 = a2 + b2?, where a and b are integer. N < 1015. Firstly, I tried to brute-force a and check N - a2 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 . 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!

• +7

 » 10 years ago, # |   +5 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?
•  » » 10 years ago, # ^ |   +2
•  » » 10 years ago, # ^ | ← Rev. 3 →   +10 Any natural number can be represented as the sum of four integer squares. We check that N = a2. If not, we check that N = a2 + b2. If this is not correct, we check that N = a2 + b2 + c2. And the answer is 4, if this is also not correct.
•  » » » 10 years ago, # ^ |   +14 how can we check if N can be represented as a sum of three squares fast?
•  » » » » 10 years ago, # ^ | ← Rev. 2 →   0 The following question on MathOverflow might help: http://mathoverflow.net/questions/57981/testing-whether-an-integer-is-the-sum-of-two-squaresEDIT: Sorry, I misread your comment :)
•  » » » » 10 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. :-)
•  » » » » » 10 years ago, # ^ | ← Rev. 2 →   +8 27 = 1*1 + 1*1 + 3*3 + 4*4 = 1*1 + 1*1 + 5*5 27 != a*a 27 != a*a + b*b Fail.
•  » » » » » » 10 years ago, # ^ |   -10 My program output: 3 :-)
•  » » » » » » 10 years ago, # ^ |   0 if N != (8*t+7)*4^k then there are 3 squares.
•  » » » » » » » 10 years ago, # ^ | ← Rev. 3 →   +1 oh, don't you know the proof or some link with the proof?
•  » » » » » » » 10 years ago, # ^ |   +13 And now read your previos explanation.
•  » » » » » 10 years ago, # ^ | ← Rev. 3 →   -8 sorry, I've misunderstood you
•  » » » » 10 years ago, # ^ |   0 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.
•  » » » » » 10 years ago, # ^ |   +5 How come?
•  » » » » » » 10 years ago, # ^ |   0 This is a very difficult method of pen and paper :)
•  » » » » » » 10 years ago, # ^ |   0 I think that algorithm follows this: http://www.proofwiki.org/wiki/Integer_as_Sum_of_Three_Squares
•  » » » » » 6 years ago, # ^ |   -12 For sum of two squares, how can it be modified?
•  » » » » » » 6 years ago, # ^ |   +29 Don't answer him. This is one of the problems from a running contest.
•  » » » » » » » 6 years ago, # ^ |   -14 Sorry?
•  » » » » » » » » 6 years ago, # ^ |   -27 Motori
 » 10 years ago, # | ← Rev. 2 →   0 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)).....
•  » » 10 years ago, # ^ |   0 How do you check number for square? I did the same and used sqrt() and got TL.
 » 10 years ago, # |   0 An arbitrary positive number n is expressible as the sum of two squares iff, given its prime factorizationn=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