flat assembler
Message board for the users of flat assembler.

 Index > Main > can an algorithm be made for this? Goto page Previous  1, 2
Author
ctl3d32

Joined: 30 Dec 2009
Posts: 204
Location: Brazil
ctl3d32
I wonder if the branch and bound algorithm would work here.
01 Dec 2011, 01:00
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Not sure I follow how the BB algo could be used here ctl3d32.
01 Dec 2011, 08:41
ctl3d32

Joined: 30 Dec 2009
Posts: 204
Location: Brazil
ctl3d32
This is an unoptimized matlab code:

Code:
```clear all
close all
clc

if ~isinteger(matrix_size)
matrix_size = round(matrix_size) + 1;
end

M = zeros(matrix_size,matrix_size);

for i = 1:matrix_size
for j =1:matrix_size
M(i,j) = i^2 + j^2;
end
end

M = tril(M);

if isempty(m)
fprintf('There are no numbers.\n');
else
fprintf('\nThe numbers are: \n');
for k = 1:size(m,1)
fprintf('%d^2 + %d^2\n',m(k),n(k));
end
end
```

Example:

Code:
```Type numer: 1000

The numbers are:
30^2 + 10^2
26^2 + 18^2
```
01 Dec 2011, 10:02
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Hi ctl3d32,

What you're doing there is actually the opposite of what I'm trying to do. You're taking a number and seeing if it is the sum of two squares.
As a simple example, I could do this

Code:
```
pos = 1
for i = 1 to 99
for j = i+1 to 100
so2s[pos] = i² + j²
pos = pos + 1
next j
next i
```

This will give a list of numbers up to 99² + 100² that are the sum of two squares.

The problem is, they are not in numerical order and the list is incomplete.

i.e 1² + 140² is less than 99² + 100² but isn't included.
01 Dec 2011, 13:06
ctl3d32

Joined: 30 Dec 2009
Posts: 204
Location: Brazil
ctl3d32
Is this what you want?

Code:
```clear all
close all
clc

answer = input('Generate ordered list till number: ');

if ~isinteger(matrix_size)
matrix_size = round(matrix_size) + 1;
end

M = zeros(matrix_size,matrix_size);

for i = 1:matrix_size
for j =1:matrix_size
M(i,j) = i^2 + j^2;
end
end

M = tril(M);

[m,n] = find(M(:,:) == i);

fprintf('\nNumber: %d\n',i);

if isempty(m)
fprintf('There are no pair of integers.\n');
else
for k = 1:size(m,1)
fprintf('%d^2 + %d^2\n',m(k),n(k));
end
end
end
```

Example:
Code:
```Generate ordered list till number: 20

Number: 1
There are no pair of integers.

Number: 2
1^2 + 1^2

Number: 3
There are no pair of integers.

Number: 4
There are no pair of integers.

Number: 5
2^2 + 1^2

Number: 6
There are no pair of integers.

Number: 7
There are no pair of integers.

Number: 8
2^2 + 2^2

Number: 9
There are no pair of integers.

Number: 10
3^2 + 1^2

Number: 11
There are no pair of integers.

Number: 12
There are no pair of integers.

Number: 13
3^2 + 2^2

Number: 14
There are no pair of integers.

Number: 15
There are no pair of integers.

Number: 16
There are no pair of integers.

Number: 17
4^2 + 1^2

Number: 18
3^2 + 3^2

Number: 19
There are no pair of integers.

Number: 20
4^2 + 2^2
```
01 Dec 2011, 19:55
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Getting there

I've never used matlab but it appears what you are doing is similar to LocoDel's bitmap idea. In principal it's fine but it can't generate the *next* number.

Code:
```for i = 1:matrix_size
for j =1:matrix_size        ;should be i+1:matrix_size for squares to
;be distinct, but no matter.
M(i,j) = i^2 + j^2;
end
end
```

This will, as you show, generate a list up to matrix_size, in your example, 20, but if I want 21 I need to run it again. I think I'll have to give up on this for the moment unless I have a sudden flash of inspiration.

Thanks for all the input though, very much appreciated

magic²
01 Dec 2011, 20:29
ctl3d32

Joined: 30 Dec 2009
Posts: 204
Location: Brazil
ctl3d32
The idea is to run once with a very big number and create a database.
01 Dec 2011, 20:40
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Yep, seems to be the only way to go.

Thanks again
02 Dec 2011, 17:45
codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark
codelab
Quote:

I was looking for a way to generate, in numerical order, integers that are the sum of two distinct squares, so taking the first few we would have these

5 = 1 + 4
10 = 1 + 9
13 = 4 + 9
17 = 1 + 16
20 = 4 + 16
25 = 9 + 16
26 = 1 + 25
29 = 4 + 25

Is there any way I can generate these in order?

yes and i liked your problem

I noticed no 16=4 + 4 in list as a magic square?
in that case:
if you do sqrroot on your boxes
side on smaller box (n) steps up to m-1
then n resets to 1 and m steps up

(s = n * n + m * m)

s n m

5 1 2
10 1 3
13 2 3
17 1 4
20 2 4
25 3 4
26 1 5
29 2 5

Code:
```; code to nth magic, (add ur own output code)

mov eax, 0  ; side of little box n
mov ebx, 1  ; size of bigger box m
mov ecx, 10 ; nth magic sqr number

l1:
cmp eax, ebx
jne dump
mov eax, 1
dump:
call printval
dec ecx
jnz l1
jmp ok

printval:
Print EAX*EAX + EBX*EBX, EAX*EAX, EBX*EBX
ret

ok:
```

output:
5 1 4
10 1 9
13 4 9
17 1 16
20 4 16
25 9 16
26 1 25
29 4 25
34 9 25
41 16 25

Sincerely, C
18 Apr 2012, 23:14
chris

Joined: 05 Jan 2006
Posts: 62
Location: China->US->China->?
chris
codelab wrote:
Quote:

I was looking for a way to generate, in numerical order, integers that are the sum of two distinct squares, so taking the first few we would have these

5 = 1 + 4
10 = 1 + 9
13 = 4 + 9
17 = 1 + 16
20 = 4 + 16
25 = 9 + 16
26 = 1 + 25
29 = 4 + 25

Is there any way I can generate these in order?

yes and i liked your problem

I noticed no 16=4 + 4 in list as a magic square?
in that case:
if you do sqrroot on your boxes
side on smaller box (n) steps up to m-1
then n resets to 1 and m steps up

output:
5 1 4
10 1 9
13 4 9
17 1 16
20 4 16
25 9 16
26 1 25
29 4 25
34 9 25
41 16 25

Actually according to this algorithm, the numbers generated are not
in the numerical order, since for instance (n-1)^2+n^2 < (n+1)^2+1
implies n<5, and the next number this algorithm generates is 37=1+36.
19 Apr 2012, 16:15
chris

Joined: 05 Jan 2006
Posts: 62
Location: China->US->China->?
chris
a google search yields the following interesting paper:
http://www.math.uchicago.edu/~may/VIGRE/VIGRE2009/REUPapers/Wong.pdf
in which a necessary and sufficient condition for Two-Squares sum problem was given.
It may suggest another approach to this problem involving prime factorization (slower?) of such an integer.
For example, the prime 129694419029057750551385771184564274499075700947656757821537291527196801 is a sum of two (necessarily different) squares, by Theorem 3.3 in above paper.
19 Apr 2012, 16:58
codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark
codelab
Quote:

Actually according to this algorithm, the numbers generated are not
in the numerical order, since for instance (n-1)^2+n^2 < (n+1)^2
....

Interesting paper

But in this case the algorithm must confirm to the question:

Construct c as n'th of 5,10,13,17,20,25,26,29,...

where c=a^2+b^2

conditions:

a>0, b>a, d=a, a=a+((d+1)<b),a=a*((d+1)<>b),a=a+(a==0)),b=b+((d+1)==b)

Infact, a function for n'th number can be made:

MagicSqr(n)
c = n * 2
rb = (-1 + Sqrt(1 - - 4 * c)) / 2 + 1 // solve quadratic
bigbox = Ceil(rb)
littlebox = Floor( bigbox - (bigbox - 1) * (bigbox - rb) - 1)

Return littlebox * littlebox + bigbox * bigbox

Sincerely, C
19 Apr 2012, 21:58
Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA
Tyler
Just look at the list of the numbers you're using as input to the addition:
4 1
9 1
9 4
16 1
16 4
16 9
...

The pattern should be obvious. You start with the first number, a, equaling 4. You then add a with all the squares less than it. (This is easy to do with a second variable, b, that starts at 1 and increases to the next square until it is equal to a.) You increase a to the next square, and repeat.
19 Apr 2012, 23:40
Apos

Joined: 11 Jan 2012
Posts: 17
Location: Paris, France (I'm not from France though.)
Apos
I'm not sure if this thread has been solved, but I decided to try and generate my own algorithm to compute the numbers in the correct order.
Code:
```//Numbers that are the sum of 2 distinct nonzero squares.
//https://oeis.org/A004431

#include <stdio.h>

int small = 0;

int smallest(int num1, int num2)
{
if(num1 < num2)
{
return num1;
}
else
{
return num2;
}
}

int squareSum(int i, int j)
{
return ((i * i) + (j * j));
}

int next(int current, int i, int j)
{
int hold = 1;

while((squareSum(i, j) <= current) || (squareSum(hold, (j + 1)) < current))
{
if(squareSum(i, j) < squareSum(hold, (j + 1)))
{
if(squareSum(i, j) > small)
{
fflush(stdout);
printf("%d\t=\t%d\t+\t%d\n", squareSum(i, j), (i * i), (j * j));
small = squareSum(i, j);
}
}
else
{
hold = next(smallest(squareSum(i, j), current), hold, (j + 1));
i = hold;
}
i++;
if(i == j)
{
i = 1;
hold = 1;
j++;
}
}
return i;
}

int main ()
{
int num = 198;

int i = 1, j = 2;

next(num, i, j);

return 0;
}
```

The algorithm will compute all the correct numbers between the first possible number and the variable 'num' found in the main.
The algorithm will also ignore duplicates.
I can assist you in case you need help in understanding my code.

In all, it took me about 45 minutes to code.

Edit:
Here the output computed from 5 to 198:
Code:
```5       =       1       +       4
10 =       1       +       9
13 =       4       +       9
17 =       1       +       16
20        =       4       +       16
25        =       9       +       16
26        =       1       +       25
29        =       4       +       25
34        =       9       +       25
37        =       1       +       36
40        =       4       +       36
41        =       16      +       25
45        =       9       +       36
50        =       1       +       49
52        =       16      +       36
53        =       4       +       49
58        =       9       +       49
61        =       25      +       36
65        =       1       +       64
68        =       4       +       64
73        =       9       +       64
74        =       25      +       49
80        =       16      +       64
82        =       1       +       81
85        =       4       +       81
89        =       25      +       64
90        =       9       +       81
97        =       16      +       81
100       =       36      +       64
101       =       1       +       100
104      =       4       +       100
106      =       25      +       81
109       =       9       +       100
113      =       49      +       64
116       =       16      +       100
117      =       36      +       81
122       =       1       +       121
125      =       4       +       121
130      =       49      +       81
136       =       36      +       100
137      =       16      +       121
145      =       64      +       81
146       =       25      +       121
148      =       4       +       144
149      =       49      +       100
153      =       9       +       144
157      =       36      +       121
160      =       16      +       144
164      =       64      +       100
169      =       25      +       144
170      =       49      +       121
173      =       4       +       169
178      =       9       +       169
180      =       36      +       144
181      =       81      +       100
185      =       64      +       121
193      =       49      +       144
194      =       25      +       169
197      =       1       +       196
```

Edit2:
While I'm at it, I'll also say there was an easier algorithm:
Code:
```//Numbers that are the sum of 2 distinct nonzero squares.
//https://oeis.org/A004431

#include <stdio.h>

int squareSum(int i, int j)
{
return ((i * i) + (j * j));
}

int main ()
{
int num = 198;

int i = 1, j = 2;
int k;
for(k = 0; k < num; k++)
{
fflush(stdout);
printf("%d\t=\t%d\t+\t%d\n", squareSum(i, j), (i * i), (j * j));
i++;
if(i == j)
{
i = 1;
j++;
}
}

return 0;
}
```

This will will compute 198 of those magic numbers without putting them in order, and without removing the duplicates. (So it doesn't fulfill all the rules specified by the OP.)
It's also the first algorithm anyone could think of to resolve this problem...

_________________
"A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away." - Antoine de Saint-Exupéry
19 Apr 2012, 23:53
codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark
codelab
My big mistake, sorry to Chris

I did not notice numerical order was required by OP !

Sincerely C
21 Apr 2012, 20:05
magicSqr

Joined: 27 Aug 2011
Posts: 105
magicSqr
Tyler wrote:
Just look at the list of the numbers you're using as input to the addition:
4 1
9 1
9 4
16 1
16 4
16 9
...

The pattern should be obvious. You start with the first number, a, equaling 4. You then add a with all the squares less than it. (This is easy to do with a second variable, b, that starts at 1 and increases to the next square until it is equal to a.) You increase a to the next square, and repeat.

Hi Tyler.

Sorry, I haven't been around in a while. Yes, you are quite right, I was missing the obvious

If i'd simply turned my additions round... grrrrr

posted the above last night just before bed. Just before dropping off it occured to me that since 65 is the first number that is the sum of two different non-zero squares in two different ways the above falls to pieces very quickly, i.e

65 = 7² + 4²
65 = 8² + 1²

so 7² + 5² and 7² + 6² are > 65 so numerical order shot again

It actually falls apart much sooner

5² + 4² = 41
6² + 1² = 37
6² + 2² = 40

[/edit]

magic²
07 Aug 2012, 00:32
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page Previous  1, 2

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum