Fdtxjr

Deciphering cause of death?

How to make a list of partial sums using forEach

Isometric embedding of a genus g surface

Difference between shutdown options

Giving feedback to someone without sounding prejudiced

What is this high flying aircraft over Pennsylvania?

Can I say "fingers" when referring to toes?

Personal or impersonal in a technical resume

How to leave product feedback on macOS?

Does the Crossbow Expert feat's extra crossbow attack work with the reaction attack from a Hunter ranger's Giant Killer feature?

Air travel with refrigerated insulin

Sound waves in different octaves

Telemetry for feature health

How to make money from a browser who sees 5 seconds into the future of any web page?

How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?

Animation: customize bounce interpolation

What is the meaning of "You've never met a graph you didn't like?"

Can you identify this lizard-like creature I observed in the UK?

Origin of pigs as a species

Would this string work as string?

Ways of geometrical multiplication

Are Captain Marvel's powers affected by Thanos breaking the Tesseract and claiming the stone?

Why do Radio Buttons not fill the entire outer circle?

Do I have to take mana from my deck or hand when tapping a dual land?

Decomposition into three squares [on hold]

Rabin and Shallit AlgorithmDoes this equation have positive integer solutions?Given f(x), create g(x) so that f(g(x)) = xProving that for every real $x$ there exists $y$ with $x+y^2inmathbbQ$Solving equations with high level exponentsSolve linear $,ax + b = 0$ in $Z_N$3 incrementing buttons, optimal valueif x^2 + 2x - 3 >= 0 then (x <= -3) V (x >= 1)Converting parametric equations with trigonometric functions into Cartesian formMatrix AlgorithmCalculate Additive Value (Tracking Progress From 0 - 100)Prove that for every prime number $| (x^p-1-1) |=p-1$

2

0

$begingroup$

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$

Not really sure how to approach this. Any ideas?

algebra-precalculus elementary-number-theory algorithms sums-of-squares

share|cite|improve this question

edited Mar 17 at 2:05

Martin Sleziak

44.9k10121274

asked Aug 30 '14 at 14:41

Devin MartinDevin Martin

133

$endgroup$

put on hold as off-topic by Carl Mummert, YiFan, jgon, Thomas Shelby, Parcly Taxel Mar 17 at 5:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, YiFan, jgon, Thomas Shelby, Parcly Taxel

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  en.wikipedia.org/wiki/Legendre's_three-square_theorem
  $endgroup$
  – lab bhattacharjee
  Aug 30 '14 at 14:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This is very cool result, Lab!
  $endgroup$
  – Travis
  Aug 30 '14 at 14:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Exactly what Im looking for! But Im having a bit of trouble with the wording. Any chance you can give me a breif synopsis thats less proofy?
  $endgroup$
  – Devin Martin
  Aug 30 '14 at 14:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I discuss Rabin and Shallit's paper on good randomized algorithms for this problem here, and for the related topic of how many ways $n$ might be expressed as the sum of three squares, see this Answer.
  $endgroup$
  – hardmath
  Sep 2 '14 at 7:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Related post on MathOverflow: Efficient computation of integer representation as a sum of three squares
  $endgroup$
  – Martin Sleziak
  Mar 17 at 2:06
  

  
  
  
  

add a comment | 

2

0

$begingroup$

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$

Not really sure how to approach this. Any ideas?

algebra-precalculus elementary-number-theory algorithms sums-of-squares

share|cite|improve this question

edited Mar 17 at 2:05

Martin Sleziak

44.9k10121274

asked Aug 30 '14 at 14:41

Devin MartinDevin Martin

133

$endgroup$

put on hold as off-topic by Carl Mummert, YiFan, jgon, Thomas Shelby, Parcly Taxel Mar 17 at 5:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, YiFan, jgon, Thomas Shelby, Parcly Taxel

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  $begingroup$
  en.wikipedia.org/wiki/Legendre's_three-square_theorem
  $endgroup$
  – lab bhattacharjee
  Aug 30 '14 at 14:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  This is very cool result, Lab!
  $endgroup$
  – Travis
  Aug 30 '14 at 14:48
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Exactly what Im looking for! But Im having a bit of trouble with the wording. Any chance you can give me a breif synopsis thats less proofy?
  $endgroup$
  – Devin Martin
  Aug 30 '14 at 14:54
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I discuss Rabin and Shallit's paper on good randomized algorithms for this problem here, and for the related topic of how many ways $n$ might be expressed as the sum of three squares, see this Answer.
  $endgroup$
  – hardmath
  Sep 2 '14 at 7:19
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Related post on MathOverflow: Efficient computation of integer representation as a sum of three squares
  $endgroup$
  – Martin Sleziak
  Mar 17 at 2:06
  

  
  
  
  

add a comment | 

$begingroup$

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$

Not really sure how to approach this. Any ideas?

algebra-precalculus elementary-number-theory algorithms sums-of-squares

share|cite|improve this question

edited Mar 17 at 2:05

Martin Sleziak

44.9k10121274

asked Aug 30 '14 at 14:41

Devin MartinDevin Martin

133

$endgroup$

share|cite|improve this question

edited Mar 17 at 2:05

Martin Sleziak

44.9k10121274

asked Aug 30 '14 at 14:41

Devin MartinDevin Martin

133

share|cite|improve this question

edited Mar 17 at 2:05

Martin Sleziak

44.9k10121274

asked Aug 30 '14 at 14:41

Devin MartinDevin Martin

133

edited Mar 17 at 2:05

Martin Sleziak

44.9k10121274

edited Mar 17 at 2:05

Martin Sleziak

44.9k10121274

asked Aug 30 '14 at 14:41

Devin MartinDevin Martin

133

asked Aug 30 '14 at 14:41

Devin MartinDevin Martin

133

1 Answer
1

active

oldest

votes

0

$begingroup$

So following from Lab's link we have $$n=x^2+y^2+z^2iff nne4^a(8b+7)$$
Therefore to test we divide by 4 as much as possible at least once. Then subtract 7 and test if it is divisible by 8. If the divisibilities are true then you have a number that can't be represented as such.

---

Algorithm

1. Check divisibility by 4. If it is not divisible then $n$ is such a number.


2. Keep dividing by 4 until it is no longer divisible.


3. Subtract 7.


4. Check divisibility by 8. If it is divisible then $n$ is not such a number else $n$ is such a number.

share|cite|improve this answer

edited Aug 30 '14 at 17:48

answered Aug 30 '14 at 16:01

Ali CaglayanAli Caglayan

3,74873163

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  this is incorrect in your algorithm step 1; I admit, I am having a little trouble following your wording. However, in $4^a (8 b + 7)$ the bounds would be $a geq 0, b geq 0.$ In particular, $7$ and $15$ are not sums of three squares, easy to confirm with pencil and paper.
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 17:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @WillJagy Unfortunately what I wrote was not what I was thinking. Let me fix this.
  $endgroup$
  – Ali Caglayan
  Aug 30 '14 at 17:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  your profile mentions programming, i suggest you write a simple triple loop program to find the three-square-sums up to, say, $250,$ and print out in order, 10 such numbers per line I guess. After that write a second program for your "algorithm" above, see if you can get the two lists to agree. The nice thing about elementary number theory is that we can write programs and look for patterns in the output. Wow, Everton 3, Chelsea 4, minute 76
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 18:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @WillJagy My answer may not be the best however the OP has accepted it so they must be happy with the information given. I am not too interested in perusing an algorithm.
  $endgroup$
  – Ali Caglayan
  Aug 30 '14 at 18:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  sorry to hear that
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 19:04
  

  
  
  
  

add a comment | 

0

$begingroup$

So following from Lab's link we have $$n=x^2+y^2+z^2iff nne4^a(8b+7)$$
Therefore to test we divide by 4 as much as possible at least once. Then subtract 7 and test if it is divisible by 8. If the divisibilities are true then you have a number that can't be represented as such.

---

Algorithm

1. Check divisibility by 4. If it is not divisible then $n$ is such a number.


2. Keep dividing by 4 until it is no longer divisible.


3. Subtract 7.


4. Check divisibility by 8. If it is divisible then $n$ is not such a number else $n$ is such a number.

share|cite|improve this answer

edited Aug 30 '14 at 17:48

answered Aug 30 '14 at 16:01

Ali CaglayanAli Caglayan

3,74873163

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  this is incorrect in your algorithm step 1; I admit, I am having a little trouble following your wording. However, in $4^a (8 b + 7)$ the bounds would be $a geq 0, b geq 0.$ In particular, $7$ and $15$ are not sums of three squares, easy to confirm with pencil and paper.
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 17:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @WillJagy Unfortunately what I wrote was not what I was thinking. Let me fix this.
  $endgroup$
  – Ali Caglayan
  Aug 30 '14 at 17:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  your profile mentions programming, i suggest you write a simple triple loop program to find the three-square-sums up to, say, $250,$ and print out in order, 10 such numbers per line I guess. After that write a second program for your "algorithm" above, see if you can get the two lists to agree. The nice thing about elementary number theory is that we can write programs and look for patterns in the output. Wow, Everton 3, Chelsea 4, minute 76
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 18:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @WillJagy My answer may not be the best however the OP has accepted it so they must be happy with the information given. I am not too interested in perusing an algorithm.
  $endgroup$
  – Ali Caglayan
  Aug 30 '14 at 18:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  sorry to hear that
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 19:04
  

  
  
  
  

add a comment | 

0

$begingroup$

So following from Lab's link we have $$n=x^2+y^2+z^2iff nne4^a(8b+7)$$
Therefore to test we divide by 4 as much as possible at least once. Then subtract 7 and test if it is divisible by 8. If the divisibilities are true then you have a number that can't be represented as such.

---

Algorithm

1. Check divisibility by 4. If it is not divisible then $n$ is such a number.


2. Keep dividing by 4 until it is no longer divisible.


3. Subtract 7.


4. Check divisibility by 8. If it is divisible then $n$ is not such a number else $n$ is such a number.

share|cite|improve this answer

edited Aug 30 '14 at 17:48

answered Aug 30 '14 at 16:01

Ali CaglayanAli Caglayan

3,74873163

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  this is incorrect in your algorithm step 1; I admit, I am having a little trouble following your wording. However, in $4^a (8 b + 7)$ the bounds would be $a geq 0, b geq 0.$ In particular, $7$ and $15$ are not sums of three squares, easy to confirm with pencil and paper.
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 17:06
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @WillJagy Unfortunately what I wrote was not what I was thinking. Let me fix this.
  $endgroup$
  – Ali Caglayan
  Aug 30 '14 at 17:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  your profile mentions programming, i suggest you write a simple triple loop program to find the three-square-sums up to, say, $250,$ and print out in order, 10 such numbers per line I guess. After that write a second program for your "algorithm" above, see if you can get the two lists to agree. The nice thing about elementary number theory is that we can write programs and look for patterns in the output. Wow, Everton 3, Chelsea 4, minute 76
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 18:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @WillJagy My answer may not be the best however the OP has accepted it so they must be happy with the information given. I am not too interested in perusing an algorithm.
  $endgroup$
  – Ali Caglayan
  Aug 30 '14 at 18:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  sorry to hear that
  $endgroup$
  – Will Jagy
  Aug 30 '14 at 19:04
  

  
  
  
  

add a comment | 

$begingroup$

So following from Lab's link we have $$n=x^2+y^2+z^2iff nne4^a(8b+7)$$
Therefore to test we divide by 4 as much as possible at least once. Then subtract 7 and test if it is divisible by 8. If the divisibilities are true then you have a number that can't be represented as such.

---

Algorithm

1. Check divisibility by 4. If it is not divisible then $n$ is such a number.


2. Keep dividing by 4 until it is no longer divisible.


3. Subtract 7.


4. Check divisibility by 8. If it is divisible then $n$ is not such a number else $n$ is such a number.

share|cite|improve this answer

edited Aug 30 '14 at 17:48

answered Aug 30 '14 at 16:01

Ali CaglayanAli Caglayan

3,74873163

$endgroup$

share|cite|improve this answer

edited Aug 30 '14 at 17:48

answered Aug 30 '14 at 16:01

Ali CaglayanAli Caglayan

3,74873163

answered Aug 30 '14 at 16:01

Ali CaglayanAli Caglayan

3,74873163

answered Aug 30 '14 at 16:01

Ali CaglayanAli Caglayan

3,74873163