flat assembler
Message board for the users of flat assembler.

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

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
Hi,

[edit] Just thought of a different way around this, I'll be back...

magic²
Post 29 Nov 2011, 22:34
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
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?

thanks

magic²
Post 29 Nov 2011, 22:47
View user's profile Send private message Reply with quote
typedef



Joined: 25 Jul 2010
Posts: 2913
Location: 0x77760000
typedef
yes
Post 29 Nov 2011, 23:12
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
typedef wrote:
yes


Thanks Wink

That's that sorted then, lol
Post 29 Nov 2011, 23:23
View user's profile Send private message Reply with quote
typedef



Joined: 25 Jul 2010
Posts: 2913
Location: 0x77760000
typedef
Ok. Just those numbers or the list goes on ?
Post 29 Nov 2011, 23:25
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
magicSqr wrote:
...so taking the first few we would have these...

ad infinitum.

I'll be using GMP as the numbers get bigger, but that's not the problem, it's the general algo I'm struggling with as there isn't really an order to the squares i.e the next few


34 = 9 + 25
37 = 1 + 36
40 = 4 + 36
41 = 16 + 25
45 = 9 + 36


magic²
Post 29 Nov 2011, 23:41
View user's profile Send private message Reply with quote
typedef



Joined: 25 Jul 2010
Posts: 2913
Location: 0x77760000
typedef
But how are you coming up with the numbers ?
Post 29 Nov 2011, 23:57
View user's profile Send private message Reply with quote
typedef



Joined: 25 Jul 2010
Posts: 2913
Location: 0x77760000
typedef
If you are just putting down random #s then it will be even harder to come up with an equation.

I was designing one based on those numbers, but I can't really go anywhere if I don't know how the numbers came about.

The first thing I noted is that the numbers to the right are Squares. So for that,

Let : X >= 2
Let : S = (X*X) // Square

Again, I don't know how the #s came about (If you just dreamed of them or something)

Then

if ( X AND 01 ) == ODD
else
EVEN

If that even helps

But first tell me how you are getting the numbers.
Post 30 Nov 2011, 00:04
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
Not sure I understand the question typedef ¿

Each number in the list so far (5, 10, 13, 17, 20 .....) can be expressed as the sum of two distinct squares (i.e. different i.e. 8 = 2² + 2² no good and I'm not including 0 as a square so 16 = 0² + 4² also no good)

I'm not sure how else to explain it Sad

6 = 1 + 5 not two squares
6 = 2 + 4 not two squares
6 = 3 + 3 not two squares

hence 6 is not in the list

magic²
Post 30 Nov 2011, 00:10
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
typedef wrote:

The first thing I noted is that the numbers to the right are Squares. So for that,


my OP

magicSqr wrote:
integers that are the sum of two distinct squares...


that's exactly where the numbers are coming from

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 16 can't be expressed (in integers) as the sum of two distinct squares

num = a² + b² (where a > b > 0)
Post 30 Nov 2011, 00:22
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
https://oeis.org/A004431 <- This is what magicSqr is trying to get (i.e. generate the first N terms of the series with N known at run-time)
Post 30 Nov 2011, 03:29
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
Thanks LocoDel Smile

That was roughly how I was going to explain it in my OP but thought the other way was easier to understand.

The numbers in the list of integers that are the sum of two distinct squares are made up like this:

1) The number must have at least one prime factor of the form (4k+1)
2) If the number has any prime factors of the form (4k+3) then the exponent of this factor must be even.
3) The number can have 2 raised to any power >= 0 as a factor.

so we would have (2^3)*(5^1)*(7^2) = 1960 = 14² + 42²

but (2^3)*(5^1)*(7^1) = 280 cannot be expressed as the sum of two distinct squares because 7 is of the form (4k+3) and is raised to an odd power.

The reason I was thinking the other way is easier is that the above requires extensive testing whereas, when we know we want numbers that are the sum of two distinct squares, why not just generate them.

One of the methods mentioned in your link actually generates Pythagorean primitive triples

a² + b² = c²

not a² + b² = c

One way I could achieve what I'm after (in BASICish terms)

k=1
for i = 1 to (n - 1)
for j = (i + 1) to n
sumofSqrs[k] = i² + j²
k = k + 1
next j
next i

and then sort the array 'sumofSqrs' into numerical order, but this seems a long way round as well.
Post 30 Nov 2011, 12:47
View user's profile Send private message Reply with quote
smiddy



Joined: 31 Oct 2004
Posts: 559
smiddy
Can you generate the sum of the two squares, to n, then sort on the answer in a runtime created array, with tracking of each component making up the sum?

Try working the long way first, then optimize for elegance and speed second?!

I am typing this on my phone, so example code would take forever to fat finger. LOL
Post 30 Nov 2011, 13:09
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
or create seperate arrays for each 'i' then interleave the results at the end, knowing that each seperate array is already in numerical order. hmmm, might just take a look into that.
Post 30 Nov 2011, 13:22
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Do you have an estimate of how much the terms are separated from each other with n large? Because if they are as near as the example at OEIS, you should consider testing with a single bit map and then printing the number by scanning for 1s in the bitmap. In this method, N could be defined as the bitmap size, and then your algo would try to fit as much numbers as it can before running out of space.

I could provide you the code for this, but I'll let you attempt this by yourself first.
Post 30 Nov 2011, 15:47
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
Thanks Loco,

I'll take a look at the density for large n and let you know. Not sure I follow the second part of your post but I'll give it a go and see where I get Wink

magic²
Post 30 Nov 2011, 15:57
View user's profile Send private message Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
Basically, I mean changing "sumofSqrs[k] = i² + j²" to "bitVector[i² + j²] = 1", where bitVector is bit-addressable (i.e. you use BTS instruction). Later, rather than sorting you just walk the entire array printing all the indexes where you find a bit set to 1.

This method should be more efficient than storing numbers as 32-bit numbers (or bigger numbers if you want to get a really long list), but if the series looses density as N gets large then perhaps the space wasted to store zeroes becomes too costly to be useable. Other option could be storing the difference with the previous number, but you'll probably need several lists like you mentioned earlier to do this to avoid costly insertions. *


*The list I mention is this: [5, 5, 3, 4, 3] which would represent [5, 10, 13, 17, 20], but the former could probably use 8-bit numbers or perhaps even fewer bits, that depends on the maximum spacing (although you could always reserve a few magic numbers to tell the code that the next, say, dword is a number rather than just a difference with the previous term).
Post 30 Nov 2011, 17:01
View user's profile Send private message Reply with quote
cod3b453



Joined: 25 Aug 2004
Posts: 619
cod3b453
Apologies for using C on this; tried to make it easy to convert. Note that I haven't confirmed this is either correct or particularly optimal. (It currently takes minutes to scan all pairs whose squares sum to less than 2^20 Sad but there is no storage requirement other than registers)

The method basically increments a modulus* (m) to match with parameters a,b which you can visualise as columns (b) and rows (a) in a matrix. Since a =/= b we can discount one triangle, the diagonal and the first column of the matrix.

*m can be considered the square of the hypotenuse of a triangle so that it can be compared with a*a + b*b and avoid the need to sqrt.
Code:
 ;//for (m = 5; m; m = m + 1)
        m = 5;
      do
  {
              ;// let col = 1..floor(sqrt(m))
             ;//for (b = 1, bb = (b + 1) * (b + 1); bb < m ; b = b + 1, bb = (b + 1) * (b + 1))
               b = 1;
              bb = 4;
             do
          {
                      ;// let row = 0..(b-1)
                      ;//for (a = 0; (a < b) && (bb < m); a = a + 1)
                        a = 0;
                      do
                  {
                              ;// convert row to index and square
                         aa = (a + 1) * (a + 1);

                         ;// calculate sum
                           r = aa + bb;

                            ;// if target modulus hit, record and increment
                             if (r == m)
                         {
                                      ;//printf("%08X %04X %04X\n",r,(b+1),(a+1));
                                     m++; ;// restart loops required???
                          }

                          a = a + 1;
                  }
                      while ( (a < b) && (bb < m) );

                    b = b + 1;
                  bb = (b + 1) * (b + 1);
             }
              while (bb < m);

              m = m + 1;
  }
      while(m);    
If anyone can spot any holes let me know Laughing
Post 30 Nov 2011, 21:56
View user's profile Send private message Reply with quote
smiddy



Joined: 31 Oct 2004
Posts: 559
smiddy
I am having enough trouble remembering assembly let alone C. LOL
Post 30 Nov 2011, 23:13
View user's profile Send private message Reply with quote
magicSqr



Joined: 27 Aug 2011
Posts: 105
magicSqr
smiddy wrote:
I am having enough trouble remembering assembly let alone C. LOL


ROFL, and pseudo C++Basic is even scarier. I'll plough my way through although me thinks the algo may be missing the point but not sure yet.

for LocoDel,:

it 'appears' the density for n = a² + b² may be limiting around n/5.
The first few thousand are higher but as I get into tens of millions there seems very little fluctuation from ~ 20%. The highest difference I have found between successive terms is 56, although this will probably grow higher for larger n. It seems that a byte would still be big enough for very large n though.


Further to what I am working on, I would require n to be the sum of two squares in *at least* four different ways.

In the prime factorization of n, as stated earlier, it can have factors of the form {4k+3) only if these are raised to an even power. n can also have 2 raised to any power >=0 as a factor.
If n satisfies these conditions and has at least one prime factor of the form (4k+1), it can be expressed as the sum of two, distinct, non-zero squares.
The number of ways a particular n can be expressed this way is *totally* dependent on the prime factors of form (4k+1).

For n to be expressible as the sum of two squares in *at least* four ways, the *minimum* requirements are that it has any of the following combinations of these type of prime factors (4k+1)...{LaTeX would be handy here, any way of incorporating it Tomasz?)

n = p1^7 or greater exponent
n = p1^1 * p2^3
n = p1^2 * p2^2
n = p1^1 * p2^1 * p3^1

The fourth example actually covers the lowest n that is of the required type

1105 = 5 * 13 * 17 = (4*1 + 1)(4*3 + 1)(4*4 + 1)

and

1105 = 4² + 33²
1105 = 9² + 32²
1105 = 12² + 31²
1105 = 23² + 24²

Forgive me for waffling, I'm a great 'doer' but an awful teacher Sad

magic²
Post 01 Dec 2011, 00:04
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< 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.