[sub-project] Perfect cuboid

Fehler und Wünsche zum Projekt yoyo@home
Bugs and wishes for the project yoyo@home
Nachricht
Autor
Benutzeravatar
yoyo
Vereinsvorstand
Vereinsvorstand
Beiträge: 8045
Registriert: 17.12.2002 14:09
Wohnort: Berlin
Kontaktdaten:

Re: [sub-project] Perfect cuboid

#25 Ungelesener Beitrag von yoyo » 22.03.2011 09:30

I can host the project in yoyo@home and will take care of
- wu-generation
- validator
- assimilator

The only thing we need is a C/C++ app without any gui and optional:
- checkpoints
- progress indicator

yoyo
HILF mit im Rechenkraft-WiKi, dies gibts zu tun.
Wiki - FAQ - Verein - Chat

Bild Bild

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#26 Ungelesener Beitrag von x3mEn » 22.03.2011 09:50

yoyo hat geschrieben:I can host the project in yoyo@home and will take care of
- wu-generation
- validator
- assimilator
As I will show below, WU-generator needs to work close to DB of primes to generate WU's from the different combinations of them. So we'll need to decide what DB platform will.
Naturally I have already calculated the start size of DB of primes. There are 203'277'595 primes between 2 and 2^32. The list of primes takes about 1Gb in archive.
Below I'll explain, why primes < 2^32 are enough for the first phase of project.
But, we will not run beforehand, all one after another. :)
Zuletzt geändert von x3mEn am 22.03.2011 12:12, insgesamt 1-mal geändert.

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#27 Ungelesener Beitrag von x3mEn » 22.03.2011 10:44

Theorem 2 also known as the theorem of Fermi-Euler and fully sounds so:
Any prime number the form 4k+1, where k is a natural number, can be presented as a sum of two squares of natural numbers, besides by only one possible way.

Let's focus now on a problem, how to get decomposition of any prime 4k+1 to a sum of two squares.
As I read in the internet, effective methods now allegedly do not exist.
Most methods are based on some surplus, or construction of sequence with the search of elements of sequence, that answer certain terms. Send you, for example, to this source: ?. ?. ????? ? ????????????? ????? ? ???? ????? ???? ????????? (russian).
But the next idea slept me, how enough quickly to get decompositions to the sum of squares for all prime numbers the form 4k+1 from a certain range:

Let p = x² + y²
then x < sqrt(p) - it's clear.
p < 2^32, thus x < 2^16
and 2^16 - it's only 65536
1) Create a table of all integers from 1 to 65536.
2) Calculate the square for all numbers from this table and keep beside.
3) Then full join a table with itself with condition x <= y,
where x - a number from left table, y - a number from right table.
Will get 2'147'516'416 records.
4) Calculate a sum squares for all records.
5) After that will do group by a sum squares (P) and calculate min(x), min(y) with having count(*)=1 and oddness of P condition.
(I suppose SQL specialists understand what I mean).

As a result we will get a table with decompositions of odd numbers the form 4k+1 to a sum of squares.
Not all of them are prime, it's clear.

If translate this algorythm to SQL, it looks like:

1. Create table:
CREATE TABLE N (
X INTEGER,
SQRX INTEGER);

2. Insert into table numbers from 1 to 65536
There are several different ways, how to do it.

3. Calculate squares:
UPDATE N
SET SQRX = X*X;

4. Collect statistics for better efficiency of cross-join:
COLLECT STATISTICS ON N COLUMN (X);

5. Create temporary table:
CREATE TABLE PXY AS (
SELECT
A.SQRX + B.SQRX AS P,
MIN(A.X) AS X,
MIN(B.X) AS Y
from N AS A, N AS B
WHERE A.X < B.X
GROUP BY P
HAVING COUNT(*) = 1
AND (P MOD 2 = 1)
) WITH DATA UNIQUE PRIMARY INDEX (P);

6. Create primary table of primes (a list of all primes from 2 to 2^32 can be found, for example here):
CREATE TABLE PRIMES (
PRIME INTEGER,
UNIQUE PRIMARY INDEX (P));

7. Insert primes into PRIMES table any way you know how

8. Left join primes table and temporary table (step 5) into the target table:
CREATE TABLE PCXY AS (
SELECT
PRIMES.PRIME,
PRIMES.PRIME MOD 4 AS PCLASS,
PXY.X,
PXY.Y
FROM PRIMES
LEFT JOIN PXY
ON PRIMES.PRIME = PXY.P
) WITH DATA UNIQUE PRIMARY INDEX (PRIME);

After all these manipulation we will get a table of all primes with decomposition of primes 4k+1 to a sum of squares (the only one for every prime).
(remind, 4k+3 and 2 have not decomposition).

FYI, all these actions are already done. :)
As a result I've got 203'277'595 primes.
A distribution to prime clases is the next:
4k+1 : 101'637'064
4k+2 : 1
4k+3 : 101'640'530
Zuletzt geändert von x3mEn am 24.03.2011 15:02, insgesamt 2-mal geändert.

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#28 Ungelesener Beitrag von x3mEn » 22.03.2011 11:12

Ok, we have 4k+1 primes, we know a decomposition of every of these primes into a sum of squares,
we know that target space diagonal is a product of primes 4k+1.

Let investigate now what is the count of different primes with a product less than 2^64 = 18'446'744'073'709'551'616 ? 1.84E+19

Will write the prime numbers of kind 4k+1 and will count up them cumulative product:
5 5
13 65
17 1105
29 32045
37 1185665
41 48612265
53 2576450045
61 157163452745
73 11472932050385
89 1021090952484265
97 99045822390973705
101 10003628061488344205

Thus the maximal amount of different prime numbers in work will fold 12:
5*13*17*29*37*41*53*61*73*89*97*101 = 10'003'628'061'488'344'205

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#29 Ungelesener Beitrag von x3mEn » 22.03.2011 12:06

Running over Diagonals.

Running over Diagonals is proposed to do the next way:
All primes the form 4k+1 ordered ascending.
Any diagonal is a product of some primes form 4k+1 in some powers.
If every prime has his order number, a diagonal can be identified by a set of primes order numbers with a some power number.
If we know a start position of diagonal we can generate all next diagonals in way how we count: we add 1 to the smallest number position, if adding will exceed the position, we zeroize a current position and add 1 to the bigger and so on.

Similarly and with running over diagonals. The only difference is than every next step we add 1 to the power number of the smallest prime in set. And exceeding event is when after enlarging of power a target diagonal will more than 2^64. Checking exceeding is very simple. For this will calculate a sum of natural logarythm of primes multiplied to powers:
S (a(i)*ln(p(i))) > 64ln (2)

Now example.
The smallest prime 4k+1 is 5.
And it generate the first diagonal: g(1) = 5^1 = 5.
Check exceeding:
1*ln(5) ? 1,61
64ln(2) ? 44,36
1*ln(5) < 64ln(2)
There is not exceeding.

The next diagonal appears from previous addition 1 to the power of the least number, the same 5:
g(2) = 5^(1+1) = 5^2
Check exceeding:
2*ln(5) < 64ln(2).
True, so can move forward.
g(3) = 5^(2+1) = 5^3; 3*ln(5) < 64ln(2).
and so on up to g(27) = 5^27
27ln(5) ? 43,45
Addition other one 1 to 5th power will call exceeding:
28ln(5) ? 45,06 > 44,36 ? 64ln(2)
So stop, zeroize a power of 5 and add 1 to power of next prime in ordered set. It is 13.
g(28) = 5^0 * 13^1 = 13^1
Check exceeding:
1*ln(13) ? 2,565 < 64ln(2)
All right. Move forward. Add 1 to power of the least prime 4k+1 (again 5):
g(29) = 5^(0+1) * 13^1 = 5^1 * 13^1
Check exceeding and so on.

Moving up by this algorythm
1) we assuredly will run over all diagonals < 2^64, that appear work of prime numbers of kind 4k+1 in all various powers.
2) have a confidence, that an algorithm always conducts from the initial state to eventual, if the initial state "less than" eventual, and checking it is not difficult.
3) assigning to the clients as the initial and eventual state, be what client will run over the identical amount of diagonals and in an identical sequence.
Zuletzt geändert von x3mEn am 25.03.2011 17:13, insgesamt 1-mal geändert.

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#30 Ungelesener Beitrag von x3mEn » 24.03.2011 10:32

Decomposing a square of space diagonal on the sum of squares

Take, for example, that task is obtained all decompositions of
g² = 5^4 * 13^6 * 17^2 * 29^4 * 37^8 * 41^4
on the sum of squares.

First of all let mention that we know, how primes 4k+1 are decomposed on the sum of squares:
5 = 1² + 2²
13 = 2² + 3²
17 = 1² + 4²
29 = 2² + 5²
37 = 1² + 6²
41 = 4² + 5²

Second, we know, how the product of 2 sums of squares can be decomposed on the sum of squares:
(a² + b²) (x² + y²) = (ax + by)² + (bx - ay)² (1)
Let's note that in general case formula (1) gives us 2 different decompositions, depends on the order of a and b (or x and y, what's the same):
(a² + b²) (x² + y²) = (ax + by)² + (bx - ay)²
(b² + a²) (x² + y²) = (bx + ay)² + (ax - by)²
We are interesting only positive integers in the decomposition, thus in general case decomposition of product of 2 sums of squares (a² + b²) (x² + y²) looks like a set of
(ax + by, |bx - ay|)
(bx + ay, |ax - by|)
Let agree that the first term is always less than the second.
So the order of terms in decomposition depends on relation between these 2 terms:
ax + by vs |bx - ay|
bx + ay vs |ax - by|
In most cases an absolute of disparity is less than a sum, so let's assign that the initial order of terms is:
(|bx - ay|, ax + by)
(|by - ax|, ay + bx)
Let also note, that a set of decompositions can contain duplicates after reordering of terms.
So, after every itteration of decomposing we need to keep only distinct pairs.

Let's return to the example.
Every power of prime factors can be decomposed on the sum of squares in way:
5 has only one decomposition: 1² + 2², so 5² has:
(|2*1 - 1*2|, 1*1 + 2*2) = (0, 5)
(|1*1 - 2*2|, 2*1 + 1*2) = (3, 4)
Actually
5² = 0² + 5²
5² = 3² + 4²

Note, we have to keep a trivial decompositions like 5² = 0² + 5² while.
Obviously, any square of integer g has at least a trivial decomposition: g² = 0² + g²
But we'll discard a trivial case only after all decomposing loops.

5^4 = 5² * 5²
We already know all decompositions of 5², so can obtain all decompositions of 5^4:
5^4 = (0² + 5²)(0² + 5²)
5^4 = (0² + 5²)(3² + 4²)
5^4 = (3² + 4²)(3² + 4²)
Every equation gives us 2 possible decomposition pairs:
(0² + 5²)(0² + 5²): (0, 25) & (25, 0)
(0² + 5²)(3² + 4²): (15, 20) & (20, 15)
(3² + 4²)(3² + 4²): (0, 25) & (7, 24)
After reording of terms and discarding of duplicates obtain:
(0, 25)
(7, 24)
(15, 20)
Actually,
5^4 = 0² + 25²
5^4 = 7² + 24²
5^4 = 15² + 20²
So, we got that 5^4 has 3 different decompositions.

Keep moving on decomposing all products of the target space diagonal on sums of squares we'll obtain that
g² = 5^4 * 13^6 * 17^2 * 29^4 * 37^8 * 41^4
has 11813 different decompositions.
Let check Dirichlet formula [(? (a(i)+1)+1)/2]:
[((4+1)(6+1)(2+1)(4+1)(8+1)(4+1)+1)/2] = [(5*7*3*5*9*5+1)/2] = 11813
And what was required to prove.
Zuletzt geändert von x3mEn am 25.03.2011 17:13, insgesamt 2-mal geändert.

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#31 Ungelesener Beitrag von x3mEn » 24.03.2011 11:40

Diagonals checking

Search for edges and face diagonals, satisfying the system
a² + b² = d²
a² + c² = e²
b² + c² = f²
a² + f² = g²

With the system it follows that
g² = a² + f²
g² = b² + e²
g² = c² + d²

We'd obtained all possible decompositions of the square of a space diagonal g² to sums of two squares.

The problem is to find three pairs (a, f), (b, e), (c, d), satisfying the conditions of the system.
First, note that
a < b < c
d < e < f
a < b < d < e < f
How are related to each other c and d - is not known.
Maybe c < d, maybe d < c

Secondly, knowing the 2 pairs (a, f), (b, e), then the pair (c, d) should not look for,
c² = e² - a²
c² = f² - b²
So edge c can be deducted on one of formulas like this:
? = sqrt(f² - b²) = sqrt(f - b) * sqrt(f + b)
Well diagonal d can either be deducted from the formula
d = sqrt(g - c) * sqrt (g + c),
or you can simply search for a pair between g decompositions,
just c² + d² = g².
Please note, if you know c, you have to search and pair (c, d) and pair (d, c)

If all decompositions of g² are stored in some table TASK,
so we can search target a, b, c, d, e, f from the query:

WITH t(A, B, F, E, FBextC, C) AS
(SELECT
a.X AS A
,b.X AS B
,a.Y AS F
,b.Y AS E
,CAST(SQRT( F-B ) AS DECIMAL(25,4)) * CAST(SQRT( F+B ) AS DECIMAL(25,4)) AS FBextC
,CAST(FBextC AS BIGINT) AS C
FROM TASK a, TASK b
WHERE A > 0
AND A < B
AND B < F / SQRT(2)
AND E > A * SQRT(2)
AND ABS(FBextC-C) < 0.001
AND ((A MOD 2) + (B MOD 2) <> 2)
AND ((A MOD 2) + (B MOD 2) + (C MOD 2) = 1)
AND (((A MOD 5) = 0) OR ((B MOD 5) = 0) OR ((C MOD 5) = 0))
AND (((A MOD 7) = 0) OR ((B MOD 7) = 0) OR ((C MOD 7) = 0))
AND (((A MOD 9) = 0) OR ((B MOD 9) = 0) OR ((C MOD 9) = 0))
AND (((A MOD 11) = 0) OR ((B MOD 11) = 0) OR ((C MOD 11) = 0))
AND (((A MOD 16) = 0) OR ((B MOD 16) = 0) OR ((C MOD 16) = 0))
AND (((A MOD 19) = 0) OR ((B MOD 19) = 0) OR ((C MOD 19) = 0))
AND ((CASE WHEN ((A MOD 3) = 0) THEN 1 ELSE 0 END) + (CASE WHEN ((B MOD 3) = 0) THEN 1 ELSE 0 END) + (CASE WHEN ((C MOD 3) = 0) THEN 1 ELSE 0 END)) >= 2
AND ((CASE WHEN ((A MOD 4) = 0) THEN 1 ELSE 0 END) + (CASE WHEN ((B MOD 4) = 0) THEN 1 ELSE 0 END) + (CASE WHEN ((C MOD 4) = 0) THEN 1 ELSE 0 END)) >= 2
)
SELECT A, B, C, d.Y AS D, E, F
FROM t, TASK AS d
WHERE C = d.X
UNION ALL
SELECT A, B, C, d.X AS D, E, F
FROM t, TASK AS d
WHERE C = d.Y;

The query check the next conditions:
1. A > 0 for discarding a trivial decomposition g² = 0² + g²
2. A < B
3. as far as b < c ? b² + c² = f², thus b < f / sqrt(2)
4. as far as a < c ? a² + c² = e², thus e > a * sqrt(2)
5. a and b can't be odd simultaneously
6. 2 of the edges a, b, c must be even and 1 edge must be odd
7. 1 of the edges a, b, c must be divisible by 5
8. 1 of the edges a, b, c must be divisible by 7
9. 1 of the edges a, b, c must be divisible by 9
10. 1 of the edges a, b, c must be divisible by 11
11. 1 of the edges a, b, c must be divisible by 16
12. 1 of the edges a, b, c must be divisible by 19
13. at least two of of the edges a, b, c must be divisible by 3
14. at least two of of the edges a, b, c must be divisible by 4

All these conditions are described here: en.wikipedia.org/wiki/Perfect_cuboid
Zuletzt geändert von x3mEn am 24.03.2011 14:55, insgesamt 3-mal geändert.

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#32 Ungelesener Beitrag von x3mEn » 24.03.2011 11:45

So, I've finished my idea description.
Any questions, proposals, objections?

OriEy
Fingerzähler
Fingerzähler
Beiträge: 1
Registriert: 24.03.2011 14:18

Re: [sub-project] Perfect cuboid

#33 Ungelesener Beitrag von OriEy » 24.03.2011 14:27

"Secondly, knowing the 2 pairs (a, f), (b, e), then the pair (c, d) should not look for,
c^2 = e^2 - a^2
c^2 = f^2 - b^2
So edge c can be deducted on one of formulas like this:
? = sqrt(f^2 - b^2) = sqrt(f-b) * sqrt(f+b)"

If c has to satisfy the 2 conditions wouldn't it save time to check first if e²-a²=f²-b²? Or is there a reason I overlooked that it is satified naturally?

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#34 Ungelesener Beitrag von x3mEn » 24.03.2011 14:53

OriEy hat geschrieben:"Secondly, knowing the 2 pairs (a, f), (b, e), then the pair (c, d) should not look for,
c² = e² - a²
c² = f² - b²
So edge c can be deducted on one of formulas like this:
? = sqrt(f² - b²) = sqrt(f - b) * sqrt(f + b)"

If c has to satisfy the 2 conditions wouldn't it save time to check first if e²-a²=f²-b²? Or is there a reason I overlooked that it is satified naturally?
The problem is that a, b, e, f are int64 type (64-bit integer)
So e²-a² and f²-b² computing leads to float numbers range operations,
thus equality can't be checked enough precisely.
? = sqrt(f² - b²) = sqrt(f - b) * sqrt(f + b) leads to float numbers operations too, but a precision of sqrt for numbers < 2^64 is more higher, than equality checking for floating numbers up to 2^128. As I know, Borland Delphi float type "extended" supports max only near 19 digits of precision (64 bits).

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

Re: [sub-project] Perfect cuboid

#35 Ungelesener Beitrag von Robert Gerbicz » 26.03.2011 00:42

yoyo hat geschrieben:I can host the project in yoyo@home and will take care of
- wu-generation
- validator
- assimilator

The only thing we need is a C/C++ app without any gui and optional:
- checkpoints
- progress indicator

yoyo
Hi! Worked some days on this nice problem. My code would search also for Euler bricks! If you are interested in that I'll send the code. It would take about 90GHz years to search up to X<1e13 (where X is the odd term), and to recheck the previous unofficial searches. And this would be also a great extension of the Euler bricks table, the currently best(?) knwon table is only up to X<2^32, see http://arxiv.org/abs/math/0111229.

My program agrees with that table (checked up to 1e9).

x3mEn
Prozessor-Polier
Prozessor-Polier
Beiträge: 102
Registriert: 20.03.2011 22:23

Re: [sub-project] Perfect cuboid

#36 Ungelesener Beitrag von x3mEn » 27.03.2011 00:19

Today I have finished console app for Windows.
You can find sources attached.
pcuboid.dpr - Delphi program code
pc_32b_000000006_1 - test work unit
To test run pcuboid.exe pc_32b_000000006_1

Could somebody help with program transfer to C/C++ ?
Dateianhänge
pcuboid.0.01.zip
(66.17 KiB) 292-mal heruntergeladen

Antworten

Zurück zu „Fehler, Wünsche / Bugs, Wishes“