Українська команда з розподілених обчислень

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

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

Треба було тільки поклацати по "ієрогліфам", тепер і Maxthon (Webkit) рендерить.

x3 как прогресс?

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-ми розмірностей не ціла тільки лицьова діагональ
-- ну і власне примітивні ідеальні кубоїди (якщо такі будуть)

уже ж до 10^10 пощитаны - насколько ты больше диапазон берёшь?

ну хотя да. http://www.wolframalpha.com/input/?i=2%5E63-10%5E10 = 9223372026854775808


есть топик на йойо? там реальнее всего запустить.

Топік є. Толку нема.
адміністратор йойо казав, що може розглянути мою пропозицію тільки якщо:
а) програма буде написана на С (на якій саме, я не уточнював)
б) програма буде консольна
в) програма матиме чекпоїнти
г) програма матиме прогрес
ґ) програма не генеруватиме багато трафіку
д) проект матиме прогрес
е) ну і бажано, щоб проект мав кінець



Ну, Andrii Muliar на одній своїй машині порахував вже до 2^36. А log(2^36) = 10.837
А якщо програму ще оптимізувати та хоча б 1000 чоловік буде рахувати, можна цю планку підняти до 2^44, я думаю. А може і вище.

ну явно не на шарпе ))
си надо чтобы скомпилить под линух и мак

у тебя консольная? чекпоинты есть?
прогресс есть? трафик я думаю там небольшой будет или как?

не совсем понятно какой прогресс у проекта?

ну конец у него есть - пощитать до стопиццот миллиардов.

как говорится до бесконечности и не дальше.

Что можно получить еще из этого проекта кроме доказать/опровергнуть существования идеального кубоида?

Давай так. Я одразу розумів, що треба буде консольну, тому у мене на Дельфі прога консольна.
У Андрія поки на C#.
Чекпоїнти можна зробити.
Прогрес є.
Трафік взагалі мізерний: пару байт на вхід, пару кілобайт на вихід.

ну, наприклад, ось такий: http://www.rechenkraft.net/yoyo/y_status_hat.php
Це теж можна організувати.

Не зовсім. Є обмеження цілочисельних обрахунків.
Межа, яку я хотів би досягти - 2^63-1.
По-перше і до цієї межі дійти буде дуже важко.
А по-друге, якщо і припустити, що дійдемо, треба буде переписувати клієнта, оскільки поточні розрахунки вилітають в простір 256-бітної цілочисельної точності.
На цей момент все складається так, що для перевірки 64-бітних чисел потрібно виходити в простір 128-бітної цілочисельної точності.

ну учитывая что мы движемся по числовой прямой прогресс очевиден - видно докуда пощитали, прально?

а есть компилятор дельфи или шарпа под линупс?

Правильно. Буде
Мінімальне n в прогресі
Максимальне n в прогресі
Все, що посередині - це робоча область.

Кожне завдання - це діапазон [m;n]
В цьому діапазоні (n-m)/4 чисел, які треба перевірити.
Із цих (n-m)/4 чисел якась частина відсіюється на стадії факторизації.
Скільки саме - заздалегідь невідомо, але я міряв в районі 2^63, там залишається десь відсотків 10 чисел-кандидатів від початкової кількості.
В принципі складність перевірки цих чисел не залежить від їх розміру.
Тобто, що перевіряти 1000 чисел в районі 1 млн, що в районі 2^63, різниці майже ніякої.
Але густина цих чисел у різних районах різна.
Тому нарізати завдання ([m;n]) треба буде в якійсь залежності від розміру m

Це все для того, щоб самі завдання між собою були приблизно однакової складності (мали приблизно однаковий час виконання).
Це, між іншим, теж одна з умов проекту - очікуваний час виконання завдань.
Якщо в проекті різні завдання дуже відрізняються за часом - це не є гут.
Наприклад, в Harmonious Trees @ yoyo, де чим далі прогрес підпроекту, тим складніші і, відповідно, довші завдання.
А в NumberFields ще гірше - одночасно можуть прийти завдання, одне на 30 секунд, інше на 1 день - це взагалі опа якась.

а предварительная сеялка будет? как в прайме.

x3mEn, может начинать поднимать сайт проекта? Beta версию, пока идут работы по написанию клиента..

ні, в цьому немає сенсу.
Кожен клієнт сам відсіюватиме.
Факторизація для чисел < 2^63 - це відносно швидкий процес.
Тим більше, що Andrii Muliar придумав дуже цікавий метод, як одним циклом від 3 до sqrt(n) провести факторизацію цілого діапазону чисел.

Досить багато часу зараз займає розклад простих чисел на суми квадратів.
В принципі ось цей джава-аплет вміє це робити дуже швидко:
http://www.alpertron.com.ar/FSQUARES.HTM
Наприклад число n=1844674407370954349 аплет розкладає менше секунди:
n = a^2 + b^2
a = 1297540285
b = 401327318

Time elapsed: 0d 0h 0m 0s

Ось тут навіть описано, як він це робить:
http://www.alpertron.com.ar/4SQUARES.HTM
Я вже 100500 разів читав цей опис, але збагнути не можу.
Якщо хтось допоможе - буду вдячний.
Ось тут навіть є сорс джава скрипту:
http://www.alpertron.com.ar/fsquares.java

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

А до боїнк-проекту ще дуже далеко.
Окрім клієнта треба ще кучу серверних приблуд написати:
генератор завдань, фідер, валідатор і т.і.

x3mEn, как продвигается написание проекта?