Four Squares Reborn

Agnishom · 2014-02-28 02:25:10

Problem
You need to find (at most) 20 ways of representing a natural number as a sum of (at most) four perfect squares.

Details
The number can be upto 10 digits large.

Last edited by Agnishom (2014-02-28 02:26:03)

bobbym · 2014-02-28 02:32:27

Hi;

You want 20 instances of a 10 digit number represented as 4 squares? For instance:

22077^2+20975^2+15106^2+8890^2=1234567890

you want 19 more like that?

A first effort with M:

square4[n_] := 
 Block[{ans}, 
  ans = FindInstance[a^2 + b^2 + c^2 + d^2 == n, {a, b, c, d}, 
      Integers, RandomSeed -> #]& /@ Range[20];
  ans = Union[Flatten[ans, 1]];
  If[Length[ans] == 20, {a, b, c, d} /. ans]]

Run square[7777777777]

Agnishom · 2014-02-28 04:11:30

In[1]:= square4[n_] := 
 Block[{ans},
  ans = FindInstance[a^2 + b^2  + c^2  + d^2 == n, {a, b, c, d},
      Integers, RandomSeed -> #] & /@ Range[20];
  ans = Union[Flatten[ans, 1]];
  If [Length[ans] == 20, {a, b, c, d} /. ans]]

In[3]:= square4[7777777777]

Out[3]= {{19490, 10320, 82626, 21549}, {31912, 9596, 75889, 
  30136}, {34436, 11990, 57866, 55675}, {38076, 31252, 72801, 
  7164}, {41376, 32166, 69642, 13459}, {45004, 554, 55403, 
  51794}, {45904, 9556, 74332, 7351}, {49972, 41088, 58680, 
  12207}, {51066, 27024, 50026, 44013}, {51074, 17822, 67096, 
  18701}, {55912, 198, 54798, 40605}, {56524, 50588, 43496, 
  11479}, {58572, 30254, 58581, 246}, {60124, 31236, 45207, 
  33816}, {61456, 3434, 58477, 23866}, {61554, 21900, 54806, 
  22485}, {64216, 44750, 29539, 27910}, {66136, 12574, 49501, 
  28202}, {70574, 3300, 46635, 24726}, {84902, 18774, 14724, 411}}

Works!

A Windoze 8 laptop is downloading tons of data whenever I connect it. How do I immediately stop this?

bobbym · 2014-02-28 04:18:03

Very good!. Do you see why it is only a first effort?

Also, please wrap a Timing command around fubar.

Agnishom · 2014-02-28 04:39:45

What is the secret behind Mathematica's FindInstance command?

bobbym · 2014-02-28 04:44:00

It is the most powerful command that can be had. It uses all known algorithms to answer and solve many, many questions. But you have not answered the question.

Agnishom · 2014-02-28 05:01:36

In[8]:= ClearSystemCache[]; Timing[fubar[7777777777];]

Out[8]= {0.499203, Null}

How do I program this without a mathematical software?

bobbym · 2014-02-28 05:05:31

A greedy algorithm is probably okay.

But you did see that this is only a first effort. Do you see the one procedural construct in it at the end?

Agnishom · 2014-02-28 05:16:30

No??

bobbym · 2014-02-28 05:20:30

If [Length[ans] == 20, {a, b, c, d} /. ans]

An if then statement is a procedural statement. This one says if Length of the answer so far is 20 then print it ( among other things ). fubar assumes that it will always return 20 answers but that is unknown. There may be inputs that do not return 20 answers!

Agnishom · 2014-02-28 05:35:46

I do not quite see what is wrong with it.

What is this: RandomSeed -> #]& /@ Range[20];

bobbym · 2014-02-28 05:41:36

That is tough to understand at first. It just gets 20 random seeds for FindInstance.

gAr · 2014-02-28 18:38:50

In[8]:= ClearSystemCache[]; Timing[fubar[7777777777];]

Out[8]= {0.499203, Null}

And it took 4.37s in raspbian VM, not bad I think.

Agnishom · 2014-03-01 02:37:32

bobbym wrote:

That is tough to understand at first.

Please explain anyway

bobbym · 2014-03-01 02:39:12

Do you know what the Range command does?

Agnishom · 2014-03-01 02:42:08

no

bobbym · 2014-03-01 02:43:54

Okay, did you notice there are no loops in my function?

The reason is functional languages have no need for loops. Commands work on and create whole lists at a time.

Range[10] would produce {1,2,3,4,5,6,7,8,9,10} search the help to see all the options.

Agnishom · 2014-03-01 04:07:13

But internally, they are programmed through loops. Aren't they?

bobbym · 2014-03-01 04:10:45

I do not know and probably that might be true. But as a high level language the user is taken away from that mode of thinking and brought into a different paradigm. Mind you, the less C++, Basic, Fortran, Pascal, etc you know the better off you are when trying to get into a functional world. That is a personal opinion but I have seen it to be true.

Agnishom · 2014-03-01 04:13:58

Why should it be a personal opinion? M is optimised for functional programming and I think you are correct and I should think in a Functional approach when programming in M.

bobbym · 2014-03-01 04:15:38

My opinion was this, the more you know of those languages the harder it will be to switch.

Agnishom · 2014-03-01 05:01:22

Okay, that is a personal opinion. I will not comment on it.

bobbym · 2014-03-01 05:02:15

It can not be helped either. Did you get the Range command?

Agnishom · 2014-03-01 17:32:16

Hmm, yes

bobbym · 2014-03-01 17:58:24

How do you get the first 100 squares with your favorite language?

Math Is Fun Forum

#1 2014-02-28 02:25:10

Four Squares Reborn

#2 2014-02-28 02:32:27

Re: Four Squares Reborn

#3 2014-02-28 04:11:30

Re: Four Squares Reborn

#4 2014-02-28 04:18:03

Re: Four Squares Reborn

#5 2014-02-28 04:39:45

Re: Four Squares Reborn

#6 2014-02-28 04:44:00

Re: Four Squares Reborn

#7 2014-02-28 05:01:36

Re: Four Squares Reborn

#8 2014-02-28 05:05:31

Re: Four Squares Reborn

#9 2014-02-28 05:16:30

Re: Four Squares Reborn

#10 2014-02-28 05:20:30

Re: Four Squares Reborn

#11 2014-02-28 05:35:46

Re: Four Squares Reborn

#12 2014-02-28 05:41:36

Re: Four Squares Reborn

#13 2014-02-28 18:38:50

Re: Four Squares Reborn

#14 2014-03-01 02:37:32

Re: Four Squares Reborn

#15 2014-03-01 02:39:12

Re: Four Squares Reborn

#16 2014-03-01 02:42:08

Re: Four Squares Reborn

#17 2014-03-01 02:43:54

Re: Four Squares Reborn

#18 2014-03-01 04:07:13

Re: Four Squares Reborn

#19 2014-03-01 04:10:45

Re: Four Squares Reborn

#20 2014-03-01 04:13:58

Re: Four Squares Reborn

#21 2014-03-01 04:15:38

Re: Four Squares Reborn

#22 2014-03-01 05:01:22

Re: Four Squares Reborn

#23 2014-03-01 05:02:15

Re: Four Squares Reborn

#24 2014-03-01 17:32:16

Re: Four Squares Reborn

#25 2014-03-01 17:58:24

Re: Four Squares Reborn

Board footer