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

[x3mEn]

Bel, ніяк. Андрій зайнятий. Я застряг на швидкому алгоритмі декомпозиції:
http://distributed.org.ua/forum/index.php?...indpost&p=89102

[Death]

спробуй написати автору

[x3mEn]

Death, пробував, писав

[A1ex01]

Просто сайт про Perfect Cuboid давно вже є:
www.perfectcuboid.com

лежит похоже(

ап:
если соединить 2 кубоида, то пространственные диагонали образуют равнобедренный треугольник
из теоремы косинусов D =2*a/(2cos(x))=a/cos(x)
D- пространственная диагональ
a-сторона кубоида
x-угол между a и D

ап2:
если с кубоидом все так плохо, предлагаю новый проект: поиск лучшего алгоритма sha2)

[rpisarev]

Death,
до задачі по Perfect Cuboid мені вдалося долучити Andrii Muliar.
Він дуже сильно вплинув на моє бачення реалізації проекту.
Зокрема він мене переконав, що прямий перебір діагоналей - не така вже витратна операція
Я планував влаштувати генерацію діагоналей як добуток простих чисел 4k+1 у всіх можливих комбінаціях (добуток менший за наперед задане число (2^63-1)).
Але, по-перше, такий перебір наврядчи буде завершено для всіх чисел з діапазону (2; 2^63-1), навіть за умови, що вони є добутком простих чисел 4k+1 (надто вже багато просто протих чисел виду 4k+1, а для утворення діагоналі-кандидата достатньо домножити це просте на 5 (5 - мінімальне просте виду 4k+1). А простих чисел 4k+1, таких, що 5*(4k+1) < 2^63-1 ну дуже вже багато).
А по-друге, результат проекту за такого пошуку буде звучати приблизно так:
Якщо ідеальний кубоїд існує і його просторова діагональ менша за 2^63, ця діагональ у своєму розкладі на дільники має містити фактор, що більший за 2^36.
Це звучить не дуже зрозуміло, чи не так, порівняно, наприклад, з таким результатом:
Якщо ідеальний кубоїд існує, його просторова діагональ більша за 2^36.
Такий результат проекту більш зрозумілий, чи не так?

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

А я вот в отпуске снова вчера копнул в тот джава код, почитал описание автора с точки зрения математики и сходу смог написать представления 4k+1 в виде 2 квадратов и 4k+3 в виде 4-х. Скорость декомпозиции 4k+1 сводится к алгоритму разрешимости квадратичного сравнения x^2 = -1 (mod 4k+1), т.е. по сути нахождению корня из -1 в поле Z(4p+1). Пока сделал "в лоб" - перебором: математика не знает лучших методов. Но функция нахождения корня параметр, т.е. в последствии можно бесшовно заменить. Известно лишь, что их 2, один четный, второй нечетный. Надо поискать результаты современной математики - может есть быстрый алгоритм.

Так же есть функция, которая принимает 2 числа, умеет их разложить в декомпозицию 4-х (в общем случае) квадратов и выдать ответ - декомпозиция в виде 4-х квадратов от произведения двух чисел. Понятно её можно обобщить на большее число.

Алгоритма факторизации пока нет и не уверен, что успею до конца отпуска.

Сейчас это консольная программа на Python, за день-два могу переписать на Си/Си++ (без длинной арифметики). Пока начал разбираться с общем случаем представления (хотя для решения задачи перфекткуба, кажется, это и не надо)

[Rilian]

лучше на руби и выложить на гитхаб

[Володимир]

Мені чомусь здається шо просторова діагональ завжд буде нераціональним числом. Хоча х/з.

А всі інші сторони та діагоналі - в принципі разом трикутники, повинні бути поєднанням різних видів цільних прямих трикутників - http://en.wikipedia.org/wiki/Integer_triangle (Піфагора, Герона, ін.)

Тута також шось про цільні прямі трикутники та квантові координати(???) http://www.wyzant.com/Tutors/OH/Dover/7286...sian_space.aspx

Також думав подивитися на проблему так шо - всі інші діагоналі то тільки проекції просторової діагоналі на три площини..

чисто раді різноманітності тута кидаю.

Д.Р. всім привіт - вибачаюся шо пропадав....

[x3mEn]

Виніс в окрему тему.

[A1ex01]

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

В дійсності ти вивів ще одну властивість кубоїда:
у ньому дві з трьох лицьових діагоналей непарні.

походу перепутал диагонали с ребрами

надо будет покурить пол кубоида как прямоугольную пирамиду...
еще вариант - менять D, а 3 ребра вычислять через [ко]синус...

[x3mEn]

Оскільки це давня відкрита математична проблема, я думаю, що легких доведень неіснування PC не буде.

[A1ex01]

предыдущая мысль ошибочна, пришел к новой)
D=dabc
D^2=a^2+b^2+c^2
D^2= a^2+dbc^2

в треугольнике отношение диагонали к стороне:
D больше a в k1(>1) раз=> a=D/k1, D больше dbc в k2(>k1) раз=> dbc =D/k2
D^2=(D/k1)^2+(D/k2)^2 => 1=(1/k1^2+1/k2^2)^(1/2)
основная мысль была -чем больше k тем меньше числа под корнем, а сумма должна быть=1
но фольфрам выдал резалт
1<k1<2^(1/2), k2=(k1^2/(k1^2-1))^(1/2)
т.е. пространственная диагональ D больше a в число, которое больше 1 и меньше корень из 2(~1.41421356...)

[A1ex01]

ping x3mEn
шо нового?

если k1 идет к 1 то k2 в бесконечн, если k1 идет к sqr(2) то и k2 к sqr(2)? также остальные стороны/ребра
ап:
dbc/dabc=cos (dbc dabc) -угол между ними
b/dbc= cos (b dbc) -угол между ними
dabc=b/cos(угол1)/cos(угол2)

[x3mEn]

Новини такі:

Після десь місяця різноманітних експериментів у мене є готова програма із пошуку 3 видів кубоїдів:
* Perfect Cuboid
* Edge Cuboid — майже ідеальний кубоїд, де цілочисельні усі сторони, окрім одного ребра.
* Diagonal Cuboid — майже ідеальний кубоїд, де цілочисельні усі сторони, окрім однієї лицьової діагоналі.

Пошук кубоїдів відштовхується від виду просторової діагоналі.
Програма консольна, написана на чистому С (не С++), є версії для
* Windows x86
* Windows x86_64
* Linux x86
* Linux x86_64

Програма приймає на вхід 2 параметри: початок та кінець діапазону пошуку, інформація про усі знайдені кубоїди пишеться в stdout, статитика — в stderr.
Програма розрахована для пошуку аж до 2^63.

Щодо швидкості. Швидкість залежить, від 3 параметрів:
1) процесор. тут все зрозуміло.
2) 64-бітна версія сильно (~ на 60% швидше) виграє у 32-бітної.
3) діапазон. чим більші числа, тим, зрозуміло, складніші завдання

Наведу тут приклад логу програми із статистичною інформацією:

Perfect Cuboid 1.06 (Windows 64-bit)
Copyright 2017, Alexander Belogourov aka x3mEn

Command line parameters : 244575149939 245273211192
Research Range borders  : 244575149941 245273211189
Total amount of Numbers : 174515313

Elapsed time            : 01:08:00.091 s
Candidates investigated : 30429317
Perfect Cuboids found   : 0
Edge Cuboids found      : 16
Diagonal Cuboids found  : 27

А ось 5 перших екземплярів із цього завдання із знайдених 16+27=43 кубоїдів:

D,244600187525,28161660483,76892843820,230485711456,81887658117,232199789635,√59036172616105401832336
E,244610350921,44854093440,121522347000,√43054653258982105514641,129535981560,212288819671,240462749879
D,244618979525,27628647696,93953798820,224160180803,97931907396,225856434115,√59075102970342683117209
E,244622018485,50414287248,108442705140,√45538511270870843862121,119588547348,219271775725,239370699061
D,244632158185,17208292297,144068966496,196959133800,√21051992431004560054225,197709447703,244026161496

Читати це так:
Перша літера P, E чи D — це тип кубоїда (див. вище).
Далі — просторова діагональ (G).
Наступні 3 числа — ребра (A, B, C).
Заключні 3 числа — лицьові діагоналі (D, E, F).

Уся робота легко розподіляється.
Щоб час виконання завдань був приблизно однаковий і не залежав від діапазону, я нарізав завдання за формулою, що залежить від початку діапазону:

y=1568625.2703x2+−183907100.8152x+5410490309.2381

, що виведена емпіричним шляхом.

Мета яку я ставлю:
1) на данний момент доведено, що якщо ідеальний кубоїд існує, його непарне ребро має бути більше за 3*10^12. Я збираюсь або знайти ідеальний кубоїд (що будо б ідеально), або хоча б 1000 разів перевершити (у певному сенсі) результат і сформулювати твердження, що якщо ідеальний кубоїд існує, його просторова діагональ має бути більшою, скажімо, за 10^15. Умовно кажучи, у ручному режимі зараз ми удвох із A1ex.UA досить скромними зусиллями за декілька днів виконали пошук до 250 млрд, тобто це 2.5*10^11. До 3*10^12 нам — "2 пісні, 3 приспіви" )
2) Знайти і опублікувати всі майже ідеальні кубоїди двох видів (Edge та Diagonal) із просторовою діагоналлю аж до 10^15.

Коли вдасться започаткувати BOINC-проект у мене є певні ідеї, як можна було б заохотити до участі: роздавати бейджі за кількість знайдених майже ідеальних кубоїдів двох видів. Тому, хто раніше приєднається, у того більше шансів "записати" майже ідеальні кубоїди на свій рахунок )
Але до того, як запустити BOINC-проект у мене є бажання провести тестування, код рев'ю та оптимізацію.
Тому я звертаюсь до усіх бажаючих:
а) програмістів (знання С та/або asm вітаються).
б) математиків (знання із теорії чисел).
а) просто бажаючих підтримати та допомогти започаткувати український математичний проект.

Усі бажаючі приєднуйтесь до групи у Telegram: https://t.me/joinchat/AAAAAA7IlqNyJx4jRSdEBA
А там я відповім на всі питання.

[Death]

а без телеги? написал в скайп тебе

[x3mEn]

28'000 tasks done
26'339 core*hours = 1097 core*days = 3 core*years spent
17'578'355'938'459 = ~ 2^44 achieved
—-------------------------------------------------
0 Perfect cuboids found
64'187 Edge cuboids found
111'237 Face cuboids found
0 Complex Perfect cuboids found
268'326 Imaginary cuboids found
1'331'250 Twilight cuboids found

Telegram: https://t.me/joinchat/AAAAAA7IlqNyJx4jRSdEBA