|
|
|
| Trianon предложил интересную задачу (источником вдохновения послужило новостное сообщение, опубликованное sim5).
Команда математиков из Калифорнийского университета в Лос-Анджелесе сумела объединить мощности 75 компьютеров и открыла новое большое простое число, которое на сегодняшний день признано самым большим. За это открытие калифорнийские ученые получили премию фонда Electronic Frontier в $100 тыс.
Исследуемые числа относятся к так называемым числам Мересенна. Они имеют вид 2^n - 1. Проверка простоты числа обычно является достаточно сложной и трудоемкой задачей, однако для чисел Мерсенна существует удобный критерий проверки - в бинарном представлении они состоят из одних единиц, т.е. число в бинарном представлении выглядит как 111 ... 11111. Найденное простое число содержит 43112609 бинарных единиц.
1) Выведите самое большое простое число в десятичном представлении в файл (отдельно подсчитайте время формирования десятичного представления и время записи полученного результата в файл). Для решения задачи допускается использовать ядро PHP и его стандартные расширения.
2) Отдельным скриптом подсчитайте количество десятичных цифр в самом большом простом числе.
Здачи будут оцениваться по точности, скорости выполнения и читабельности кода (правильности его оформления). В качестве приза победитель получит любую из книг сотрудников SoftTime, по собственному выбору. Результаты конкурса будут подведены 12 октября 2008 года.
Разместить свой ответ можно в специальной форме. В день подведения итогов ответы будут автоматически опубликованы. Количество вариантов не ограничено, однако, опубликован будет лишь последний вариант.
PS В этой теме публиковать ответ не следует, она предназначена только для обсуждение организационных вопросов. | |
|
|
|
|
|
|
|
для: cheops
(02.10.2008 в 20:37)
| | Хех.. =) Файл с тем числом, которое нашли математики вроде 13 мегабайт весил.. | |
|
|
|
|
|
|
|
для: krollik
(03.10.2008 в 08:52)
| | Нет столько места на диске :)))?
PS На самом деле должно получится 12 Мб с хвостиком. | |
|
|
|
|
|
|
|
для: cheops
(02.10.2008 в 20:37)
| | Мм.. Числа Мересенна не все являются простыми, если я не ошибаюсь (проверка для n=4 => 2^4-1 = 15 - а это не простое число).. Может лучше поставить задачу для нахождения самого большого числа Мересенна.. | |
|
|
|
|
|
|
|
для: krollik
(03.10.2008 в 08:57)
| | > Числа Мересенна не все являются простыми
Да, но никто не утверждал обратного.
> Может лучше поставить задачу для нахождения самого большого числа Мересенна
Докажите, что оно существует? :))) | |
|
|
|
|
|
|
|
для: krollik
(03.10.2008 в 08:57)
| | >Может лучше поставить задачу для нахождения самого
>большого числа Мересенна..
Только скорее всего придется отказаться PHP и обзавестись кластером побольше... Собственно, задача проверки насколько я понимаю и сводилось к тому, чтобы поделить возможное простое число на все числа поменьше и доказать, что нет ни одного делителя - длительная трудоемкая работа за которую дают 100 000 $. Здесь задача попроще - самое большое из доказанных на сегодня простых числе - необходимо просто вывести в десятичном формате и подсчитать количество символов в него входящих. | |
|
|
|
|
|
|
|
для: cheops
(03.10.2008 в 11:38)
| | print 43112609%8;
выводит 1
Калифорнийцы обманывают что у них простое число , у них похоже там в начале нулей присутствует :)
Запись в файл должна обязательно не содержать нули ? | |
|
|
|
|
|
|
|
для: exp
(04.10.2008 в 23:46)
| | Запись должна быть десятичной. А не двоичной. :) 316...511
Длина файла должна совпадать с ответом второго скрипта. | |
|
|
|
|
|
|
|
для: cheops
(02.10.2008 в 20:37)
| | То ли я деградирую, то ли просто до конца не вникнул в задачу...
Как бы САМУ ЗАДАЧУ я понял, но вот КАК её решить у меня не протсо нету идей, даже предположений... то есть если бы мне дали тест по химии для выпускника какого-нибудь факультета с химической направленостью, бы наверное больше понял...
А тут полное ничто :(
ЗЫ. но до 12 я должен справиться и разобраться!!! | |
|
|
|
|
автор: DEM... (06.10.2008 в 02:00) |
|
|
для: cheops
(02.10.2008 в 20:37)
| | Скажите, то есть нам надо вывести просто очень большое простое число и чем оно будет больше, тем лучше? | |
|
|
|
|
автор: DEM... (06.10.2008 в 02:02) |
|
|
для: DEM...
(06.10.2008 в 02:00)
| | Тогда еще вопрос:
оно уже есть какое-то определённое или его нужно задавать в скрипте\форме ? | |
|
|
|
|
автор: DEM... (06.10.2008 в 02:05) |
|
|
для: DEM...
(06.10.2008 в 02:02)
| | Извините за уже третий пост вподряд...
"В десятичном виде" - имеется ввиду обычное число? Ну то есть 131 или 3 или 1292313? | |
|
|
|
|
|
|
|
для: DEM...
(06.10.2008 в 02:00)
| | Странно как это Вы настроены решать задачу, не прочитав условие...
Условие, насколько я вижу, не менялось - надо запись в файл число "2 в степени 43112609 минус 1". В десятичном виде. Это означает, что нужно записать число в десятичной системе счисления, т.е. с использованием цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
> Ну то есть 131 или 3 или 1292313?
Да, это обычные числа в 5-ричной , 6-ричной или 12-ричной системах счисления соотвественно. :))
| |
|
|
|
|
|
|
|
для: BinLaden
(06.10.2008 в 02:15)
| | нда... то есть я совсем видимо деградировал (((
Даже как-то стыдно стало за эти вопросы ((( | |
|
|
|
|
|
|
|
для: DEM
(06.10.2008 в 02:34)
| | IMHO, самоуничижение не принесет Вам пользы | |
|
|
|
|
|
|
|
для: BinLaden
(06.10.2008 в 08:58)
| | Да нет, просто я как-то перечитал первый пост и всё равно не понял некотрые вопросы...
Ладно, будем ждать следующей задачи, надеюсь я тогда смогу собраться и решить её... | |
|
|
|
|
|
|
|
для: DEM
(06.10.2008 в 13:30)
| | В общем-то, Вы, наверное, для себя хотите задачу решить, а не для нас. Поэтому и в Ваших интересах все недопонимания утранить, нет?
А время еще есть. Странно Вы себя ведете...:) | |
|
|
|
|
автор: DEM... (06.10.2008 в 16:30) |
|
|
для: BinLaden
(06.10.2008 в 15:18)
| | Ну в принципе да, давно уже хотел найти такую задачку что бы поломать глову над её решением :)
Но тут же ещ и ТАКОЙ приз... как тут не нерничать ))) | |
|
|
|
|
|
|
|
для: cheops
(02.10.2008 в 20:37)
| | Правильно ли я понял, что книга будет содержать автографы всех трёх её авторов с расшифровкой их фамилий? Или потом придётся бедному победителю ломать голову над вопросом кому какой росчерк принадлежит?
+++++++++++++++++++++++++
Можно ли надеяться, что над автографами будет располагаться ещё и, пусть краткое, но рукописное, разъяснение обстоятельств по которым эта книга должна принадлежать её новому обладателю? Как минимум 10 слов. | |
|
|
|
|
|
|
|
для: Eugene77
(06.10.2008 в 18:54)
| | Конечно, и рассшифруем и напишем за что вручена.
PS Только могут возникнуть технические сложности, если вы захотите получить, например, первое издание "Самоучитель PHP 5" или скажем "PHP 5. Практика создания Web-сайтов" - книги уже не издаются и пополнить запасы не откуда (кроме того, для них существуют вторые издания). | |
|
|
|
|
|
|
|
для: cheops
(06.10.2008 в 19:35)
| | Ну скажите нафига первое, если есть второе? ) | |
|
|
|
|
|
|
|
для: cheops
(06.10.2008 в 19:35)
| | >PS Только могут возникнуть технические сложности, если вы захотите получить, например, первое издание "Самоучитель PHP 5" или скажем "PHP 5. Практика создания Web-сайтов"
Да бросте, кто их ещё не прочитал, шансов на выигрыш не имеют! | |
|
|
|
|
|
|
|
для: cheops
(02.10.2008 в 20:37)
| | Всё же хотелось бы удостовериться окончательно:
Нужнов озвести двуйку (2) в очень большую степень(43112609)?
Просто возможно я ошибаюсь, но используя даже мои не самые большие знания математики это можно решить довольно легко (сравнительно)... хотя вероятно я всё же не до конца понял суть задачи... тогда будет обидно :) | |
|
|
|
|
|
|
|
для: DEM
(07.10.2008 в 10:42)
| | да, это так!
вот и решайте, книгу получите )))) | |
|
|
|
|
|
|
|
для: ddhvvn
(07.10.2008 в 11:03)
| | Ну... на это я даже не надеюсь, разев что никто больше не будет принимать участие :)
Но постараюсь... просто интересно, правильно я думаю или нет... | |
|
|
|
|
|
|
|
для: DEM
(07.10.2008 в 11:04)
| | >Ну... на это я даже не надеюсь, разев что никто больше не будет принимать участие :)
Зря не надеетесь. Хеопс решил реально простую задачу задать. А поскольку основное время уйдёт на преобразование этого числа в десятичное представление, то по скорости будет сравнивать нечего. Это преобразование не ускорить. Больше 20% разницы в скорости между программами претендентов не будет. Хеопс будет игральные кости бросать чтобы определить кому книгу вручить.
>Но постараюсь... просто интересно, правильно я думаю или нет...
Вы легко себя проверите. Попробуйте разделить, то, что получили на десяток простых чисел, что вам известны и получите почти полную гарантию, что число у вас правильно опредеолено.
Как это всё-таки здорово! - можно любую книгу!
У него даже такие есть, которых я ни разу у нас в магазине не видел!
Просто мечта! | |
|
|
|
|
|
|
|
для: Eugene77
(07.10.2008 в 13:55)
| | ПРОГРАММИРОВАНИЕ. СТУПЕНИ УСПЕШНОЙ КАРЬЕРЫ?
Сколько у нас не спрашивал, нигде нету ((( А когда заказывал сестре книгу подарок на озоне не додумался купить((( | |
|
|
|
|
|
|
|
для: DEM
(07.10.2008 в 14:00)
| | Только сейчас понял что уже 12.10.08 по Московскому :) Как-то всё думал времени много, можно взяться завтра... Хех... жду с нетерпением ваши решения :) | |
|
|
|
|
|
|
|
для: DEM
(12.10.2008 в 00:15)
| | cheops, пойдите ему навстречу -- перенесите дату подведения итогов | |
|
|
|
|
|
|
|
для: BinLaden
(12.10.2008 в 00:48)
| | ненене! ответы в студию!
я вот тоже хотел поучаствовать, но с математикой чет туговато (надеюсь она тут нужна))) )...
было несколько вариантов, но все упирались в 1 проблему....
так что жду не дождусь, привильного решения | |
|
|
|
|
|
|
|
для: DEM
(12.10.2008 в 00:15)
| | Задача. в том виде, как она сейчас сформулирована, решается в три - четыре строки.
У Вас даже сейчас вагон времени. | |
|
|
|
|
|
|
|
для: Trianon
(12.10.2008 в 11:49)
| | Кстати вышеупомянутая компания вручившая 100 тыс у.е. ученым, объявила что вручит 150 или 200 тыс у.е. тому кто найдет еще большее простое число | |
|
|
|
|
|
|
|
для: Arfey
(12.10.2008 в 22:48)
| | А я-то здесь при чем? :))) | |
|
|
|
|
|
|
|
для: Trianon
(12.10.2008 в 22:58)
| | Trianon, мы будем болеть за Вас всем форумом. :) | |
|
|
|
|
|
|
|
для: Drago
(13.10.2008 в 00:01)
| | Зря :)))
Сам я еще не настолько болен, чтобы претендовать на. | |
|
|
|