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
I wonder if the branch and bound algorithm would work here.


01 Dec 2011, 01:00 

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


01 Dec 2011, 08:41 

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
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
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
The idea is to run once with a very big number and create a database.


01 Dec 2011, 20:40 

magicSqr
Yep, seems to be the only way to go.
Thanks again 

02 Dec 2011, 17:45 

codelab
Quote:
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 m1 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 Sincerely, C 

18 Apr 2012, 23:14 

chris
codelab wrote:
Actually according to this algorithm, the numbers generated are not in the numerical order, since for instance (n1)^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
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 TwoSquares 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
Quote:
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
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
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 SaintExupéry 

19 Apr 2012, 23:53 

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
Tyler wrote: Just look at the list of the numbers you're using as input to the addition: 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 [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 nonzero 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:

Copyright © 19992020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.