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]

A1ex01,
не знаю, яким місцем ти відчув, але саме сьогодні, після майже 5 місячної перерви, я поновив роботу над задачею. Почав і вже майже закінчив писати безгуйового клієнта, заточеного на фактично виконання нарізаних гіпотетичним сервером завдань на перевірку діагоналей від і до.
Як доведу до ладу, можу викласти сорці разом із ехешником, якщо комусь цікаво буде. Я б не відмовився, якби хтось допоміг перекласти з Паскаля на С.
Без гуя в програмі залишилася чиста математика: динамічні масиви, 64 бітні цілі, сортування, перестановки і таке інше.
Адмін yoyo@home обіцяв розглянути можливість розгортання підпроекту на німецькому сервері, за умови, якщо прога буде написана на С. В них є досвід перекладання не-БОЇНК проектів на рейки БОЇНК.

[A1ex01]

если 2 диагонали нечетные

dab^2=a^2+b^2
dbc^2=b^2+c^2
dac^2=a^2+c^2
пусть dab и dbc нечет, тогда если a^2 нечет то и с^2 нечет, а b^2-чет

D^2=a^2+b^2+c^2
и в сумме D^2 -чет

правда, если a^2 чет то и с^2 чет, а b^2-нечет
D^2=a^2+b^2+c^2
и в сумме D^2 -нечет

значит D и чет и нечет

[x3mEn]

пусть dab и dbc нечет, тогда если a^2 нечет то и с^2 нечет, а b^2-чет

D^2=a^2+b^2+c^2
и в сумме D^2 -чет

ця ситуація неможлива, оскільки серед a, b, c тільки одне ребро може бути непарним.
Джерело: http://en.wikipedia.org/wiki/Perfect_cuboid
Some interesting facts about a primitive perfect cuboid:

• 2 of the edges {a,b,c} must be even and 1 edge must be odd
• 1 edge must be divisible by 4 and 1 edge must be divisible by 16
• 1 edge must be divisible by 3 and 1 edge must be divisible by 9
• 1 edge must be divisible by 5
• 1 edge must be divisible by 7
• 1 edge must be divisible by 11
• 1 edge must be divisible by 19.

[x3mEn]

Закінчив писати консольну версію програми.
Хтось може помогти перекласти програму на С/С++?

[Rilian]

x3mEn, https://distributed.org.ua/forum/index.php?...522&#entry77522

ты в новостях

[x3mEn]

x3mEn, https://distributed.org.ua/forum/index.php?...522&#entry77522

ты в новостях

Я в курсі. Тільки толку мало. Мало народу там для конструктивної розмови.
Є там один, Роберт якийсь. Вважає себе пупом землі. Критикує мене мовляв надто багато завдань получається.
За його оцінкою десь 10^17 діагоналей. От сиджу тепер, перевіряю...

Може в когось є вже написана в Паскалі/Дельфі функція/процедура для факторизації?
А то мене щось ламає писати.

function MaxDivisor(n: int64; var Has4kp3: boolean): int64;
var
divnum: int64;
begin
Has4kp3:=false;
Result:=3;
while (Result<=sqrt(n)) and not Has4kp3 do begin
divnum:=trunc(n/Result);
if n=divnum*Result then begin
Has4kp3:=Result mod 4=3;
n:=divnum;
end
else inc(Result, 2);
end;
Result:=n;
end;

інколи працює довго. Це взагалі найтупіший метод.
Мені, власне, навіть не факторизація потрібна, а перевірка, чи є серед дивізорів прості числа 4k+3, а якщо нема, тоді найбільший простий 4k+1 множник.

Це так, чисто для статистики, порахувати, скільки серед випадково обраних чисел 4k+1, мають у розкладі на прості множники лише 4k+1.
А потім зробити апроксимацію на весь діапазон від 1 до 2^63

[Death]

1. Гербиц известній математик.
2. он программировал клиента для єйлера на йойо.

http://www.euler413.narod.ru/

Современый поиск

На момент начала открытия проекта (24 октября 2007г), самая быстрейшая программа из всех созданных для поиска чисел опровергающих гипотезу Эйлера, методом тотального поиска, является программа Euler413.exe Роберта Гербица (Венгрия).
http://robert.gerbicz.googlepages.com
К примеру вместо 30 лет работы простого перебора, она выполняет поиск до 1000000 за 4 сек. На данном этапе мы имеем реальную возможность в течении не слишком большого времени проверить все числа до 2 000 000 000. Простой перебор в этом случае говорит, что нам бы потребовалось порядка 1020 лет работы (многократно больше возраста вселенной). Дальше пока невозможно из за ограничения размеров чисел, с которыми работает программа. Переход на 64 битную версию и более быстрые процессоры в будущем дадут новый импульс в этой задаче.

[x3mEn]

Ну, я ж кажу, вважає себе пупом землі.
Він мені одразу не сподобався.
Надто зухвало себе поводить, нібито його точка зору сама правильна, а інших бути не може. Я йому сторінки 2 доводив, що він робить висновки, коли ще не вкурив всю тему.

[Death]

http://mathoverflow.net/questions/7330/whi...gth/10875#10875

Доказательство в одно предложение, что все простые числа вида 4k+1 есть сумма двух квадратов (Цагир), опубликованное в настоящем математическом журнале.

Дана ссылка на JSTOR, каковой требует 12 баксов за статью. В комментах благодетельный юзер Zavosh нарушает копирайт и цитирует релевантный кусок статьи, бесплатно.

[x3mEn]

http://mathoverflow.net/questions/7330/whi...gth/10875#10875

Доказательство в одно предложение, что все простые числа вида 4k+1 есть сумма двух квадратов (Цагир), опубликованное в настоящем математическом журнале.

Дана ссылка на JSTOR, каковой требует 12 баксов за статью. В комментах благодетельный юзер Zavosh нарушает копирайт и цитирует релевантный кусок статьи, бесплатно.

$S = {(x,y,z) in mathbb{N}^3 : x^2 +4yz = p }
$ defined by: [ (x,y,z)
mapsto left {
begin{array}{cc} (x+2z,z,y-x-z) &
text{if } x < y-z ( 2y-x, y, y-x+z ) &
text{if } y-z < x <2y ( x-2y, x-y+z, y ) &
text{if } x > 2y
end{array}
right.
]

Що це за мова така? MathCad, чи що?
І як це по-людськи зрозуміти?

Власне, мене доведення теореми не цікавить, я і так знаю, що прості 4k+1 розкладаються на суму квадратів, до того ж один єдиним чином.
Мене цікавить, чи з цієї абракадабри можна висмикнути якийсь ефективний алгоритм пошуку цього самого розкладу.
Бо, нажаль, на даний момент якогось іншого методу пошуку розкладу N=x^2+y^2, окрім як перебір x від 1 до sqrt(N/2) я не придумав.

[Death]

Власне, мене доведення теореми не цікавить, я і так знаю

*facepalm*

$S = {(x,y,z) in mathbb{N}^3 : x^2 +4yz = p }

это TeX - разметка

[Death]

хром рендерит круто

[Death]

8. Разложение простых чисел р= 1 mod 4 на сумму двух квадратов [179]

http://1.iesod.z8.ru/nehudlit/self0001/hasse.rar

[x3mEn]

Death,
ти сам хоч читав, що процитував?
Якщо число p = 4611686018427387817, а це просте число, можеш перевірити, і до того ж виду 4k+1
А ну зконструюй мені xΞ((p-1)/2)! mod p
Або на прикладі розкажи, як отримати розклад на суму квадратів.

[Death]

напиши профессору шо он идиот, ок?