Сколько HD по 1Tb нужно для хранения 10^30 простых чисел?

[ananova]

Занимательный вопрос.

Сколько жестких дисков по 1 Терабайту может занимать архив простых чисел до $2^{100}$, что приблизительно равно $10^{30}$?

100 байт займет одно простое число. Т.е. на одном жестком диске может поместиться, грубо говоря, без индексных таблиц для поиска, 1000000000 байт - итого - 10000000 простых чисел, т.е. приблизительно $10^7$.

Правильно я понимаю, что праймориал первых $10^7$ чисел займёт, для хранения своей записи, грубо говоря, 1 Тб ? Что-то в это не верится.... совсем.

На $10^7$ простых, если обычных чисел $10^8$, то количество жестких дисков будет приблизительно $10^{22}$?

Считаю эти расчёты очень грубыми. Почему мне это интересно? Хочу представить сколько потребуется ресурсов компьютера, чтобы побить рекорды поиска наибольших простых чисел, основанные на праймориале. Есть идейка как побить рекорд. И под это хочу грант просить - надо оценить сколько чего потребуется... на побитие рекорда. Сразу предупреждаю, что это не серьезное намерение - просто гипотетическое - на уровне фантазий, которыми бы мне хотелось заняться. Как говорят на Украине - "дурень думкой богатеет"

Вот тут
http://primes.utm.edu/largest.html#largest - The Ten Largest Known Factorial/Primorial Primes
собраны разные рекорды...

Лучший результат был получен очень давно - в 2001 году..
1 392113#+1 169966 p16 2001 Primorial

Буду признателен, если Вы расскажете, как расшифровать 169966? Я так понимаю, что Primorial из 169966 цифр. Сколько чисел в этом праймориале примерно? Вроде как 392113 - это наибольшее простое число в произведении первых простых чисел?

Я так понимаю, что поиск следующего простого числа за праймориалом не составляет большого труда мыслительного - главное ресурсы. Где это число хранится? ( Или хранятся все простые числа до 392113 включительно.) Как получить доступ?

[Someone]

ananova в сообщении #298429 писал(а):

Лучший результат был получен очень давно - в 2001 году..
1 392113#+1 169966 p16 2001 Primorial

Буду признателен, если Вы расскажете, как расшифровать 169966?

Количество цифр в десятичной записи данного числа.

[fer1800]

Мне кажется хранить простые числа никто не разрешит.

На сколько мне известно простые числа используются при шифровании. Количество цифр в числе раньше было толи 200, толи 400. Если будут известны все простые числа указанной длины, то сломать код, наверное будет просто.

[maxal]

ananova в сообщении #298429 писал(а):

Буду признателен, если Вы расскажете, как расшифровать 169966? Я так понимаю, что Primorial из 169966 цифр. Сколько чисел в этом праймориале примерно? Вроде как 392113 - это наибольшее простое число в произведении первых простых чисел?

На оба вопроса - ответ да.

ananova в сообщении #298429 писал(а):

Я так понимаю, что поиск следующего простого числа за праймориалом не составляет большого труда

Неправильное понимание. Все сильно зависит от размера числа.

[venco]

ananova в сообщении #298429 писал(а):

Сколько жестких дисков по 1 Терабайту может занимать архив простых чисел до $2^{100}$, что приблизительно равно $10^{30}$?

$10^{12}/\left(13\cdot {2^{100}\over 100\cdot\ln 2}\right) = 2.4\cdot 10^{17}$ дисков.

ananova в сообщении #298429 писал(а):

100 байт займет одно простое число.

100 бит, или 13 байт.

ananova в сообщении #298429 писал(а):

Т.е. на одном жестком диске может поместиться, грубо говоря, без индексных таблиц для поиска, 1000000000 байт - итого - 10000000 простых чисел, т.е. приблизительно $10^7$.

1 терабайт - $10^{12}$ байт а не $10^9$. Для хранения всех $2^{100}$ простых чисел понадобится $2.4\cdot 10^{17}$ таких дисков.

ananova в сообщении #298429 писал(а):

Правильно я понимаю, что праймориал первых $10^7$ чисел займёт, для хранения своей записи, грубо говоря, 1 Тб ? Что-то в это не верится.... совсем.

Правильно не верится. Всего 14 мегабайт.

ananova в сообщении #298429 писал(а):

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

Проблема не в памяти, а во времени, необходимом для проверки на простоту.

(Оффтоп)

И почему люди с такими математическими способностями берутся ставить рекорды по простым числам?
Наверно, потому, что они не могут понять сложность проблемы...

[Руст]

Цитата:

$$\frac{2^{100+3}}{10^{12+2}\ln 2} = 2.4\cdot 10^{17}$$

дисков.

ananova в сообщении #298429 писал(а):

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

Проблема не в памяти, а во времени, необходимом для проверки на простоту.

Как вы представляете, доживет ли он до того времени, если закажет столько дисков (допустим он имеет средств) и заводы будут выпускать миллиард таких дисков в год (сейчас меньше)? Потребуется 100 миллионов лет.

[venco]

Там он дальше снизил требования до произведения $10^7$ простых чисел.
В любом случае, проблема с временем встаёт гораздо раньше, чем с памятью.

[ananova]

fer1800 в сообщении #298449 писал(а):

Мне кажется хранить простые числа никто не разрешит.

Это предусмотрено на всякий случай... Даже если у Вас будут все простые числа в какой-либо супер-памяти - чтобы разложить произведение двух простых чисел на множители (например, на 2 простых числа), потребуется супер-вычислитель. Хотя есть разговоры о квантовых компьютерах, но ... мне в это слабо пока верится. Можно увеличить значения чисел к тому времени как они появятся. В общем в Википедии на эту тему достаточно информации.

-- Ср мар 17, 2010 08:38:17 --

Благодарю всех за помощь в оценке. Особая благодарность venco за существенные уточнения. Один вопрос остался для меня пока непонятым. Есть ли архив простых чисел до 392113 включительно. Вероятно как-то можно получить праймориал или значение праймориала - т.е. уже известное число, полученное рекордсменом? Впрочем компьютеру искать все простые числа до 392113 не составит большого труда... Далее потребуются библиотеки с кодом, чтобы перемножать такой размерности числа. Ну и наиболее сложная часть - проверка на простоту.

Можно попробовать довести праймориал до такого (большого числа +1), которое будет не сложно проверить "доморощенным" алгоритмом...

[ananova]

Учитывая, что число Мерсенна-38 не так сильно больше, чем рекордсмен на праймориале, то с нынешним уровнем вычислительной техники можно было бы довести значение рекорда до значения числа Мерсенна -38. А если процесс отладить то и получить более весомый результат. На мой взгляд это более перспективное направление чем гоняться за самым большим числом Мерсенна. Т.к. непрерывную последовательность простых получить по-моему проще. Т.к. самое большое число в этой последовательности по современным меркам совсем небольшое - всего навсего 392113. Что, разве сложно получить следующее простое число и получить новый праймориал? Всё что надо - это довести значение праймориала до 13 миллионов цифр и рекорд у нас в руках

Какой праймориал по силам получить форумчанам?

[Xaositect]

ananova в сообщении #298524 писал(а):

Т.к. непрерывную последовательность простых получить по-моему проще. Т.к. самое большое число в этой последовательности по современным меркам совсем небольшое - всего навсего 392113.

Вы что-то путаете: http://www.prime-numbers.org

[ananova]

Xaositect в сообщении #298573 писал(а):

Вы что-то путаете

Благодарю за комментарий. Действительно, решил раз самый большой праймориал получен до числа 392113, ... далее мысли увели к неправильным выводам...

Цель на самом деле простая и Ваша ссылка подтверждает, что она имеет смысл на осуществление - Не очень сложно вычислить праймориал, который по своим размерам поспорит со рекордом известных простых чисел. Если это так, то есть способ побить рекорд максимального простого числа Мерсенна.

[Xaositect]

Вычислить его, может быть, и несложно.
Но вот проверить его (ну то есть не его, а следующее за ним число) на простоту...

[ananova]

Xaositect в сообщении #298589 писал(а):

Но вот проверить его (ну то есть не его, а следующее за ним число) на простоту...

Уточняю - я знаю способ как это сделать весьма просто... Он работает на любом праймориале, а не на каких-то особенных. Поэтому мне нужен единомышленник (единомышленники), которые могут вычислить праймориал больше чем 12 млн цифр.. Как тут посчитал venco - это несколько десятков мегабайт всего навсего.

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

Если кто-то может, то я попробую (мы попробуем) получить грантик на эту работу.

[ananova]

Переоценил возможности способа проверки простоты - после тестирования на больших праймориалах+1 - эффективность уступает алгоритму проверки числа Мерсенна. В общем-то, это не удивительно. Тем не менее задача не снимается с повестки дня, т.к. рекорд от 2001 года пора бы уже улучшить кому-то.

[venco]

ananova в сообщении #298610 писал(а):

Уточняю - я знаю способ как это сделать весьма просто... Он работает на любом праймориале, а не на каких-то особенных.

Уверяю Вас, вы не знаете такого способа.

ananova в сообщении #298610 писал(а):

Поэтому мне нужен единомышленник (единомышленники), которые могут вычислить праймориал больше чем 12 млн цифр.. Как тут посчитал venco - это несколько десятков мегабайт всего навсего.

Это довольно тривиальная задача. Произведение первых $10^7$ простых чисел (вплоть до $179424673$) считается за время меньше минуты.
В бинарном виде 32 мегабайта (выше я немного ошибся).
В десятичном виде $77919922$ цифр:
$3380445109538286518178...30065441278013328441066732954520433703644022980910$