2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 00:01 
Аватара пользователя
Nacuott в сообщении #659966 писал(а):
...произведение половины чисел менее всего отличающееся от полученного числа, после извлечения корня.

Плохая идея, во-первых, потому что 20 чисел из 40 можно выбрать довольно многими способами, а во-вторых, потому что искомый набор может не быть (и не будет) состоящим ровно из 20 чисел.

-- Вт, 2012-12-18, 01:04 --

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

-- Вт, 2012-12-18, 01:05 --

venco в сообщении #659911 писал(а):
3) заранее посчитать и отсортировать все возможные наборы из некоторого количества последних множителей (чтобы потом использовать бинарный поиск).
Ключевая идея вот. А первые две я вообще не использовал.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 00:08 
wcl.AleX в сообщении #659956 писал(а):
Квадратов между чем и чем? Покажите, пожалуйста, на примере , без двойки, с числами 3,5,7,11,13
Числа должны быть 105 и 143
$123^2$- самый маленький квадрат, превосходящий $a=3\cdot5\cdot7\cdot11\cdot13$.
$123^2-a$ не является полным квадратом. Но уже $124^2-a=19^2$.
Отсюда $a=(124-19)(124+19)$.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 00:09 
Ну, не половины, но до тех пор, пока произведение ближе всего не приблизится к извлеченному квадрату.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 00:17 
Аватара пользователя
А это перебирать порядка $2^{40}$, что немного чересчур.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 00:54 
Уважаемый Val, ваш способ эффективен только до первых 20 простых чисел, а мне нужно от 40
проблема с двойкой решается элементарно, но к сожалению это не решает задачу в целом, так как всё равно нельзя использовать более 40 чисел


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

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 09:25 
Аватара пользователя
А Вам тогда какая часть работы останется?

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 09:31 
VAL в сообщении #659974 писал(а):
$123^2$- самый маленький квадрат, превосходящий $a=3\cdot5\cdot7\cdot11\cdot13$.
$123^2-a$ не является полным квадратом. Но уже $124^2-a=19^2$.
Отсюда $a=(124-19)(124+19)$.

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

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 10:10 
Аватара пользователя
Пруф или фуфло.

-- Вт, 2012-12-18, 11:11 --

(Много раскрывать не надо, дайте две следующие цифры с конца)

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 10:52 
ИСН в сообщении #660080 писал(а):
Пруф или фуфло.

Любое натуральное число $N=ab$ можно разложить на разность квадратов:
$N=\left(\dfrac{a+b}{2}\right)^2-\left(\dfrac{a-b}{2}\right)^2$*
Из этого выражения видно, что $\left(\dfrac{a+b}{2}\right)^2>N$, соответственно: $\left(\dfrac{a+b}{2}\right)>\sqrt {N}$.
Чем меньше выражение $\left(\dfrac{a-b}{2}\right)^2$, тем менее $\left(\dfrac{a+b}{2}\right)$ превосходит $\sqrt {N}$.
Таким образом, факторизируя число по методу Ферма, первыми обнаружатся множители $a,b$ наименее отличающиеся друг от друга.
*Т.к. примориалы имеют четность степени $2^1$, то следует оперировать квадратами чисел, имеющих $5$ после запятой.



ИСН в сообщении #660080 писал(а):
(Много раскрывать не надо, дайте две следующие цифры с конца)

Программированием, к сожалению не владею, поэтому "пасс".

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 10:56 
Батороев в сообщении #660070 писал(а):
VAL в сообщении #659974 писал(а):
$123^2$- самый маленький квадрат, превосходящий $a=3\cdot5\cdot7\cdot11\cdot13$.
$123^2-a$ не является полным квадратом. Но уже $124^2-a=19^2$.
Отсюда $a=(124-19)(124+19)$.

Это фактически повторяет "факторизацию числа по Ферма" (в данном случае число - примориал).
Разумеется.
Цитата:
Метод Ферма позволяет в первую очередь находить натуральные множители числа, наименее отличающиеся друг от друга
Как раз то, что нам нужно.
Цитата:
(независимо от числа их простых множителей и наличия среди них простого 2).
Нет, двойка в нечетной степени мешает. Но эта беда легко исправляется.
Цитата:
По-видимому, лучшего способа решить поставленную задачу (независимо от величины примориала), чем этот, не найти.
Угу.
Осталось выяснить, почему ИСН, давно нашел ответ. А я, своим "лучшим способом" час мурыжил комп и снял задачу. :shock:
(Зато программку писал одну минуту :-) )
Конечно, можно существенно усовершенствовать метод Ферма, используя систему попарно взаимно простых модулей, дабы не пытаться миллиард раз проверять, является ли число квадратом. Но от самого миллиарда итераций все равно не уйти.
Так что, лучшим с практической точки зрения является комбинированный метод с отсечением бесперспективных ветвей и т.д.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 10:58 
Аватара пользователя
Это всё и так очевидно. Я просил пруфов к
Батороев в сообщении #660070 писал(а):
По-видимому, лучшего способа решить поставленную задачу (независимо от величины примориала), чем этот, не найти.
Нет пруфов? Так и запишем.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 11:19 
Мдя! А вроде бы казалось, что по методу Ферма комп должен быстро найти - все-таки, аж 40 множителей! Ладно, след. раз креститься буду! :-(

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 11:50 
Батороев в сообщении #660099 писал(а):
Мдя! А вроде бы казалось, что по методу Ферма комп должен быстро найти - все-таки, аж 40 множителей! Ладно, след. раз креститься буду! :-(
Тут еще от везения многое зависит.
Для уже упомянутого случая 35-ти простых, по методу Ферма мой комп тратит около сотой доли секунды. Просты искомые произведения очень близки и находятся всего за 6383 итерации.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 11:52 
VAL в сообщении #660095 писал(а):
Так что, лучшим с практической точки зрения является комбинированный метод с отсечением бесперспективных ветвей и т.д.

Не понадобятся никакие отсечения. Venco же уже все написал. Делим массив пополам. Для каждого подмножества первой части (которых чуть больше миллиона) подбираем за 20 сравнений добавку из второй части. Все выполняется за секунду.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 11:54 
Аватара пользователя
Вот-вот. Даже бинарный поиск не нужен: мы тупо идём по левому массиву снизу, а по правому - сверху.

 
 
 [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group