Форум: Форум PHPФорум ApacheФорум Регулярные ВыраженияФорум MySQLHTML+CSS+JavaScriptФорум FlashРазное
Новые темы: 0000000
Самоучитель MySQL 5. Авторы: Кузнецов М.В., Симдянов И.В. Программирование. Ступени успешной карьеры. Авторы: Кузнецов М.В., Симдянов И.В. PHP на примерах (2 издание). Авторы: Кузнецов М.В., Симдянов И.В. MySQL на примерах. Авторы: Кузнецов М.В., Симдянов И.В. PHP Puzzles. Авторы: Кузнецов М.В., Симдянов И.В.
ВСЕ НАШИ КНИГИ
Консультационный центр SoftTime

Выбрать другой форум

 

Здравствуйте, Посетитель!

вид форума:
Линейный форум Структурный форум

тема: Задача N 23. Вывод самого большого простого числа
 
 автор: cheops   (02.10.2008 в 20:37)   письмо автору
 
 

Trianon предложил интересную задачу (источником вдохновения послужило новостное сообщение, опубликованное sim5).

Команда математиков из Калифорнийского университета в Лос-Анджелесе сумела объединить мощности 75 компьютеров и открыла новое большое простое число, которое на сегодняшний день признано самым большим. За это открытие калифорнийские ученые получили премию фонда Electronic Frontier в $100 тыс.

Исследуемые числа относятся к так называемым числам Мересенна. Они имеют вид 2^n - 1. Проверка простоты числа обычно является достаточно сложной и трудоемкой задачей, однако для чисел Мерсенна существует удобный критерий проверки - в бинарном представлении они состоят из одних единиц, т.е. число в бинарном представлении выглядит как 111 ... 11111. Найденное простое число содержит 43112609 бинарных единиц.

1) Выведите самое большое простое число в десятичном представлении в файл (отдельно подсчитайте время формирования десятичного представления и время записи полученного результата в файл). Для решения задачи допускается использовать ядро PHP и его стандартные расширения.
2) Отдельным скриптом подсчитайте количество десятичных цифр в самом большом простом числе.

Здачи будут оцениваться по точности, скорости выполнения и читабельности кода (правильности его оформления). В качестве приза победитель получит любую из книг сотрудников SoftTime, по собственному выбору. Результаты конкурса будут подведены 12 октября 2008 года.

Разместить свой ответ можно в специальной форме. В день подведения итогов ответы будут автоматически опубликованы. Количество вариантов не ограничено, однако, опубликован будет лишь последний вариант.

PS В этой теме публиковать ответ не следует, она предназначена только для обсуждение организационных вопросов.

   
 
 автор: krollik   (03.10.2008 в 08:52)   письмо автору
 
   для: cheops   (02.10.2008 в 20:37)
 

Хех.. =) Файл с тем числом, которое нашли математики вроде 13 мегабайт весил..

   
 
 автор: cheops   (03.10.2008 в 11:42)   письмо автору
 
   для: krollik   (03.10.2008 в 08:52)
 

Нет столько места на диске :)))?

PS На самом деле должно получится 12 Мб с хвостиком.

   
 
 автор: krollik   (03.10.2008 в 08:57)   письмо автору
 
   для: cheops   (02.10.2008 в 20:37)
 

Мм.. Числа Мересенна не все являются простыми, если я не ошибаюсь (проверка для n=4 => 2^4-1 = 15 - а это не простое число).. Может лучше поставить задачу для нахождения самого большого числа Мересенна..

   
 
 автор: BinLaden   (03.10.2008 в 11:09)   письмо автору
 
   для: krollik   (03.10.2008 в 08:57)
 

> Числа Мересенна не все являются простыми

Да, но никто не утверждал обратного.

> Может лучше поставить задачу для нахождения самого большого числа Мересенна

Докажите, что оно существует? :)))

   
 
 автор: cheops   (03.10.2008 в 11:38)   письмо автору
 
   для: krollik   (03.10.2008 в 08:57)
 

>Может лучше поставить задачу для нахождения самого
>большого числа Мересенна..
Только скорее всего придется отказаться PHP и обзавестись кластером побольше... Собственно, задача проверки насколько я понимаю и сводилось к тому, чтобы поделить возможное простое число на все числа поменьше и доказать, что нет ни одного делителя - длительная трудоемкая работа за которую дают 100 000 $. Здесь задача попроще - самое большое из доказанных на сегодня простых числе - необходимо просто вывести в десятичном формате и подсчитать количество символов в него входящих.

   
 
 автор: exp   (04.10.2008 в 23:46)   письмо автору
 
   для: cheops   (03.10.2008 в 11:38)
 

print 43112609%8;

выводит 1

Калифорнийцы обманывают что у них простое число , у них похоже там в начале нулей присутствует :)
Запись в файл должна обязательно не содержать нули ?

   
 
 автор: Trianon   (05.10.2008 в 00:58)   письмо автору
 
   для: exp   (04.10.2008 в 23:46)
 

Запись должна быть десятичной. А не двоичной. :) 316...511
Длина файла должна совпадать с ответом второго скрипта.

   
 
 автор: DEM   (05.10.2008 в 01:29)   письмо автору
 
   для: 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?

   
 
 автор: BinLaden   (06.10.2008 в 02:15)   письмо автору
 
   для: 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-ричной системах счисления соотвественно. :))

   
 
 автор: DEM   (06.10.2008 в 02:34)   письмо автору
 
   для: BinLaden   (06.10.2008 в 02:15)
 

нда... то есть я совсем видимо деградировал (((
Даже как-то стыдно стало за эти вопросы (((

   
 
 автор: BinLaden   (06.10.2008 в 08:58)   письмо автору
 
   для: DEM   (06.10.2008 в 02:34)
 

IMHO, самоуничижение не принесет Вам пользы

   
 
 автор: DEM   (06.10.2008 в 13:30)   письмо автору
 
   для: BinLaden   (06.10.2008 в 08:58)
 

Да нет, просто я как-то перечитал первый пост и всё равно не понял некотрые вопросы...

Ладно, будем ждать следующей задачи, надеюсь я тогда смогу собраться и решить её...

   
 
 автор: BinLaden   (06.10.2008 в 15:18)   письмо автору
 
   для: DEM   (06.10.2008 в 13:30)
 

В общем-то, Вы, наверное, для себя хотите задачу решить, а не для нас. Поэтому и в Ваших интересах все недопонимания утранить, нет?

А время еще есть. Странно Вы себя ведете...:)

   
 
 автор: DEM...   (06.10.2008 в 16:30)
 
   для: BinLaden   (06.10.2008 в 15:18)
 

Ну в принципе да, давно уже хотел найти такую задачку что бы поломать глову над её решением :)

Но тут же ещ и ТАКОЙ приз... как тут не нерничать )))

   
 
 автор: Eugene77   (06.10.2008 в 18:54)   письмо автору
 
   для: cheops   (02.10.2008 в 20:37)
 

Правильно ли я понял, что книга будет содержать автографы всех трёх её авторов с расшифровкой их фамилий? Или потом придётся бедному победителю ломать голову над вопросом кому какой росчерк принадлежит?
+++++++++++++++++++++++++
Можно ли надеяться, что над автографами будет располагаться ещё и, пусть краткое, но рукописное, разъяснение обстоятельств по которым эта книга должна принадлежать её новому обладателю? Как минимум 10 слов.

   
 
 автор: cheops   (06.10.2008 в 19:35)   письмо автору
 
   для: Eugene77   (06.10.2008 в 18:54)
 

Конечно, и рассшифруем и напишем за что вручена.

PS Только могут возникнуть технические сложности, если вы захотите получить, например, первое издание "Самоучитель PHP 5" или скажем "PHP 5. Практика создания Web-сайтов" - книги уже не издаются и пополнить запасы не откуда (кроме того, для них существуют вторые издания).

   
 
 автор: ddhvvn   (06.10.2008 в 21:09)   письмо автору
 
   для: cheops   (06.10.2008 в 19:35)
 

Ну скажите нафига первое, если есть второе? )

   
 
 автор: Eugene77   (07.10.2008 в 13:59)   письмо автору
 
   для: cheops   (06.10.2008 в 19:35)
 

>PS Только могут возникнуть технические сложности, если вы захотите получить, например, первое издание "Самоучитель PHP 5" или скажем "PHP 5. Практика создания Web-сайтов"

Да бросте, кто их ещё не прочитал, шансов на выигрыш не имеют!

   
 
 автор: DEM   (07.10.2008 в 10:42)   письмо автору
 
   для: cheops   (02.10.2008 в 20:37)
 

Всё же хотелось бы удостовериться окончательно:
Нужнов озвести двуйку (2) в очень большую степень(43112609)?
Просто возможно я ошибаюсь, но используя даже мои не самые большие знания математики это можно решить довольно легко (сравнительно)... хотя вероятно я всё же не до конца понял суть задачи... тогда будет обидно :)

   
 
 автор: ddhvvn   (07.10.2008 в 11:03)   письмо автору
 
   для: DEM   (07.10.2008 в 10:42)
 

да, это так!

вот и решайте, книгу получите ))))

   
 
 автор: DEM   (07.10.2008 в 11:04)   письмо автору
 
   для: ddhvvn   (07.10.2008 в 11:03)
 

Ну... на это я даже не надеюсь, разев что никто больше не будет принимать участие :)
Но постараюсь... просто интересно, правильно я думаю или нет...

   
 
 автор: Eugene77   (07.10.2008 в 13:55)   письмо автору
 
   для: DEM   (07.10.2008 в 11:04)
 

>Ну... на это я даже не надеюсь, разев что никто больше не будет принимать участие :)

Зря не надеетесь. Хеопс решил реально простую задачу задать. А поскольку основное время уйдёт на преобразование этого числа в десятичное представление, то по скорости будет сравнивать нечего. Это преобразование не ускорить. Больше 20% разницы в скорости между программами претендентов не будет. Хеопс будет игральные кости бросать чтобы определить кому книгу вручить.

>Но постараюсь... просто интересно, правильно я думаю или нет...

Вы легко себя проверите. Попробуйте разделить, то, что получили на десяток простых чисел, что вам известны и получите почти полную гарантию, что число у вас правильно опредеолено.

Как это всё-таки здорово! - можно любую книгу!
У него даже такие есть, которых я ни разу у нас в магазине не видел!
Просто мечта!

   
 
 автор: DEM   (07.10.2008 в 14:00)   письмо автору
 
   для: Eugene77   (07.10.2008 в 13:55)
 

ПРОГРАММИРОВАНИЕ. СТУПЕНИ УСПЕШНОЙ КАРЬЕРЫ?
Сколько у нас не спрашивал, нигде нету ((( А когда заказывал сестре книгу подарок на озоне не додумался купить(((

   
 
 автор: DEM   (12.10.2008 в 00:15)   письмо автору
 
   для: DEM   (07.10.2008 в 14:00)
 

Только сейчас понял что уже 12.10.08 по Московскому :) Как-то всё думал времени много, можно взяться завтра... Хех... жду с нетерпением ваши решения :)

   
 
 автор: BinLaden   (12.10.2008 в 00:48)   письмо автору
 
   для: DEM   (12.10.2008 в 00:15)
 

cheops, пойдите ему навстречу -- перенесите дату подведения итогов

   
 
 автор: ddhvvn   (12.10.2008 в 11:13)   письмо автору
 
   для: BinLaden   (12.10.2008 в 00:48)
 

ненене! ответы в студию!

я вот тоже хотел поучаствовать, но с математикой чет туговато (надеюсь она тут нужна))) )...
было несколько вариантов, но все упирались в 1 проблему....

так что жду не дождусь, привильного решения

   
 
 автор: Trianon   (12.10.2008 в 11:49)   письмо автору
 
   для: DEM   (12.10.2008 в 00:15)
 

Задача. в том виде, как она сейчас сформулирована, решается в три - четыре строки.
У Вас даже сейчас вагон времени.

   
 
 автор: Arfey   (12.10.2008 в 22:48)   письмо автору
 
   для: Trianon   (12.10.2008 в 11:49)
 

Кстати вышеупомянутая компания вручившая 100 тыс у.е. ученым, объявила что вручит 150 или 200 тыс у.е. тому кто найдет еще большее простое число

   
 
 автор: Trianon   (12.10.2008 в 22:58)   письмо автору
 
   для: Arfey   (12.10.2008 в 22:48)
 

А я-то здесь при чем? :)))

   
 
 автор: Drago   (13.10.2008 в 00:01)   письмо автору
 
   для: Trianon   (12.10.2008 в 22:58)
 

Trianon, мы будем болеть за Вас всем форумом. :)

   
 
 автор: Trianon   (13.10.2008 в 00:25)   письмо автору
 
   для: Drago   (13.10.2008 в 00:01)
 

Зря :)))
Сам я еще не настолько болен, чтобы претендовать на.

   
Rambler's Top100
вверх

Rambler's Top100 Яндекс.Метрика Яндекс цитирования