can an algorithm be made for this?

Index > Main > can an algorithm be made for this?

Goto page Previous 1, 2

Author

Thread

ctl3d32

Joined: 30 Dec 2009
Posts: 206
Location: Brazil

ctl3d32 01 Dec 2011, 01:00

I wonder if the branch and bound algorithm would work here.

01 Dec 2011, 01:00

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 01 Dec 2011, 08:41

Not sure I follow how the BB algo could be used here ctl3d32.

01 Dec 2011, 08:41

ctl3d32

Joined: 30 Dec 2009
Posts: 206
Location: Brazil

ctl3d32 01 Dec 2011, 10:02

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

01 Dec 2011, 10:02

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 01 Dec 2011, 13:06

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: 206
Location: Brazil

ctl3d32 01 Dec 2011, 19:55

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

01 Dec 2011, 19:55

magicSqr

Joined: 27 Aug 2011
Posts: 105

magicSqr 01 Dec 2011, 20:29

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²

01 Dec 2011, 20:29

ctl3d32

Joined: 30 Dec 2009
Posts: 206
Location: Brazil

ctl3d32 01 Dec 2011, 20:40

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 02 Dec 2011, 17:45

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 18 Apr 2012, 23:14

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

18 Apr 2012, 23:14

chris

Joined: 05 Jan 2006
Posts: 62
Location: China->US->China->?

chris 19 Apr 2012, 16:15

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 19 Apr 2012, 16:58

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 19 Apr 2012, 21:58

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

19 Apr 2012, 21:58

Tyler

Joined: 19 Nov 2009
Posts: 1216
Location: NC, USA

Tyler 19 Apr 2012, 23:40

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 19 Apr 2012, 23:53

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

19 Apr 2012, 23:53

codelab

Joined: 03 Apr 2006
Posts: 16
Location: Denmark

codelab 21 Apr 2012, 20:05

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 07 Aug 2012, 00:32

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²

07 Aug 2012, 00:32

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