Поиск простых чисел

[anwior]

Jnrty в сообщении #662672 писал(а):

Хм... Я попробовал, у меня работает, если
1) щёлкнуть левой кнопкой мыши по знаку "=" (иногда приходится щёлкнуть несколько раз, прежде чем сработает, но эта проблема, скорее всего, гнездится у меня);
2) поместить курсор в окошко ввода вычисляемого выражения и нажать клавишу "Enter".

А слово "sqrt" в самом начале выражения, часом, не стёрли? Это слово - команда извлечь квадратный корень.

По п. 1). возможно и у меня та же проблема.
По п. 2) - зайду и ёще раз проделаю-- в первой пробе наж. кнопку, а не "Enter".
Спасибо Вам.

[ananova]

(Оффтоп)

Пожалуй дело в браузере. Если в IE не работает. Попробуйте в Chrome или Safari

[anwior]

Разобрался с прогой. Предел вводимых знаков -- 195. И это удручает. Тем не мение, придумал методику играючись извлекать кв. корни даже из 600 и более знаков безошибочно и с точным значением разряда единиц в результате. Затея с он-лайн прогой нужна была для сравнения возможностей. О деталях находки раскажу как подготовлю связный текст, иначе получится "винигрет" с упущениями. Я так не привык.
За советы всем спасибо.

[anwior]

Где-то за 18-20 часов извлёк кв. корень из 617 значного числа. Пока вдаваться в подробности не желаю, а делаю пробу предъявить скриншот полной записи в Excel. Так как здесь нет навигации вставка рисунка, даю прямую ссылку: http://laperino.narod2.ru/kkv617z.jpg

[Droog_Andrey]

Каким образом всё это относится к теме?

[anwior]

Droog_Andrey в сообщении #665887 писал(а):

Каким образом всё это относится к теме?

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

[nnosipov]

(Оффтоп)

anwior в сообщении #665621 писал(а):

Где-то за 18-20 часов извлёк кв. корень из 617 значного числа.

Если речь идёт о том, чтобы найти целую часть квадратного корня, то это делается гораздо быстрее (меньше секунды).

[anwior]

nnosipov в сообщении #666110 писал(а):

Если речь идёт о том, чтобы найти целую часть квадратного корня, то это делается гораздо быстрее (меньше секунды).

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

[nnosipov]

(Оффтоп)

anwior в сообщении #666184 писал(а):

жажду ссылку на таковую прогу.

FloorSqrt:=proc(N)
local x,x_next;
x:=iquo(N+1,2); x_next:=iquo(x^2+N,2*x);
while x>x_next do
x:=x_next; x_next:=iquo(x^2+N,2*x)
end do;
return x 
end proc:

Это на Maple. Здесь iquo(m,n) --- стандартная процедура, которая находит неполное частное от деления m на n.

[tolstopuz]

да какая там секунда...

http://code.activestate.com/recipes/577 ... -function/

def isqrt(x):
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

print(isqrt(int('1234567890'*30) ** 2))

[anwior]

Пока не схлопотал выговор, плавно перебрался в новую тему: Улучшение способа излечения кв. корней из больших чисел!
Пожалуйста отвечайте мне в ней.

[yk2ru]

Возвращаясь к сообщению post570788.html?#p570788 про аналог теста Люка-Лемера для чисел вида $Q_n=\frac{3^n-1}{2}$.
Почти тот же алгоритм, но по числам Люка: $S_1 = 4$ и $S_{k+1} = S_k(S_k^2+3)$.
Остаток по модулю $Q_n$ будет давать на последнем шаге значение $S_n \equiv \frac{3+5(-1)^{\frac{n-1}{2}}}{2}\pmod{Q_n}.$.
Я так понимаю, что всевдопростые на числах Люка встречаются заметно реже. Кто знает, где посмотреть первые значения таких всевдопростых?

[maxal]

yk2ru в сообщении #677979 писал(а):

Возвращаясь к сообщению post570788.html?#p570788 про аналог теста Люка-Лемера для чисел вида $Q_n=\frac{3^n-1}{2}$.
Почти тот же алгоритм, но по числам Люка: $S_1 = 4$ и $S_{k+1} = S_k(S_k^2+3)$.
Остаток по модулю $Q_n$ будет давать на последнем шаге значение $S_n \equiv \frac{3+5(-1)^{\frac{n-1}{2}}}{2}\pmod{Q_n}.$.
Я так понимаю, что всевдопростые на числах Люка встречаются заметно реже. Кто знает, где посмотреть первые значения таких всевдопростых?

Повторю свою ремарку:
Псевдопростые здесь могут не существовать в силу разреженности $Q_n$ (то есть, эмпирическая вероятность существования псевдопростого числа мала). И тут становится особенно не важно, чем тестировать - например, тест Ферма по основанию 2 для чисел вида $Q_n$ с нечётным $n>1$ тоже, похоже, псевдопростых не дает.

[Руст]

Найдено 48-ое простое число Мерсена $2^{57885161}-1$.

[Jnrty]

О, $17425170$ цифр!

А насчёт того, что оно именно сорок восьмое, как будто бы неизвестно. Если не ошибаюсь, сплошной проверки всех простых показателей до $57885161$ не было. Или я отстал от жизни, и лакуны закрыты?