Hi,

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

magic²

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²

yes

Thanks

That's that sorted then, lol

Ok. Just those numbers or the list goes on ?

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²

But how are you coming up with the numbers ?

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.

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

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²

my OP



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)

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)

Thanks LocoDel

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.

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

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.

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.

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

magic²

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

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 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.
If anyone can spot any holes let me know

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

magic²