Пятница...

← →
Думкин © (2006-07-28 13:41) [0]

Раскидавшись с проектами разными, чуток остался не у дел. И занялся ерундой. По пути ерунды всплыла задачка. задачка из ерунды всплыла естественным образом. поэтому не исключаю, что кто-то с подобной и сталкивался и уже и решение имеет. У меня решения пока нет. Итак:

Есть отображение нечетных чисел на все.
3 –1, 5 –2, 7 – 3
и т.д.
То есть, если вычеркнем из натурального ряда 1 и все четные, то получим ряд нечетных начиная с 3, и каждое число из этого ряда имеет номер. Итак, построено биективное отображение N<->I(/1) которое можно выразить так:
n(i) = i div 2
i(n) = 2*n +1

А если из полученного ряда вычеркнуть все числа кратные 3 то, как выразить отображения между значениями и порядковыми номерами нового ряда?

n(i) = i – [(i div 2 + i div 3 – i div 6 ] –1
i(n) = ?

А если еще и кратные 5, а потом и 7 …..

← →
For kaif (2006-07-28 14:25) [1]

Похоже на поиск формулы N-го простого числа. Насколько я знаю, такой формулы не существует.

← →
Думкин © (2006-07-28 14:33) [2]

> For kaif (28.07.06 14:25) [1]

Похоже. Но пока не свел к этому.
Но ноги растут именно из этой области.
Ветка тут была и пытались меня напугать числами уровня Longint.
Ушел уже дальше и намного - стало забавно. Ищу оптимизации.
Статьи пока не читаю - тыкаюсь как теля по интересу.

← →
For kaif (2006-07-28 14:39) [3]

Думкин © (28.07.06 14:33) [2]

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

← →
Думкин © (2006-07-28 14:42) [4]

> For kaif (28.07.06 14:39) [3]

Я знаю. Но пока не надоело. Да и всего-то пару часов убил. Но первый миллиард простых в течении приемлего времени - вуаля. Хотя конечно не то... :)
До статей возможно и не дойдет по серьезному - надоест раньше. Материал будет использован иначе. Не для пинания Крэев и прочих монстров. :)

← →
For kaif (2006-07-28 14:46) [5]

Думкин © (28.07.06 14:42) [4]

Миллиард? Впечатляет. Удачи.

← →
TJulia © (2006-07-28 14:48) [6]

> А если из полученного ряда вычеркнуть все числа кратные
> 3 то, как выразить отображения между значениями и порядковыми
> номерами нового ряда?

n(i)=(i-1) div 3
i(n)=2*n+1+2*( (n+1) div 2 )

Вроде так получается.

← →
Думкин © (2006-07-28 15:11) [7]

> TJulia © (28.07.06 14:48) [6]

Да, для 3 формула вышла проще. Я ее походя из другиз видимо соображений выводил.
А с 5 если бы? :)

← →
default © (2006-07-28 15:22) [8]

"n(i) = i – [(i div 2 + i div 3 – i div 6 ] –1" -->n(i) = i div 3

← →
Внук © (2006-07-28 15:22) [9]

>>Думкин © (28.07.06 15:11) [7]
Миллиард простых? Или все простые среди первого миллиарда?

← →
default © (2006-07-28 15:23) [10]

опоздал малость, после обеда попробую из той же идея для 5 попробовать

← →
TJulia © (2006-07-28 15:27) [11]

> А с 5 если бы? :)

Уже после того, как делящиеся на 3 выкинули?

← →
Думкин © (2006-07-28 15:32) [12]

> Внук © (28.07.06 15:22) [9]

Все простые до 200 лимонов - за 59 секунд вывалились.
Все простые первого миллиарда - пока на обед ходил посчитались. Без оптимизации особой. Сейчас прикинул как оптимизировать. И пока получается, что за тоже время и первый миллиард выйдет.
То что посчитал - приукрасил конечно, но как - уже видно. Проблемы только с одним - оптимизация работы с памятью. Пока так.

> TJulia © (28.07.06 15:27) [11]

Ага.

← →
default © (2006-07-28 15:32) [13]

и соответсвенно
i(n)=i div 3
n(i)=3*i + (i mod 2) + 1

← →
Думкин © (2006-07-28 15:34) [14]

Было обсуждение похожего на алголисте в свое время. Но не вникал.

← →
default © (2006-07-28 15:40) [15]

n(i)=i div 3
i(n)=3*n + (n mod 2) + 1
:)
если для 5 алгоритм будет, для 7 надеюсь не понадобится?

← →
Думкин © (2006-07-28 15:42) [16]

> default © (28.07.06 15:40) [15]

Если бы вообще для всех простых.... :)
Чем больше - тем лучше.
Повторяю - я пока не решил. Если на выходных вырву кусок времени - тоже подумаю.
До понедельника. :)

← →
TJulia © (2006-07-28 15:44) [17]

> если для 5 алгоритм будет, для 7 надеюсь не понадобится?

Понадобится и не только для 7.:)

← →
default © (2006-07-28 16:29) [18]

Думкин © (28.07.06 15:42) [16]
для 5 могу вот что сказать(дальше уже тоже время нет думать):
7 - первое число, не кратное 2,3,5
далее имеем такой период: 4,2,4,2,4,6,2,6
по периоду считаем все остальные числа
2: 7+4=11
3: 11+2=13
4: 13+4=17;
5: 17+2=19;
6: 19+4=23
7: 23+6=29;
8: 29+2=31;
9: 31+6=37;
и далее сначала периода и тд
может это поможет для вывода формулы

← →
default © (2006-07-29 01:34) [19]

исходя из [18](периода и величины первого числа) можно написать соответствующие ф-ции для делителей 2,3,5
для удобства - на Delphi
const X: Array[0..8] of Byte = (0, 4, 6, 10, 12, 16, 22, 24, 30); Y: Array[0..30] of Byte = (0, 0, 0, 0, 1, 0, 2, 0, 0, 0, 3, 0, 4, 0, 0, 0, 5, 0, 0, 0, 0, 0, 6, 0, 7, 0, 0, 0, 0, 0, 8); var Form1: TForm1; implementation {$R *.dfm} function i(n: Cardinal): Cardinal; begin Result := 7 + 30 * ((n-1) div 8) + X[(n-1) mod 8] end; function n(i: Cardinal): Cardinal; begin Result := 1 + 8 * ((i-7) div 30) + Y[(i-7) mod 30] end;

можно аналогично записать для делителей 2,3,5,7 и тд
только вот периоды будет приходиться искать всё труднее
можно попробовать автоматизировать поиск периодов и формирования искомых пар-функций...

← →
default © (2006-07-29 01:55) [20]

правые границы массивов X и Y можно урезать до 7 и 29 соответственно(не изменяя значения оставшихся элементов)
издержки времени суток:)

← →
Думкин © (2006-07-29 05:54) [21]

Да, сложность вычислений растет. Если бы было просто, то такую функцию, достаточно бы было найти для простого числа в районе 1700000 и легким движением руки получить 1 миллиард простых чисел.
Первый миллиард ищется - но иначе. У меня по крайней мере.
Дома места на диске мало - а вот на работе на обеде запущу счет. 8 гиг на диске всяко найдется. :) Время пока не оценивал, но вроде должно быть приемлемым.

← →
Думкин © (2006-07-29 05:57) [22]

170 000 - на нолик наврал. :)

← →
мимопроходивший (2006-07-29 09:18) [23]

"рекуррентная формула простого числа":
http://ega-math.narod.ru/Liv/Zagier.htm

← →
palva © (2006-07-29 22:49) [24]

Метод колеса - так наверно будет по-русски.
http://primes.utm.edu/glossary/page.php?sort=WheelFactorization

← →
Думкин © (2006-07-30 05:57) [25]

> мимопроходивший (29.07.06 09:18) [23]
> palva © (29.07.06 22:49) [24]

Предложенная мной задачка попутная, и к поиску в итоге оказавшаяся не вполне пригодной.

> Думкин ©

Не могли бы вы привести используемый вами алгоритм поиска?
Ковыряюсь сейчас с Компонентным Паскалем, хочу для обучения языку написать что-нить, не связанное с GUI(если смогу. конечно;-)).
Заранее спасибо.

> "рекуррентная формула простого числа":
> http://ega-math.narod.ru/Liv/Zagier.htm

Классный рассказ :) Спасибо за ссылку!

> Насколько я помню, сейчас поиск простых чисел осуществляется
> сетью суперкомпьютеров и они уже ищут в районе миллионнозначных
> чисел

А что будет, если найдут? Счастье?

> Тульский © (31.07.06 09:28) [29]
> А что будет, если найдут? Счастье?

А что, бывает же совершенные числа. Совершенство, значит, можно найти. Для кого-то это почти счастье, а для некоторых несчастье.

Хотя, да. Наверняка премию кто-то получит.

> Тульский © (31.07.06 09:28) [29]

Ну например, - это интересно. Каждому свое. Но почему-то и знаки числа Пи ищут. А вроде бы - зачем? И даже Эйлер в своей бессметртной - "Исчисление бес...." приводит более 100 знаков числа е - зачем?

Вот и я побаловавашись могу сказать

p(1 000 000 000) = 22 801 763 489

Поправочка

p(1 000 000 000) = 22 777 909 421

22 801 763 489 = p(1 000 999 999)

> 22 801 763 489 = p(1 000 999 999)

Сколько времени вычисялось?

> atruhin © (02.08.06 18:45) [34]

Не оптимизировал. Если оптимизировать, то раза в 4 минимум можно ускорить.
А так. Пень 2,8. Нагрузку на память не осуществлял. Сбрасывал сразу в файлы. Простые до миллиарда - 248 секунд.
Потом посчитал 1300 млн. простых. Заняло около 2 часов.

Но можно весьма ускорить.

Последнее расчитанное такое:
p(1 300 094 810) = 30000999997

Если же не все считать - лишь бы простое, то подход другой нужен и они есть. С тем что есть у меня ис пользуя простейший подход влегкую можно найти простое в районе 900 060 000 819 994 000 009.

Пятница... Найти похожие ветки