Perfect Cuboid, Задача про цілочисельний паралелепіпед |
Привіт Гість ( Вхід | Реєстрація )
Perfect Cuboid, Задача про цілочисельний паралелепіпед |
x3mEn |
Aug 6 2010, 00:01
Пост
#1
|
snow catcher Група: Trusted Members Повідомлень: 2 213 З нами з: 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) |
x3mEn |
Jan 30 2011, 14:03
Пост
#31
|
snow catcher Група: Trusted Members Повідомлень: 2 213 З нами з: 4-August 07 Користувач №: 563 Стать: Чол Free-DC_CPID |
Далі.
Якщо число n має m розкладів на суму квадратів n = x(i)^2 + y(i)^2, то число 4n теж має m розладів, до того ж самі розклади утворюються із розкладів n ще простіше, аніж для 2n: 4n = 2^2 * n = (2x)^2 + (2y)^2 Давайте тепер повернемося до нашої задачі. a^2 + b^2 = d^2 a^2 + c^2 = e^2 b^2 + c^2 = f^2 a^2 + f^2 = g^2 Ребра a, b, c мають бути різні, це зрозуміло, тому для g^2 має існувати як мінімум 3 різні розклади на суми квадратів: g^2 = a^2 + f^2 g^2 = b^2 + e^2 g^2 = c^2 + d^2 Для того, щоб n = g^2 розкладалося на суму квадратів, потрібно, щоб у розкладі n прості числа 4k+3 були представлені у парних ступенях. До того ж n має бути повним квадратом, а це можливо тоді і тільки тоді, коли всі прості множники n представлені у парних ступенях. Тепер доведемо, що діагональ мінімального ідеального кубоїда є непарним числом. По-перше зазначимо, що якщо ідеальний кубоїд існує, значить їх існує нескінченно багато. Адже лінійно збільшуючи "габарити" кубоїда ми отримаємо так само ідеальний кубоїд. Тому задача полягає в пошуку ідеального кубоїда мінімального розміру. Припустимо, що просторова діагональ g є числом парним. Тоді, як доведено вище, має розклад на суму квадратів і число (g/2)^2. І нам відомо, яким саме єдиним чином: (g/2)^2 = (a/2)^2 + (f/2)^2 (g/2)^2 = (b/2)^2 + (e/2)^2 (g/2)^2 = (c/2)^2 + (d/2)^2 З парності g випливає парність a, b, c, d, e, f Отже кубоїд з парною просторовою діагоналлю g не є мінімальним. Висновок: парні просторові діагоналі нас не цікавлять. А значить шукана g має бути числом непарним. -------------------- (Show/Hide) |
x3mEn |
Jan 30 2011, 20:13
Пост
#32
|
snow catcher Група: Trusted Members Повідомлень: 2 213 З нами з: 4-August 07 Користувач №: 563 Стать: Чол Free-DC_CPID |
Далі.
Теорема 5. Якщо просте число p не можна представити у вигляді суми двох квадратів, і якщо сума квадратів x^2+y^2 кратна p, то кожне із цілих чисел x, y кратне p. Доведення цієї теореми наведено в пдф документі на сторінці 20. Із Теорем 1 і 5 випливає, що якщо в розкладі просторовою діагоналі g є прості числа виду 4k+3 у будь-яких ступенях, то і всі a, b, c, d, e, f кратні всім цим 4k+3, оскільки прості числа виду 4k+3 НЕ розкладаються на суму квадратів, а значить кубоїд не є мінімальним, оскільки всю систему рівнянь можна спростити, поділивши всі рівняння на число Q = П q(j)^b(j), де q(j) - попарно різні прості числа виду 4k+3, b(j) - ступені q(j). Таким чином якщо ідеальний кубоїд мінімального розміру існує, його просторова діагональ має мати вигляд добутку простих чисел виду 4k+1: g = П (p(i)^a(i)) На цьому доведення цієї чудової властивості завершено. Є питання? -------------------- (Show/Hide) |
Alien |
Jan 30 2011, 20:15
Пост
#33
|
Разработчик MolDynGrid Група: Trusted Members Повідомлень: 569 З нами з: 7-October 07 Користувач №: 594 Стать: Чол Парк машин: Q6600 2.4@3.0GHz\Asus p5kc\8Gb\8600GT\2 SATA: Sams 500Gb+ 500Gb + Seagate 400Gb |
алхимия какая-то =)
-------------------- |
A1ex01 |
Jan 31 2011, 14:53
Пост
#34
|
round catcher) Група: Trusted Members Повідомлень: 1 365 З нами з: 27-August 08 З: Kyiv Користувач №: 809 Стать: Чол Парк машин: хз*X2/2/500/хз*5870 ц7x64 |
Є питання? та да, может быстрее 3 числа в квадрате сравнить, чем делать кучу проверок? пока вникаю -------------------- |
x3mEn |
Jan 31 2011, 20:45
Пост
#35
|
snow catcher Група: Trusted Members Повідомлень: 2 213 З нами з: 4-August 07 Користувач №: 563 Стать: Чол Free-DC_CPID |
Є питання? та да, может быстрее 3 числа в квадрате сравнить, чем делать кучу проверок? пока вникаю Ну, по-перше, ще ніяких перевірок робити не треба, я тільки навів доведення, чому має дорівнювати просторова діагональ і, власне, вже дав підказку, яким чином її формувати. По-друге, якщо ти пропонуєш перебирати всі комбінації трьох чисел-ребер, то для початку порахуй, скільки взагалі існує комбінацій (a, b, c), таких, що a<b<с і a^2+b^2+c^2 < 2^128 По-третє, пдінесення до квадрату 64 бітних чисел - операція дуже витратна. А ще більш витратна - добування корення з 128 бітного числа. Ну а по-четверте, коли вирішиш проблему, як точно порахувати квадрат 64 бітного числа, а потім з точністю хоча б до третього знака після коми порахувати корінь з 128 бітного числа, приходь, розповіси. Свого часу я розповім, яким чином я уникаю проблему виходу із 64 бітного простору, хоча, по суті, перевіряю просторові діагоналі аж до 2^64, які за формулою нібито ще треба підносити до квадрату. -------------------- (Show/Hide) |
Death |
Jan 31 2011, 21:59
Пост
#36
|
<script ///> Група: Moderators Повідомлень: 6 371 З нами з: 5-November 03 З: Kyiv Користувач №: 26 Стать: НеСкажу Free-DC_CPID Парк машин: гидропарк jabber:deadjdona@gmail.com |
самое главное узнать что уже было сделано в этом направлении.
а то получится как с вайфайричем потім з точністю хоча б до третього знака після коми порахувати корінь з 128 бітного числа, приходь, розповіси. та гавно вопрос a$ = 128bitnumber$; b$ = sqrt( a$ ); printf b$; -------------------- |
molo |
Jan 31 2011, 22:17
Пост
#37
|
Трохи обжився Група: Trusted Members Повідомлень: 23 З нами з: 21-January 09 Користувач №: 906 Стать: Чол |
a$ = 128bitnumber$; b$ = sqrt( a$ ); printf b$; Mozha trohy konkretyky? Na chomu to napysano? Bil'shist' cilyh (integer) chysel na .net/java obmezujet'sja 64bit - -9,223,372,036,854,775,808 .. 9,223,372,036,854,775,807 Dlja 128bit mabut' pryjdet'sja svij 'type' vvodyty, ale to vzhe sprava realizaciji. Chastkovo bude opydsano tut - http://perfectcuboid.com/forum/4-development UPD .NET - decimal value type - 79,228,162,514,264,337,593,543,950,335. -------------------- |
Death |
Feb 1 2011, 10:58
Пост
#38
|
<script ///> Група: Moderators Повідомлень: 6 371 З нами з: 5-November 03 З: Kyiv Користувач №: 26 Стать: НеСкажу Free-DC_CPID Парк машин: гидропарк jabber:deadjdona@gmail.com |
та ні на чому. абстракція.
я хотів сказати що це справа компілятора обчислювати корені й іншу фігню. людина розробляє алгоритм - машина рахує. -------------------- |
vitalidze1 |
Feb 1 2011, 12:22
Пост
#39
|
ЮЗЕР Група: Trusted Members Повідомлень: 1 367 З нами з: 17-May 09 З: Вінниця Користувач №: 1 029 Стать: Чол Free-DC_CPID Парк машин: ~15-20 компліхтерів. |
Йоптіль, як побачив ці квадрати, логарифми і іншу поєбень, аж мурашки по шкірі побігли.
PS. математику терпіти не можу -------------------- |
x3mEn |
Feb 1 2011, 18:53
Пост
#40
|
snow catcher Група: Trusted Members Повідомлень: 2 213 З нами з: 4-August 07 Користувач №: 563 Стать: Чол Free-DC_CPID |
vitalidze1,
ну ясно, тру кранчер -------------------- (Show/Hide) |
A1ex01 |
Feb 1 2011, 22:15
Пост
#41
|
round catcher) Група: Trusted Members Повідомлень: 1 365 З нами з: 27-August 08 З: Kyiv Користувач №: 809 Стать: Чол Парк машин: хз*X2/2/500/хз*5870 ц7x64 |
По-третє, пдінесення до квадрату 64 бітних чисел - операція дуже витратна. А ще більш витратна - добування корення з 128 бітного числа. Ну а по-четверте, коли вирішиш проблему, як точно порахувати квадрат 64 бітного числа, а потім з точністю хоча б до третього знака після коми порахувати корінь з 128 бітного числа, приходь, розповіси. SSEx пробовал?-там регистры 128бит -------------------- |
A1ex01 |
Mar 25 2011, 17:56
Пост
#42
|
round catcher) Група: Trusted Members Повідомлень: 1 365 З нами з: 27-August 08 З: Kyiv Користувач №: 809 Стать: Чол Парк машин: хз*X2/2/500/хз*5870 ц7x64 |
x3mEn, по кубоиду
D^2=a^2+b^2+c^2 dab^2=a^2+b^2 dbc^2=b^2+c^2 dac^2=a^2+c^2 dab^2+dbc^2+dac^2=2(a^2+b^2+c^2)=2D^2 -сумма квадратов диагоналей четная, значит 2 диагонали нечетные или три четные =>D -четное -------------------- |
x3mEn |
Mar 25 2011, 20:09
Пост
#43
|
snow catcher Група: Trusted Members Повідомлень: 2 213 З нами з: 4-August 07 Користувач №: 563 Стать: Чол Free-DC_CPID |
A1ex01,
поясни, як ти зробив висновок, що з непарності двох із трьох діагоналей випливає парність просторової діагоналі. Контраргумент: D^2=a^2+b^2+c^2 dab^2=a^2+b^2 dbc^2=b^2+c^2 dac^2=a^2+c^2 неп^2=пар^2+пар^2+неп^2 пар^2=пар^2+пар^2 неп^2=пар^2+неп^2 неп^2=пар^2+неп^2 В дійсності ти вивів ще одну властивість кубоїда: у ньому дві з трьох лицьових діагоналей непарні. -------------------- (Show/Hide) |
Allineer |
Mar 25 2011, 22:55
Пост
#44
|
мрію про ферму... Група: Trusted Members Повідомлень: 186 З нами з: 15-February 11 Користувач №: 1 637 Стать: Чол |
A1ex01, x3mEn, ребят, простите... а вы сейчас с кем разговариваете?
|
x3mEn |
Mar 26 2011, 00:25
Пост
#45
|
snow catcher Група: Trusted Members Повідомлень: 2 213 З нами з: 4-August 07 Користувач №: 563 Стать: Чол Free-DC_CPID |
Allineer,
розмова почалась ось тут: https://distributed.org.ua/forum/index.php?...indpost&p=66404 продовжена ось тут: http://perfectcuboid.com/forum/6---/9 перекладена ось тут: http://www.rechenkraft.net/phpBB/viewtopic.php?f=56&t=11559 продубльована ось тут: http://perfectcuboid.com/forum/4-development/28-theory Якщо сильний математик чи програміст (а краще і той і той одночасно), приєднуйся до розмови, you are welcome! -------------------- (Show/Hide) |
Lo-Fi Версія | Поточний час: 26th September 2024 - 08:54 |