## [sub-project] Perfect cuboid

Fehler und Wünsche zum Projekt yoyo@home
Bugs and wishes for the project yoyo@home
Nachricht
Autor
Robert Gerbicz
PDA-Benutzer
Beiträge: 56
Registriert: 08.06.2010 19:06

### Re: [sub-project] Perfect cuboid

x3mEn hat geschrieben:So, I've finished my idea description.
Any questions, proposals, objections?
I read your algorithm, that's correct. The problem with that g can be very large. If you fix X, where X is the odd term of {a,b,c} then you can only say that a,b,c<=(X^2-1)/2 (I read this bound, the X^2-1 bound is trivial). This makes that g can be even X^2/2. So for example only X<1e10 would be unreachable by your method.

Only one "real" example that this is a problem: let X=9801055;Y=1099548672;Z=2033707104;
then this is an Euler brick, so X^2+Y^2; Y^2+Z^2; Z^2+X^2 is square (but not perfect brick), and g=sqrt(X^2+Y^2+Z^2)~2e9, but X was less than 1e7, so g is much larger.
I don't know what your posted code searches, but my code finds it in approx. 100 seconds on a 2.2 GHz Amd (using one core) by testing all X<1e7.

And, this is just a programming advice for you: sqrt, division are all costly operations in all languages, in c/c++ also. Avoid them, my current code uses only addition/subtraction and lookup tables where you do sqrt/mod operations. Currently for these tables it needs less than 32MB Ram.

About my method: my first program used the well known trick, that if you fix X, where X is odd and Y,Z are the other two length of the cuboid, then
X^2=A^2-Y^2
X^2=B^2-Z^2
decompose it X^2=A^2-Y^2=(A-Y)(A+Y) so d=A-Y is a divisor of X^2, if you know it, then Y=(d+X^2/d)/2, for another D: Z=(D+X^2/D)/2. (You can suppose that 0<d,D<X).

This method works, but not so fast, because it involves divisions. The other method:

X^2+Y^2=A^2, use Pythagorean triples, this means that X=K(P^2-Q^2); Y=2KPQ; Z=K(P^2+Q^2); where K>0 integer, P>Q>0; P-Q is odd and gcd(P,Q)=1. From X=K(P-Q)(P+Q) you can see, that if you know the prime factorization of X, then you can find all triples K,P,Q for the Pythagorean triples. Generating them is really fast (and you don't need to compute gcd's), use sieve to find (prime) divisor of X values. Note also that gcd(X,Y,Z)=K. The rest of the algorithm: fix two triangles, so two K1,P1,Q1 and K2,P2,Q2 triples, then you need to check only that Y^2+Z^2 is also square or not, so S=(2*K1*P1*Q1)^2+(2*K2*P2*Q2)^2=C^2 or not. I don't compute this square sum, since this can be overflow in 64 bits, I check for many primes that this S is a quadratic resideu or not. You can check many primes at once.

x3mEn
XBOX360-Installer
Beiträge: 99
Registriert: 20.03.2011 22:23

### Re: [sub-project] Perfect cuboid

Robert Gerbicz,

you and me, like the most who had tried to solve this problem, began to search and check DIAGONALS by "smart brute force" running over EDGES.
As you noticed, the main trouble for this method is a calculation limit for g that can be even X^2/2, so X<1e10 would be unreachable.

My method is based on searching and checking EDGES by running over SPACE DIAGONALS.
But not every diagonal will be checked, but only those, who are a product of 4k+1 primes.
Do you feel a difference?

I can show a broad bounds of my method checking in the next example.
Let g = 5^4*13^3*17^1*29^1*41^5*53^1 = 4156733166885008125 ? 4.1E+18
g^2 = 5^8*13^6*17^2*29^2*41^10*53^2 ? 1.7E+37

First of all we are searching for decompositions of g^2 to a sum of squares.
According to Dirichlet formula there are
[((8+1)(6+1)(2+1)(2+1)(10+1)(2+1)+1)/2] = 9356
different decompositions of 4156733166885008125^2 to a sum of squares.
The list of all of them you can find attached
(my GUI program may optionally generate these lists for every given diagonal)

I show here only the top and the bottom of this list:

Code: Alles auswählen

``````0,4156733166885008125
570091156017900,4156733127791335925
707705422451028,4156733106639744779
1001294989456125,4156733046286496000
1115826613516500,4156733017119675125
...
2938357150494534384,2940150995581606013
2938401145537459875,2940107026723009000
2938610048867891125,2939898229764853500
2938654040128490684,2939854257122003637
2939146293923494980,2939362121889314485
2939190277161907275,2939318141222344700``````
You may recheck yourself that

Code: Alles auswählen

``````4156733166885008125^2 = 0^2 + 4156733166885008125^2
4156733166885008125^2 = 570091156017900^2 + 4156733127791335925^2
4156733166885008125^2 = 707705422451028^2 + 4156733106639744779^2
4156733166885008125^2 = 1001294989456125^2 + 4156733046286496000^2
4156733166885008125^2 = 1115826613516500^2 + 4156733017119675125^2
?
4156733166885008125^2 = 2938357150494534384^2 + 2940150995581606013^2
4156733166885008125^2 = 2938401145537459875^2 + 2940107026723009000^2
4156733166885008125^2 = 2938610048867891125^2 + 2939898229764853500^2
4156733166885008125^2 = 2938654040128490684^2 + 2939854257122003637^2
4156733166885008125^2 = 2939146293923494980^2 + 2939362121889314485^2
4156733166885008125^2 = 2939190277161907275^2 + 2939318141222344700^2``````
All factors righter of equation symbol are candidates for edges and face diagonals.

First of all, all these pair are obtained WITHOUT exceeding 64-bit integer operations limit.
Second, for checking these pair as a candidates for edges, sqrt operation is used only after the sequance of trivial conditions, so not far for every pair sqrt is used
(during a program debug I noticed that only for near 1 of 20 or even seldomer).

So, man, do you understand now, that bounds of my method are far far away from 10E+11, which are reached by your and the most others similar searching methods?
Dateianhänge
4156733166885008125.zip
(164.71 KiB) 244-mal heruntergeladen

Robert Gerbicz
PDA-Benutzer
Beiträge: 56
Registriert: 08.06.2010 19:06

### Re: [sub-project] Perfect cuboid

x3mEn hat geschrieben: But not every diagonal will be checked, but only those, who are a product of 4k+1 primes.
Do you feel a difference?
Not a real difference, up to n there are O(n/sqrt(log(n))) such numbers, this is a theorem. That gives you still need to check O(X^2/sqrt(log(X))) different \$g\$ values to check all odd numbers up to X.
x3mEn hat geschrieben: So, man, do you understand now, that bounds of my method are far far away from 10E+11, which are reached by your and the most others similar searching methods?
That is only one worked out example for g=4156733166885008125.
The best known search checked all X<1e12. By your method it would need to check 10^24/sqrt(log(10^12))~10^23 different \$g\$ values just to reach this record. And that's impossible.

x3mEn
XBOX360-Installer
Beiträge: 99
Registriert: 20.03.2011 22:23

### Re: [sub-project] Perfect cuboid

Robert Gerbicz hat geschrieben:
x3mEn hat geschrieben: But not every diagonal will be checked, but only those, who are a product of 4k+1 primes.
Do you feel a difference?
Not a real difference, up to n there are O(n/sqrt(log(n))) such numbers, this is a theorem. That gives you still need to check O(X^2/sqrt(log(X))) different \$g\$ values to check all odd numbers up to X.
Excuse me, but I feel you absolutely didn't understand my idea.
Please read again my message named Running over Diagonals from the previous page.
Or we can discuss all in skype. My nick is x3mEn.

The amount of different \$g\$ values is very difficult question and can not be calculated as you did.
Robert Gerbicz hat geschrieben:The best known search checked all X<1e12. By your method it would need to check 10^24/sqrt(log(10^12))~10^23 different \$g\$ values just to reach this record. And that's impossible.
You really didn't understand my idea.
Because this diagonal will be checked by the first workinit.

Robert Gerbicz
PDA-Benutzer
Beiträge: 56
Registriert: 08.06.2010 19:06

### Re: [sub-project] Perfect cuboid

Now reading that message and your first post I see what you don't understand.

What you want to do with Boinc is already known/searched... You want to search for g<2^32, where g is the space diagonal. But a^2+b^2+c^2=g^2, this means that (if X=odd term of {a,b,c}), X^2<g^2<2^64, so X<2^32. And this is known for more than 10(?) years. In fact all (primitive) Euler bricks is known for X<2^32, http://arxiv.org/abs/math/0111229, what link I have already posted. Just to post one more data, my code would do it in about 1-2 days.

And from that message: "Will get 2'147'516'416 records."
And that would cost 16GB Ram (if you store it as two int values). That's too much, here.

My code would use less than 32MB Ram for X<1e13.

ps. Reading again those messages, I'm not sure what you want to search. If in fact you want to cover g<2^64, then those tables would be much bigger. Or in other case I don't see the proof that g has no prime divisor larger than 2^32. This is a hole.

x3mEn
XBOX360-Installer
Beiträge: 99
Registriert: 20.03.2011 22:23

### Re: [sub-project] Perfect cuboid

Robert Gerbicz hat geschrieben:Now reading that message and your first post I see what you don't understand.

What you want to do with Boinc is already known/searched... You want to search for g<2^32, where g is the space diagonal. But a^2+b^2+c^2=g^2, this means that (if X=odd term of {a,b,c}), X^2<g^2<2^64, so X<2^32. And this is known for more than 10(?) years. In fact all (primitive) Euler bricks is known for X<2^32, http://arxiv.org/abs/math/0111229, what link I have already posted. Just to post one more data, my code would do it in about 1-2 days.
Robert Gerbicz,
I say again, you didn't understand my idea!
First 2 pages of this topic I spent to prove that space diagonal of primitive perfect cuboid is a product of primes 4k+1.
Do you exactly understand, what "a product of primes 4k+1" is?
A product of primes 4k+1 means that g = ? (p(i)^a(i)),
where ? means multiplication sign,
p(i) is prime of kind 4k+1,
a(i) is a power of p(i)

WE DON'T CHECK ANY OTHER ODD NUMBERS!!!
ONLY THOSE, WHO ARE A PRODUCT OF PRIMES 4k+1!!!
IF SOME ODD NUMBER HAS ANY 4k+3 FACTOR, IT WILL BE PASSED (IGNORED) AUTOMATICALLY!
BECAUSE WE WILL CHECK ONLY THOSE NUMBERS, WHO ARE PRODUCED BY MULTIPLICATION OF PRIMES 4K+1.
AND WE WILL NOT FACTORIZE ODD NUMBERS!!! WE WILL GENERATE SPACE DIAGONALS BY MULTIPLICATION OF PRIMES! AND ONLY AFTER THAT WILL CHECK!

Every client will generate these numbers from the given set of primes 4k+1 in way described before!
The method of running over all these diagonals is described on the previous page.
Specially for you I'll list several first diagonals from the fisrt workunit:
g(1) = 5^1 = 5
g(2) = 5^2 = 25
g(3) = 5^3 = 125
g(4) = 5^4 = 625
g(5) = 5^5 = 3125
g(6) = 5^6 = 15625
g(7) = 5^7 = 78125
g(8) = 5^8 = 390625
g(9) = 5^9 = 1953125
g(10) = 5^10 = 9765625
g(11) = 5^11 = 48828125
g(12) = 5^12 = 244140625
g(13) = 5^13 = 1220703125
g(14) = 5^14 = 6103515625
g(15) = 5^15 = 30517578125
g(16) = 5^16 = 152587890625
g(17) = 5^17 = 762939453125
g(18) = 5^18 = 3814697265625
g(19) = 5^19 = 19073486328125
g(20) = 5^20 = 95367431640625
g(21) = 5^21 = 476837158203125
g(22) = 5^22 = 2384185791015625
g(23) = 5^23 = 11920928955078125
g(24) = 5^24 = 59604644775390625
g(25) = 5^25 = 298023223876953125
g(26) = 5^26 = 1490116119384765625
g(27) = 5^27 = 7450580596923828125
g(28) = 13^1*5^0 = 13
g(29) = 13^1*5^1 = 65
g(30) = 13^1*5^2 = 325
g(31) = 13^1*5^3 = 1625
g(32) = 13^1*5^4 = 8125
g(33) = 13^1*5^5 = 40625
g(34) = 13^1*5^6 = 203125
g(35) = 13^1*5^7 = 1015625
g(36) = 13^1*5^8 = 5078125
g(37) = 13^1*5^9 = 25390625
g(38) = 13^1*5^10 = 126953125
g(39) = 13^1*5^11 = 634765625
g(40) = 13^1*5^12 = 3173828125
g(41) = 13^1*5^13 = 15869140625
g(42) = 13^1*5^14 = 79345703125
g(43) = 13^1*5^15 = 396728515625
g(44) = 13^1*5^16 = 1983642578125
g(45) = 13^1*5^17 = 9918212890625
g(46) = 13^1*5^18 = 49591064453125
g(47) = 13^1*5^19 = 247955322265625
g(48) = 13^1*5^20 = 1239776611328125
g(49) = 13^1*5^21 = 6198883056640625
g(50) = 13^1*5^22 = 30994415283203125
g(51) = 13^1*5^23 = 154972076416015625
g(52) = 13^1*5^24 = 774860382080078125
g(53) = 13^1*5^25 = 3874301910400390625
g(54) = 13^2*5^0 = 169
g(55) = 13^2*5^1 = 845
and so on...

I hope it's clear how to generate every next diagonal from the previous, or not?
Any workunit will contain initial and finish states of \$g\$ described as a sets of primes 4k+1 with their powers.
Every workunit will have to check both big and small \$g\$

I've already attached the example of workunit.
I can repeat it here:

Code: Alles auswählen

``````[WU]
Ini=41^1*37^3*29^5*17^4
Fin=41^2*29^5*17^2*13^2*5^4
Amt=1995

[Primes]
5=1^2+2^2
13=2^2+3^2
17=1^2+3^2
29=2^2+5^2
37=1^2+6^2
41=4^2+5^2``````
Initial state is 41^1*37^3*29^5*17^4
finish state of workunit is 41^2*29^5*17^2*13^2*5^4
Every prime 4k+1, which will be necessary for workunit is described in Primes section with its decomposition to the sum of squares.

Do you understand why initial state 41^1*37^3*29^5*17^4 (3557744073931065217) formally is bigger than finish state 41^2*29^5*17^2*13^2*5^4 (1052500395367143125)?
Do you understand how to pass from 41^1*37^3*29^5*17^4 to 41^2*29^5*17^2*13^2*5^4, what is a sequence of diagonals you need to pass through, or explain?
If you yet don't, please read all my messages from the beginning again.

A client no needs any other information to execute this work unit.
Only initial state, finish state and decomposition of all primes, which will be necessary for him to pass through.
Robert Gerbicz hat geschrieben: And from that message: "Will get 2'147'516'416 records."
And that would cost 16GB Ram (if you store it as two int values). That's too much, here.

My code would use less than 32MB Ram for X<1e13.
You have pulled out a phrase from a context.
I explained how to obtain the base of all primes with their unique decomposition for primes 4k+1.
All this work IS ALREADY DONE!
I ALREADY HAVE ALL PRIMES 2<p<2^32 WITH THEIR UNIQUE DECOMPOSITIONS!
SO A CLIENT WILL NOT NEED TO PRODUCE OR EVEN TO CHECK THESE NUMBERS TO PRIMARITY!
THEY WILL BE GIVEN TO A CLIENT AS IS, WITH THEIR DECOMPOSITIONS ALREADY DONE!
AND EVERY TIME ONLY A VERY SMALL SET OF THEM (maybe 6-7 at once). See example above.
A client will need only to compose different diagonals from the set of primes in way I described already several times,
and to check are there between diagonal decompositions the edges and face diagonals satisfying to conditions.

For your attention, my program would use less than 2MB Ram for ANY diagonal for ANY moment of runtime!
Robert Gerbicz hat geschrieben:ps. Reading again those messages, I'm not sure what you want to search. If in fact you want to cover g<2^64, then those tables would be much bigger. Or in other case I don't see the proof that g has no prime divisor larger than 2^32. This is a hole.
About g with divisor larger than 2^32 I'll share my thoughts later.
For today I don't see that you understand my idea basically.

Robert Gerbicz
PDA-Benutzer
Beiträge: 56
Registriert: 08.06.2010 19:06

### Re: [sub-project] Perfect cuboid

You still haven't answered to my questions. Let another example: g=18446744073709550105<2^64. For this g=5*13*p, where p>2^32. Where is the proof that this g can't be the space diagonal for a perfect Euler brick (I don't see). This example also shows that there are at least approx. primepi(2^64/5/13)/2~3198681033135654 such numbers only in this class.

About generating g numbers: this is also interesting. I would say that this is trivial. But what you are write is different from backtracking and everything. You write some numbers then "and so on..." this is clearly not a definition.

And stop this style/shouting. I think I answered/asked in a normal way.

x3mEn
XBOX360-Installer
Beiträge: 99
Registriert: 20.03.2011 22:23

### Re: [sub-project] Perfect cuboid

Robert Gerbicz hat geschrieben:You still haven't answered to my questions. Let another example: g=18446744073709550105<2^64. For this g=5*13*p, where p>2^32. Where is the proof that this g can't be the space diagonal for a perfect Euler brick (I don't see). This example also shows that there are at least approx. primepi(2^64/5/13)/2~3198681033135654 such numbers only in this class.
A good question.
You are right, there are a lot of primes p=4k+1, 2<p<2^64/5/13
And as a fact unfortanately we couldn't run all of them.
Because only to store all of them it needs more than 50000Tb (my estimate).
But we could take a goal to check all g<2^64, who are a product of all primes p=4k+1, where, for example, p<1'000'000'000'000.
This goal is achievable.

Now about big divisors of g.
If g<2^64 and one of his factors f>2^32, all other factors are less than 2^32, it's clear.
Thus g can have only one big divisor f>2^32.
Therefore we no need to keep all primes 4k+1, p>2^32 to generate these g's.
We only need to organize some cache (buffer) to keep a constant amount of primes 4k+1, p>2^32

The base of primes 4k+1 p<2^32 needs to be saved constantly.
Big primes will be saved in cache.
So every time we need to generate a new package of WU's, we take 1 prime from cache and compose it with all possible primes from consistantly saved base. "All possible primes" means that a product of all primes is less than 2^64.

This is a reason why I propose to split the project to 2 phases:
phase 1: to generate and check all diagonals as a product of possible compositions of primes p=4k+1 from the base, where p<2^32.
phase 2: to generate and check as much as possible diagonals, who are a product of 1 prime from sliding up cache and all possible primes from the 1st base.

A good new is that a difficulty of checking any g depends only on powers of factors and doesn't depend on values of factors.
So, any g=5*13*p, where p is prime 4k+1 leads to equal amount of decompositions.
According to Dirichlet formula the amount of decompositions of g^2=5^2*13^2*p^2 is: [((2+1)(2+1)(2+1)+1)/2] = 14.
g=5*13*17 and g=5*13*p, where p is some big prime 4k+1, have the same amount of decompositions and therefore the same level of difficulty.
The same level of difficulty means the similar time for checking. Later I'll explain why the equal level of difficulty doesn't mean the equal run time.
Also I'll share my thought about how to estimate the difficulty of workunit later, when all other questions will be cleared.

As bigger the greatest factor of g is, as smaller is a time of checking whole available compositions of this big factor with primes p=4k+1, p<2^32 from the 1st base.
Robert Gerbicz hat geschrieben: About generating g numbers: this is also interesting. I would say that this is trivial. But what you are write is different from backtracking and everything. You write some numbers then "and so on..." this is clearly not a definition.
Do you want I write mathematically strong definition how obtain the next number from the previous one?
Do you really not understand my description?
I suppose you understand, but you simply anticipated my style of description or my tone.
But I really fell that you did't read or understand what I have explained before, when you write, for example, the next:
By your method it would need to check 10^24/sqrt(log(10^12))~10^23 different \$g\$ values just to reach this record.
instead of g = 5^4*13^3*17^1*29^1*41^5*53^1 = 4156733166885008125 will be checked from the very start.
Or when you write
And from that message: "Will get 2'147'516'416 records."
And that would cost 16GB Ram (if you store it as two int values). That's too much, here.
My code would use less than 32MB Ram for X<1e13.
when I explained how I've obtained the base of all primes and their decompositions up to 2^32.
I never said that a client will need to do this.
I supposed you understand for what the base of primes are generated.
And so on, and so on...

I oppologize and please excuse me again.
I'll try to be more loyal to questions when I think I've already explained above.

Robert Gerbicz
PDA-Benutzer
Beiträge: 56
Registriert: 08.06.2010 19:06

### Re: [sub-project] Perfect cuboid

You also haven't answered to my question that if you have a better bound or no than the known: g<=(X^2-1)/2. Because applying this if for example you could reach g<2^63, in this case you would prove the conjecture only for X<2^32 by a huge computation.

x3mEn
XBOX360-Installer
Beiträge: 99
Registriert: 20.03.2011 22:23

### Re: [sub-project] Perfect cuboid

Robert Gerbicz hat geschrieben:You also haven't answered to my question that if you have a better bound or no than the known: g<=(X^2-1)/2. Because applying this if for example you could reach g<2^63, in this case you would prove the conjecture only for X<2^32 by a huge computation.
phase 1: we will check all g<2^64, which the largest factor is less than 2^32
phase 2: we will check all g<2^64, which the largest factor is greater than 2^32 up to, for example, 2^40.

As a result of this kind of seach, we either find a perfect cuboid(s), or will be able to say:
1.If a perfect cuboid exists and its space diagonal is less than 2^64, the largest factor of space diagonal must be greater than 2^40
However we will also be able to say:
2.If a perfect cuboid exists, its space diagonal must be greater than 2^40
This conclusion can be drawn from the existing results of the known traditional search,
so I will not notice this conclusion as the main result.

The directions of searching are different for the search by the smallest edge (traditional search) and for the search by the space diagonal (my method).
So we can not say that we will continue the traditional searching or even recheck its results.
We can say that we change the focus of searched object and take a look to the same problem from the another point of view.
The profit of this kind of search is that during this search we can find a perfect cuboid that can not be found by the traditional search, because 1, 2 or even 3 edges could be greater than 10^11. Actually as you can see, during decomposition of space diagonal to a sum of squares, we are checking edges-candidates, which may be absolutely different, from 1 up to G/sqrt(3). So if G is closer to 2^64, the smalest possible edge X can be close to 2^64/sqrt(3) and we'll check it!
As you knew, the traditional search is limited to 10^11 for X (or something about).

From the other hand, the traditional search may find X,Y,Z, where G=sqrt(X^2+Y^2+Z^2) is integer, G>2^40 and its largest factor is greater than 2^40. These diagonals are unreachable by my method.

So, every search method has its own space of work. And these spaces are not comparable.

x3mEn
XBOX360-Installer
Beiträge: 99
Registriert: 20.03.2011 22:23

### Re: [sub-project] Perfect cuboid

I think if we'll try, we could find even the 3rd method of searching, based, for example, on running over face diagonals.
But I don't know any useful property of face diagonal which helps us to narrow the search.

I think that g = ? p(i)^a(i) is very-very useful property for searching a primitive perfect cuboid.
When I say 'primitive', I mean the smallest in its class.

Every odd number has 4k+1 and/or 4k+3 prime factors in its decomposition to divisors.
How many odd numbers less than 2^64 has only 4k+1 primes in its decomposition?
The answer to this question will give us a view, how many diagonals we will need to run over.

For a more realictic view, we can ask even the next:
How many odd numbers less than 2^64 has only 4k+1 primes in its decomposition to divisors, if the largest divisor is less than 2^32 (2^40 or any other number, that we will set as a goal)

Robert Gerbicz
PDA-Benutzer
Beiträge: 56
Registriert: 08.06.2010 19:06

### Re: [sub-project] Perfect cuboid

x3mEn hat geschrieben: For a more realictic view, we can ask even the next:
How many odd numbers less than 2^64 has only 4k+1 primes in its decomposition to divisors, if the largest divisor is less than 2^32 (2^40 or any other number, that we will set as a goal)
Why not simulate it? For 100000 random numbers gives 595 such numbers. So we can expect approx. 595/100000*2^64~10^17 numbers to test. It's a pretty huge. Only for one number on average you should check thousands of triangle pairs.