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
Thread Post new topic Reply to topic
ctl3d32



Joined: 30 Dec 2009
Posts: 204
Location: Brazil
ctl3d32
I wonder if the branch and bound algorithm would work here.
Post 01 Dec 2011, 01:00
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
Not sure I follow how the BB algo could be used here ctl3d32.
Post 01 Dec 2011, 08:41
View user's profile Send private message Reply with quote
ctl3d32



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


Code:
clear all
close all
clc

answer = input('Type numer: ');

matrix_size = sqrt(answer);

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(:,:) == answer);

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
    
Post 01 Dec 2011, 10:02
View user's profile Send private message Reply with quote
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] =+ 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.
Post 01 Dec 2011, 13:06
View user's profile Send private message Reply with quote
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: ');

matrix_size = sqrt(answer);

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);

for i = 1:answer
    
    [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
    
Post 01 Dec 2011, 19:55
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
Getting there Wink

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 Wink

magic²
Post 01 Dec 2011, 20:29
View user's profile Send private message Reply with quote
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.
Post 01 Dec 2011, 20:40
View user's profile Send private message Reply with quote
magicSqr



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

Thanks again
Post 02 Dec 2011, 17:45
View user's profile Send private message Reply with quote
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:
 add eax, 1
 cmp eax, ebx
 jne dump
 mov eax, 1
 add ebx, 1
dump:
 call printval
 dec ecx
 jnz l1
 jmp ok

printval:
 pushad
 Print EAX*EAX + EBX*EBX, EAX*EAX, EBX*EBX
 popad
 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
how about magic cubes now Smile

Sincerely, C
Post 18 Apr 2012, 23:14
View user's profile Send private message Reply with quote
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.
Post 19 Apr 2012, 16:15
View user's profile Send private message Reply with quote
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.
Post 19 Apr 2012, 16:58
View user's profile Send private message Reply with quote
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 Smile

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 Shocked Idea
Post 19 Apr 2012, 21:58
View user's profile Send private message Reply with quote
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.
Post 19 Apr 2012, 23:40
View user's profile Send private message Reply with quote
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... Very Happy

_________________
"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
Post 19 Apr 2012, 23:53
View user's profile Send private message Reply with quote
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
Post 21 Apr 2012, 20:05
View user's profile Send private message Reply with quote
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 Embarassed

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

[edit]

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²
Post 07 Aug 2012, 00:32
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page Previous  1, 2

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.