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

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


snow catcher
*********

Група: Moderators
Повідомлень: 2 208
З нами з: 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
6 Сторінки V « < 4 5 6  
Reply to this topicStart new topic
Відповідей(75 - 88)
x3mEn
Dec 11 2011, 20:01
Пост #76


snow catcher
*********

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



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


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

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Death
Dec 11 2011, 22:04
Пост #77


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

Група: Moderators
Повідомлень: 6 428
З нами з: 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
Dec 11 2011, 23:03
Пост #78


snow catcher
*********

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



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


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

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
A1ex01
May 12 2012, 23:24
Пост #79


round catcher)
********

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



(x3mEn @ Dec 5 2011, 00:19) *

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

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

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

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


--------------------
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
rpisarev
Dec 24 2012, 15:17
Пост #80


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

Група: Trusted Members
Повідомлень: 366
З нами з: 10-December 11
Користувач №: 2 868
Стать: bot



(x3mEn @ Dec 1 2011, 14:05) *

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, за день-два могу переписать на Си/Си++ (без длинной арифметики). Пока начал разбираться с общем случаем представления (хотя для решения задачи перфекткуба, кажется, это и не надо)
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Rilian
Dec 24 2012, 17:22
Пост #81


interstellar
**********

Група: Team member
Повідомлень: 17 333
З нами з: 22-February 06
З: Ванкувер
Користувач №: 184
Стать: НеСкажу
Free-DC_CPID
Парк машин:
ноут и кусок сервера



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


--------------------
(Show/Hide)

Миссия проекта Help Fight Childhood Cancer (Помоги Победить Детский Рак) - подобрать белки, блокирующие некоторые виды рака. Подключайтесь!
IPB Image
IPB Image

IPB Image

IPB Image
IPB Image

общая статистика: BOINCstats * FreeDC команда: BOINC команда Ukraine

IPB Image
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Володимир
Dec 24 2012, 17:45
Пост #82


кранчер з фермою
*******

Група: Trusted Members
Повідомлень: 660
З нами з: 29-June 11
З: Хмельницький 2016 (Khmelnytsky)
Користувач №: 1 830
Стать: Чол
Free-DC_CPID
Парк машин:
i5-4200M @ 2.50GHz



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

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

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

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

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

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


--------------------
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Oct 22 2013, 06:17
Пост #83


snow catcher
*********

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



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


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

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
A1ex01
Oct 23 2013, 08:23
Пост #84


round catcher)
********

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



(x3mEn @ Mar 25 2011, 21:09) *

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 ребра вычислять через [ко]синус...


--------------------
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
Oct 23 2013, 10:06
Пост #85


snow catcher
*********

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



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


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

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
A1ex01
Mar 23 2014, 21:07
Пост #86


round catcher)
********

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



предыдущая мысль ошибочна, пришел к новой)
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...)


--------------------
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
A1ex01
Aug 5 2016, 14:50
Пост #87


round catcher)
********

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



ping x3mEn help.gif
шо нового?

если 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)


--------------------
User is offlineProfile CardPM
Go to the top of the page
+Quote Post
x3mEn
May 31 2017, 20:29
Пост #88


snow catcher
*********

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



Новини такі:

Після десь місяця різноманітних експериментів у мене є готова програма із пошуку 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
А там я відповім на всі питання.


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

(Show/Hide)

User is offlineProfile CardPM
Go to the top of the page
+Quote Post
Death
Jun 6 2017, 21:18
Пост #89


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

Група: Moderators
Повідомлень: 6 428
З нами з: 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

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

 



- Lo-Fi Версія Поточний час: 27th July 2017 - 20:48

Rambler's Top100 Рейтинг@Mail.ru
Invision Power Board v1.3.3 © 1996 IPS, Inc.