Perfect Cuboid, Задача про цілочисельний паралелепіпед Налаштування

[x3mEn]

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

Досі невідомо, чи існує такий паралелепіпед. Комп'ютерний перебір не знайшов жодної цілочисельної цеглини з ребрами до 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

[re_SET]

molo, Насколько сложная задача в плане выч. мощностей?

[molo]

molo, Насколько сложная задача в плане выч. мощностей?

Хороше питання, re_SET!

Передусім об’єм обрахунків буде залежати лід алгоритму. x3mEn уже зробив певні дослідження в цьому напрямку.

Пригадую я вже робив заміри на десктопному процесорі (див. вище по темі)
Повторивши результати:

1.6GHz processor - 1 ядро (laptop)
10^9 комбінацій ~ 5хв – простий перебір

Щоб обрахувати кубоід з 10^6 ( 1-1,000,000):
10^6 * 10^6 * 10^6 = 10^18 комбінацій
10^18 комбінацій / (10^9 комб/5хв) = 10^9 циклів по 5хв = 5*10^9 хв = 83,333,333 год = 3,472,222 доби = 9,512 роки

Переведемо на 1GHz:

Щоб обрахувати кубоід з 10^6 на 1GHz (10^18 комбінацій):
9,512 * 1.6 = 15,219 роки

Щоб обрахувати кубоід з 10^11 на 1GHz (10^33 комбінацій) - повторити теперішні обрахунки:
10^33 / 10^18 = 10^15 циклів по 15,219 роки
10^15 * 15,219 роки ~ 15 * 10^15 років

Так як навіть зараз процесори мають більші потужності ~ 2*2.5 = 5GHz. Не кажучи про 6-ти ядерні від AMD – 3.5GHz * 6core = 21GHz. Тому з часом швидкість обрахунків буде тільки зростати в рази.

Основною складовою буде, як завжди, в розподільних обчисленнях, буде кількість учасників.

Виглядає досить амбітно і довготривало.