Привіт Гість ( Вхід | Реєстрація )

> Perfect Cuboid, Задача про цілочисельний паралелепіпед
x3mEn
Aug 6 2010, 00:01
Пост #1


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID





Раціональний кубоїд (або цілочисельна цеглина, або ідеальний кубоїд) — прямокутний паралелепіпед,
у якого всі сім основних величин (три ребра, три лицьових діагоналі і просторова діагональ) є цілими числами, є однією з відкритих математичних проблем
Інакше кажучи, раціональний кубоїд — цілочисельне рішення системи діофантових рівнянь.

Досі невідомо, чи існує такий паралелепіпед. Комп'ютерний перебір не знайшов жодної цілочисельної цеглини з ребрами до 10^11.
Втім, знайдено кілька «майже цілочисельних» паралелепіпедів, у яких цілочисельними є всі величини, крім однієї:
— одна з лицевих діагоналей не ціле число.
, — одне з ребер не ціле число.
Велика кількість паралелепіпедів Ейлера (з нецілою просторовою діагоналлю, див. нижче).
Косокутні паралелепіпеди, у яких всі сім величин цілі. При цьому досить одного непрямого кута.
У 2005 році тбіліський студент Лаша Маргішвілі запропонував доведення, що цілочисельний кубоід не існує — однак на 2009 рік робота так і не пройшла перевірку незалежними вченими.

Паралелепіпед Ейлера
Прямокутний паралелепіпед, у якого цілочисельні тільки ребра і лицьові діагоналі, називається ейлеровим.
Найменший з паралелепіпедів Ейлера — (240, 117, 44), з лицьовими діагоналями 267, 244 і 125.
Ще кілька паралелепіпедів Ейлера:
(275, 252, 240),
(693, 480, 140),
(720, 132, 85),
(792, 231, 160).
Ейлер описав два сімейства таких паралелепіпедів (звідси назва). Втім, повного опису всіх паралелепіпедів Ейлера також немає.
Відомі такі вимоги до ейлерового паралелепіпеда (а значить, і до цілочисельної цеглини):
- Одне ребро ділиться на 4, друге ділиться на 16, третє непарне (якщо, звичайно, він примітивний — тобто, НСД (a, b, c) = 1).
- Одне ребро ділиться на 3 і ще одне — на 9.
- Одне ребро ділиться на 5.
- Одне ребро ділиться на 11.
- Одне ребро ділиться на 19.
- Одне ребро або просторова діагональ діляться на 13.
- Одне ребро, лицьова або просторова діагональ діляться на 17.
- Одне ребро, лицьова або просторова діагональ діляться на 29.
- Одне ребро, лицьова або просторова діагональ діляться на 37.
- Добуток ребер, лицьових і просторової діагоналі має ділитися на 2^8·3^4·5^3·7·11·13·17·19·29·37

Це повідомлення відредагував x3mEn: Oct 22 2013, 09:16


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
9 Сторінки V < 1 2 3 4 > »   
Reply to this topicStart new topic
Відповідей(15 - 29)
Death
Jan 28 2011, 22:59
Пост #16


<script ///>
**********

Група: Moderators
Повідомлень: 6 429
З нами з: 5-November 03
З: Kyiv
Користувач №: 26
Стать: НеСкажу
Free-DC_CPID
Парк машин:
гидропарк
jabber:deadjdona@gmail.com



список простых чисел примерно до миллиарда давно известен.
проверить их на форму 4к+1 - 10 минут.

надо просто этот список нагуглить. ещё 2 минуты.

быстрее

Welcome to Prime-Numbers.org. This website provides entire small prime numbers list. You can browse all small prime numbers(small than 10000000000) here. ...
www.prime-numbers.org/

олсо

The Goldbach conjecture verification project reports that it has computed all primes below 1018.[1] That means 24,739,954,287,740,860 primes, but they were not stored. There are known formulas to evaluate the prime-counting function (the number of primes below a given value) faster than computing the primes. This has been used to compute that there are 1,925,320,391,606,803,968,923 primes (roughly 2×10^21) below 10^23.


--------------------
wbr, Me. Dead J. Dona OGR-27
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Jan 28 2011, 23:02
Пост #17


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID



Я сподіваюсь, що після усього мною сказаного зрозуміло, що цей проект має дуже багато спільного з PrimeGrid. Я, до речі, намагався налагодити контакти з ідейним керівником PrimeGrid. Його зацікавила моя ідея, але не більше. Власне через те, що їх метою є пошук простих чисел, а моєю - використання бази простих чисел для власного субпроекту, я думаю, наша переписка далі балачок не просунулась.
Власне, якщо б мати базу всіх простих чисел до (2^64)/(5^2), можна було б зайнятися прогою для нарізки завдань.
Дійсно, спочатку треба дізнатися, скільки така база буде важити.
Я сподіваюсь, що не більше пари гіг
Якщо б так, можна було б спробувати порахувати, скільки завдань треба буде нарізати, ну і скільки це загалом триватиме.


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Jan 28 2011, 23:17
Пост #18


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID



(Death @ Jan 28 2011, 22:59) *

roughly 2х10^21 below 10^23

(2^64)/(5^2) = ~ 7.3*10^18
Якщо в загальній масі простих чисел приблизно 2%, а нас цікавлять виду 4k+1, тобто десь половина, отже це 1% від 7.3*10^18, тобто десь 7.3*10^16
Для зберігання одного числа все одно треба буде виділяти 64 біта, получається, що всього для зберігання база має бути 7.3*10^16 * 8 байт = 56'294Тб.
Мда, трохи забагато...

Я здається ніде не помилився в розрахунках?
Навіть якщо замість 64 біт використовувати якийсь тип із динамічним виділенням розміру, все одно багато виходить...


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Jan 28 2011, 23:36
Пост #19


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID



До речі, простих чисел менших за 2^32 якщо теж близько 2%, для того, щоб їх всіх зберігати треба лише щось близько 350Мб,
а для 2^48 - 858Гб. Якщо подумати, не так вже і багато. molo, може для початку спробувати сили в діапазоні до 2^48?


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Death
Jan 29 2011, 00:00
Пост #20


<script ///>
**********

Група: Moderators
Повідомлень: 6 429
З нами з: 5-November 03
З: Kyiv
Користувач №: 26
Стать: НеСкажу
Free-DC_CPID
Парк машин:
гидропарк
jabber:deadjdona@gmail.com



не, там дальше их количество уменьшается.
пи(х) нелинейно.


--------------------
wbr, Me. Dead J. Dona OGR-27
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Jan 29 2011, 00:36
Пост #21


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID



(Death @ Jan 29 2011, 00:00) *

не, там дальше их количество уменьшается.
пи(х) нелинейно.

На 10 млрд - 4.55%, на 10^23 - 2%
від цього нічого особливо не міняється.
ну, на 2^48 буде не 900Гб, а 2Тб.
Подумаєш, терабайт туда, терабайт сюда... smile.gif


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
A1ex01
Jan 29 2011, 09:33
Пост #22


round catcher)
********

Група: Trusted Members
Повідомлень: 1 395
З нами з: 27-August 08
З: Kyiv
Користувач №: 809
Стать: Чол
Парк машин:
хз*X2/2/500/хз*5870 ц7x64



пока разобрал шо на рисунке blink.gif
перерисовал по своему

Приєднане зображення

зы: добавил dab, dac


--------------------
Stats: RC5-72 OGR-(26 /27 /28 ) Mag@(free-dc /boinc)
support: BTC 3Po6aejsoZM7bQvo138fuYwaLc67bzMfEr
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Jan 29 2011, 10:29
Пост #23


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID



A1ex01,
так зрозуміліше.
тільки я б діагоналі назвав по іншому.
Адже загалом задача зводиться до вирішення системи діафантових рівнянь
a^2 + b^2 = d^2
a^2 + c^2 = e^2
b^2 + c^2 = f^2
a^2 + f^2 = g^2
Хоча, звичайно, якими саме літерами назвати грані і діагоналі, немає особливого значення.


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Jan 29 2011, 10:44
Пост #24


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID



Я переспав з цією проблемою, де зберігати прості числа і прийшов до такої думки:
якщо мета - перебрати всі діагоналі в діапазоні до 2^64, а діагональ утворюється добутком простих чисел, то достатньо отримати базу простих чисел в діапазоні від 2 до 2^32, адже будь-які діагоналі, що утворюються добутком, в якому присутнє просте число, більше за 2^32, не може містити іншого простого числа, більшого за 2^32. Отже для формування завдань з використанням простих чисел, більших за 2^32, достатньо буде тримати базу простих чисел від 2 до 2^32, а в діапазоні від 2^32 до 2^64 організувати вікно, що буде рухатись вгору по мірі виконання завдань.
Таким чином прості числа в діапазоні від 2^32 до 2^64 будуть шукати окремим підпроектом і немає необхідності їх десь зберігати.
Єдине що, одним з бонусів підпроекту має бути оголошення всіх знайдених простих чисел в діапазоні від 2^32 до 2^64 на окремий сервіс, який займається збиранням простих чисел, наприклад у той самий www.prime-numbers.org, якщо в них оголошення простих чисел передбачено...


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
re_SET
Jan 29 2011, 20:47
Пост #25


кранчер зі стажем
******

Група: Trusted Members
Повідомлень: 465
З нами з: 26-January 09
З: Волинська обл., смт. Любешів
Користувач №: 911
Стать: Чол
Парк машин:
1х Athlon X2 BE2300 (2.2 Ghz) 1x C2D E8200 1x C2D E2180 (2.34 Ghz) 1x C2D E2160 1x C2D E5200 (2.9 Ghz) 9x C2D E6500 (Up 3.24 Ghz) 1x C2Q Q8300 (Up 3 Ghz)



(x3mEn @ Jan 29 2011, 10:44) *

Я переспав з цією проблемою, де зберігати прості числа і прийшов до такої думки:
якщо мета - перебрати всі діагоналі в діапазоні до 2^64, а діагональ утворюється добутком простих чисел, то достатньо отримати базу простих чисел в діапазоні від 2 до 2^32, адже будь-які діагоналі, що утворюються добутком, в якому присутнє просте число, більше за 2^32, не може містити іншого простого числа, більшого за 2^32. Отже для формування завдань з використанням простих чисел, більших за 2^32, достатньо буде тримати базу простих чисел від 2 до 2^32, а в діапазоні від 2^32 до 2^64 організувати вікно, що буде рухатись вгору по мірі виконання завдань.
Таким чином прості числа в діапазоні від 2^32 до 2^64 будуть шукати окремим підпроектом і немає необхідності їх десь зберігати.
Єдине що, одним з бонусів підпроекту має бути оголошення всіх знайдених простих чисел в діапазоні від 2^32 до 2^64 на окремий сервіс, який займається збиранням простих чисел, наприклад у той самий www.prime-numbers.org, якщо в них оголошення простих чисел передбачено...

cool2.gif


--------------------
Нельзя попасть в Рай одной религии, не попав при этом в Ад всех остальных...





(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
A1ex01
Jan 29 2011, 22:01
Пост #26


round catcher)
********

Група: Trusted Members
Повідомлень: 1 395
З нами з: 27-August 08
З: Kyiv
Користувач №: 809
Стать: Чол
Парк машин:
хз*X2/2/500/хз*5870 ц7x64



(x3mEn @ Aug 28 2010, 19:44) *


Просторова діагональ може бути тільки числом, що розкладається на прості числа виду 4k+1.


напиши почему так, а то ссылки твои здохли
по 29 гипотеза Альошина -нагуглил:
"29. Целочисленного параллепипеда не существует (Разраб.)"

простые числа на прайме:
http://www.primegrid.com/torrent/

http://www.primegrid.com/download/primes_iso/


--------------------
Stats: RC5-72 OGR-(26 /27 /28 ) Mag@(free-dc /boinc)
support: BTC 3Po6aejsoZM7bQvo138fuYwaLc67bzMfEr
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Jan 29 2011, 23:19
Пост #27


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID



A1ex01,
я збирався це зробити.
основний дуже важливий документ, з якого я зробив цей висновок, доступний за адресою
http://kvant.mirror1.mccme.ru/pdf/1999/03/kv0399senderov.pdf

Доведення буде складатися з деяких частин.
Нажаль треба багато часу, щоб навести його тут цілком, тому почну з початку:

Теорема 1.
Всякое нечётное число, представимое в виде суммы квадратов двух целых чисел при делении на 4 даёт остаток 1, а не 3.
Доказательство:
Из двух квадратов, сумма которых нечетна, обязательно один четен, а другой нечетен.
Квадрат четного числа нацело делится на 4, а квадрат нечетного числа при делении на 4 даёт остаток 1.

Теорема 2.
Любое простое число p, которое при делении на 4 даёт остаток 1, представимо в виде суммы квадратов двух натуральных чисел.
Доказательство состоит из двух лемм:
Лемма 1.
Для любого простого числа p = 4k+1, где k - натуральное, существует такое целое число m, что m^2+1 кратно p.
Лемма 2.
Любой простой делитель p числа m^2+1, где m - целое, представим в виде суммы квадратов двух натуральных чисел.

Из Теорем 1 и 2 следует, что простое число p>2 не представимо в виде суммы двух квадратов, если оно имеет вид 4k+3, и представимо, если p = 4k+1

Критерий Жирара.
Натуральное число представимо в виде суммы квадратов двух целых чисел тогда и только тогда, когда в его разложении на простые множители любой простой множитель вида 4k+3 входит в чётной степени.


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
A1ex01
Jan 30 2011, 09:27
Пост #28


round catcher)
********

Група: Trusted Members
Повідомлень: 1 395
З нами з: 27-August 08
З: Kyiv
Користувач №: 809
Стать: Чол
Парк машин:
хз*X2/2/500/хз*5870 ц7x64



теорема 1 понятна и так, особенно в двоичной системе

теорема 2 о простых числах, почему диагональ всегда простое число?
по моему это частный случай, т.е. если диагональ простое -тогда твоя формула...


--------------------
Stats: RC5-72 OGR-(26 /27 /28 ) Mag@(free-dc /boinc)
support: BTC 3Po6aejsoZM7bQvo138fuYwaLc67bzMfEr
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
molo
Jan 30 2011, 11:06
Пост #29


Трохи обжився
**

Група: Trusted Members
Повідомлень: 23
З нами з: 21-January 09
Користувач №: 906
Стать: Чол



(A1ex01 @ Jan 29 2011, 22:01) *


Djakuju, A1ex01

Vygljadaje, scho po torrentu nihto ne rozdaje.
Ale prjami linky pracjujut' - probuju vykachaty i pidnjaty. Nevpevnenyj scho tam - bachu obrazy DVD, ale scho v seredyni...

Htos' mozhlyvo zustrichav dazu/spysok - Euler brick (Прямоугольный параллелепипед, у которого целочисленные только рёбра и лицевые диагонали, называется эйлеровым. )? To by moglo pomogty na pershyh stadijah rozrahunkiv, a takozh dlja perevirky pravyl'nosti nashyh teorij.


--------------------
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Jan 30 2011, 11:23
Пост #30


snow catcher
*********

Група: Moderators
Повідомлень: 2 225
З нами з: 4-August 07
Користувач №: 563
Стать: Чол
Free-DC_CPID



A1ex01,
якраз збирався написати другу частину.

Загальна формула для представлення добутку суми двох квадратів у вигляді суми двох квадратів наступна:
(a^2+b^2)(x^2+y^2) = a^2*x^2 + a^2*y^2 + b^2*x^2 + b^2*y^2,
додамо і віднімемо 2axby:
(a^2+b^2)(x^2+y^2) = a^2*x^2 + 2axby + b^2*y^2 + a^2*y^2 - 2axby + b^2*x^2 = (ax + by)^2 + (bx - ay)^2 (1)
Запам'ятаємо цю формулу, вона нам ще дуже знадобиться.

а) Якщо число n є сумою двох квадратів, то і число 2n представляється у вигляді суми двох квадратів.
Доведення:
Якщо n = x^2 + y^2, то
(x+y)^2 + (x-y)^2 = x^2 + 2xy + y^2 + x^2 - 2xy + y^2 = 2x^2 + 2y^2 = 2(x^2+y^2) = 2n
Тобто
2n = (x+y)^2 + (x-y)^2
Власне, цю формулу можно отримати і з формули (1), якщо згадати, що 2 = 1^2 + 1^2, тобто в формулі (1) a і b = 1.

Теорема 3 (основна теорема арифметики):
Ціле число розкладається на прості множники одним єдиним способом (з точністю до перестановки множників і асоціативності)
Доведення цієї теореми залишимо за дужками.

Будь-яке число n можна представити у вигляді добутку простих чисел трьох типів: 2^a, p(i)^a(i), q(j)^b(j),
де p(i) - прості числа виду 4k+1, a(i) - ступінь числа p(i)
q(j) - прості числа виду 4k+3, b(j) - ступінь числа q(j).
Нехай Q = П q(j)^b(j)
Тоді, якщо Q не є повним квадратом (а це можливо лише тоді, коли всі b(j) парні), то n не можна розкласти на суму квадратів (критерій Жирара).
Якщо ж Q є повним квадратом, то кількість розкладів n дорівнює кількості розкладів числа П(p(i)^a(i)) на суми квадратів

Теорема 4 (формула Діріхле):
Якщо число n розкладається на суму квадратів, то кількість представлень дорівнює [ (П (a(i)+1) +1) / 2 ] (2)
(Якщо кількість множників рівна 0, то добуток вважається рівним 1. Представлення, що відрізняються порядком доданків, не розрізняються)

Запам'ятайте і цю формулу. Вона нам теж знадобиться для перевірки, що ми правильно розклали число на всі можливі суми квадратів.
Доведення цієї теореми можна знайти у тому ж самому пдф-документі (ст.21)

Основні висновки з цієї теореми: :
1) всі ступені 4k+3 мають бути парними, щоб n мало розклади
2) кількість розкладів n залежить тільки від ступенів 4k+1
3) наявність чи відсутність у розкладі двійки (2) у будь-яких ступенях не впливає ні на "розкладність" n, ні на кількість розкладів

Так от, із Теореми 4 і загальної формули (1) випливає, якщо n - парне і розкладається на суму квадратів m різними способами,
то і число n/2 розкладається на суми квадратів і до того ж теж m різними способами.
При цьому способи розкладу n/2 утворюються із розкладів n одним єдиним способом.
Яким саме - залишаю вам це завдання в якості домашнього завдання. )

Отже, запам'ятаємо цей результат:
Якщо число n має m розкладів на суму квадратів n = x(i)^2 + y(i)^2, то і число 2n має m розкладів, при цьому самі розклади утворюються одним єдиним способом:
2n = (x+y)^2 + (x-y)^2
Цей факт буде використаний пізніше.


--------------------

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post

9 Сторінки V < 1 2 3 4 > » 
Reply to this topicStart new topic
5 Користувачів переглядають дану тему (5 Гостей і 0 Прихованих Користувачів)
0 Користувачів:

 



- Lo-Fi Версія Поточний час: 29th March 2024 - 14:26

Invision Power Board v1.3.3 © 1996 IPS, Inc.