2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 74, 75, 76, 77, 78, 79, 80 ... 215  След.
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 14:07 
Заслуженный участник


27/06/08
4062
Волгоград
EUgeneUS в сообщении #1557569 писал(а):
А Вы факторизуете в PARI/GP или на https://www.alpertron.com.ar/ECM.HTM ?
Пробовал и там, и там. Я же писал.
Но PARI уже отказался считать. Сутки помолотил, а затем написал, что число слишком большое, и порекомендовал снять задачу.
А 70 часов - это на Alpertron'е

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 14:21 
Аватара пользователя


11/12/16
13850
уездный город Н
VAL
Понятно. Тогда сложно делать какие-то прогнозы.
Что касается PARI/GP, то там надо поднимать размер стека, иначе не посчитает.
Только не помню - в этом случае было достаточно размера стека. как .gp от Дмитрия, или потребовалось ещё больше.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 14:58 


05/06/22
293
Well I have the $n+0$ factorization running again, I'll have to hope it completes before the machine crashes again. I may try to add some checkpoint logging in the factorization code, so that I can restart an incomplete factorization without going right back to the beginning.

EUgeneUS, It does make me wonder whether numdiv() did a full factorization, or used some different analysis to decide that $pq$ had to be a semiprime.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 14:59 
Заслуженный участник


20/08/14
11766
Россия, Москва
У меня 130e6 стека не хватило, вылетел через 16ч счёта, для числа 923...492. Так что лучше сразу давать ему гиг или два и не жадничать.

-- 16.06.2022, 15:04 --

Huz
Hugo, in the documentation for PARI it is written that all functions of working with divisors are internally implemented via factorint(), i.e. full factorization. This is the first. Secondly, PARI can be forced to save the found large primes and then check them first at any attempt to factorize a large number, i.e. calling numdiv()+factor() or factor()+numdiv() in a row will not double the factorization time, the second function will be executed instantly - i.e. any of them performs full factorization.

-- 16.06.2022, 15:09 --

Кстати именно на этом трюке основан мой вариант частичной факторизации, когда полной факторизации не проводится если устанавливается что делителей точно неподходящее количество: вызывается factor() с ограничением (на величину простых или времени выполнения) и даже если не завершилась успешно, то всё большое найденное (простые больше 16млн) сохранила и при последующем вызове фактически продолжает работу, разлагая лишь последнее составное число, а не всё с начала. Трюк описан в документации к PARI, искать по имена параметра factor_add_primes.
К сожалению простые сохраняются не любые, а только входящие в разложение, потому не получается продолжить разложение составного числа если ни один из его делителей не был найден.
Как и не получается заставить factor() продолжить перебор эллиптических кривых (или других перебираемых параметров в других методах) не с начала (что кстати кажется возможно на том сайте). Так что трюк полезен только когда в процессе был найден хотя бы один новый делитель, иначе большое составное число так и остаётся составным с неизвестным разложением.
Опять таки к сожалению я не нашёл как заставить factor() не продолжать факторизацию по нахождению любого делителя, а вернуть его нам чтобы уже мы решали стоит ли разлагать дальше или плюнуть (например если делителей уже больше требуемых), потому приходится ограничивать просто по времени, что при следующем вызове повторяет часть уже выполненной работы. :-(

-- 16.06.2022, 15:21 --

VAL в сообщении #1557543 писал(а):
Код:
print(n," Yess!!!);break))))))};
В print надо бы закрывать кавычки.

-- 16.06.2022, 15:45 --

EUgeneUS
Так что в программе где Вы проверяете числа можно в начале добавить default(factor_add_primes,1);, а потом после вызова numdiv(n) спокойно вызвать ещё и factor(n) (на то же число или хотя бы его делители), которая выполнится мгновенно и выдаст полную факторизацию. Или в обратном порядке, без разницы.
Только если проверяете разные числа без выхода из PARI, то стоит перед проверкой нового числа добавить и removeprimes; для очистки накопленной таблицы больших простых из разложений предыдущих чисел, ведь для новых чисел они не подойдут.
Вот например кусочек моей программы для проверки хорошо разложимых цепочек:
Код:
x=18652995711772;
default(parisize,130*10^6); \\Может быть мало и лучше пожертвовать гиг или два
default(factor_add_primes,1); \\Будем сохранять простые из разложений больших чисел
print(x); removeprimes; \\Старые простые удалим
{for(d=1,9,
   f=factor(x+d-1); fd=numdiv(x+d-1); \\Вторая выполнится мгновенно
   print("+",d-1,":",fd,"\t",f);
)}

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 15:54 
Заслуженный участник


27/06/08
4062
Волгоград
Dmitriy40 в сообщении #1557584 писал(а):
В print надо бы закрывать кавычки.
Спасибо!
Заработало!!
Подлость заключается в том... Ну в общем, это как искать заначенную купюру в "Войне и мире": пролистать по страничке все тома и найти на последней странице 4-го.
А коварство в том, что мне как-то удалось запустить программу и без этой кавычки!
Подумал, может, я этот несчастный недокавыченный "Yess!" добавил уже после первых запусков... Но нет! Протоколы говорят об обратном :shock:

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 16:10 
Заслуженный участник


20/08/14
11766
Россия, Москва
VAL в сообщении #1557589 писал(а):
А коварство в том, что мне как-то удалось запустить программу и без этой кавычки!
Как это ни странно, но есть разница запускать ли код прямо в PARI (через \r file.gp или просто набирая/вставляя) или запуская PARI для выполнения файла командой gp64.exe -q file.gp — в первом случае у меня Ваш код тоже запустился и молчал, ни памяти не хапнул, ни процессора, ни даже остановить себя по Ctrl-C не позволял, а вот сохранив весь текст в файл и запустив gp64.exe -q file.gp получил более-менее внятное сообщение об ошибке:
Код:
T:\>gp64.exe -q M318.gp
  ***   Warning: new stack size = 1073741824 (1024.000 Mbytes).
  ***   run-away string: ...            )))))};
  ***   quit;
  ***        ^-
... skipping file 'M318.gp'
?
Сильно это не помогло, пришлось разворачивать эту кучу невнятного текста в нормальный иерархический код с отступами и скобочками (потому что 90% опечаток у меня лично связаны именно с забытой/лишней скобочкой) и уже только тогда заметил странность.

Так что если что-то не работает, то полезно сохранить в файл и запускать по другому.
Рассказывать про общепринятое оформление кода понимаю бессмысленно. :-(

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 16:24 
Заслуженный участник


27/06/08
4062
Волгоград
Запускаю я сначала пустой exe'шник, а потом копирую туда программку. Самое интересное, что так я делал и когда все в игоге все работало (несмотря на отсутствие закрывающей кавычки), и когда зависало.
Dmitriy40 в сообщении #1557591 писал(а):
Рассказывать про общепринятое оформление кода понимаю бессмысленно. :-(
Правильно понимаете!
Лет 37 тому, когда я делал первые шаги в написании программ, меня уже били за это. Но и тогда уже было поздно :-)
Для меня главное, чтобы на страничку помещалось, дабы весь код перед глазами был. А парность скобок я проверяю, в notepad++.
А вот парность кавычек он, гад, не проверяет :oops:

-- 16 июн 2022, 17:17 --

Повторно разложил 850...500. На этот раз всего за час с небольшим (почему такая разница, знают только Бог и Дарио Алперн)

(Оффтоп)

850110 906168 382371 216057 545387 082625 772983 773608 338698 713882 862297 162247 190308 993041 704075 477374 723603 562500 (108 digits) = 2^2 × 5^6 × 1699 445829 859553 411400 105322 065849 864679 (40 digits) × 8003 652873 018143 615563 236294 297839 985832 184458 343462 982419 746783 (64 digits)

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 18:13 
Заслуженный участник


27/06/08
4062
Волгоград
Dmitriy40 в сообщении #1557614 писал(а):
Вы точно уверены что в разложении будут числа именно 22 и 56?
Внес очевидные поправки.
Насколько я понимаю, интерес представляли другие делители.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение16.06.2022, 22:13 


05/06/22
293
VAL в сообщении #1557595 писал(а):
Повторно разложил 850...500.


Thanks!

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение17.06.2022, 07:45 
Аватара пользователя


11/12/16
13850
уездный город Н
VAL в сообщении #1557595 писал(а):
Повторно разложил 850...500

Вчера запустил факторизацию:
а) $n+0$ на PARI/GP (на "счётах" - компьютере под Windows)
б) $n+8$ на Альпетроне (на планшете от Самсунга)
К утру ничего не посчиталось. Пункт б) считался порядка 20-и часов, так что Ваш компьютер как минимум в 20 раз мощнее моего планшета :D

-- 17.06.2022, 07:50 --

Dmitriy40 в сообщении #1557584 писал(а):
Так что в программе где Вы проверяете числа можно в начале добавить default(factor_add_primes,1);, а потом после вызова numdiv(n) спокойно вызвать ещё и factor(n) (на то же число или хотя бы его делители), которая выполнится мгновенно и выдаст полную факторизацию. Или в обратном порядке, без разницы.

И-эээх :cry: Жаль раньше не знал.
Я запускаю факторизацию конкретных чисел не через скрипт, а в ручную из коммандной строки. Но перед этим запускаю пару команд из Вашего .gp. В том числе
Код:
default(factor_add_primes,1);
Так что сработало ... бы.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение17.06.2022, 08:51 
Заслуженный участник


27/06/08
4062
Волгоград
Нашлась цепочка из 7 чисел по 152 делителя.
Привожу обновленную таблицу, в которой представлены все $k>4$, для которых установлено точное значение $M(k)$ и $k \mod 12 \in \{0,4,6,8\}$.

На данный момент у меня идет поиск максимальных цепочек для $k \in \{318,340,364,380\}$


Вложения:
All_k_with_M(k)_gt_3_proved_17-06-22.pdf [72.84 Кб]
Скачиваний: 270
 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение17.06.2022, 11:54 
Заслуженный участник


27/06/08
4062
Волгоград
И еще одна таблица.
Конечно, может оказаться, что я ничего не забыл и не перепутал, но это большая редкость. (В частности, мне казалось, что цепочку из 11 чисел по 60 делителей мы нашли, но я не нашел сообщения о том, что мы ее нашли :-( )
Поэтому проверьте, пожалуйста!
Представлены максимальные длины цепочек для всех тех $k$, для которых известны цепочки длиннее 7.
($L(k)$ - lower bound for $M(k)$, $U(k)$ - upper bound for $M(k)$)
\begin{tabular}{|l|l|l|}
\hline k & L(k)  & U(k) \\
\hline \textbf{12} & \textbf{15} & \textbf{15} \\
\hline 24 & 18 & 31 \\
\hline 36 & 13 & 15 \\
\hline 48 & 20 & 31 \\
\hline 60 & 11 & 23 \\
\hline 72 & 13 & 31 \\
\hline 84 & 10 & 23 \\
\hline 96 & 12 & 31 \\
\hline \end{tabular}

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение17.06.2022, 12:38 
Аватара пользователя


11/12/16
13850
уездный город Н
VAL в сообщении #1557705 писал(а):
(В частности, мне казалось, что цепочку из 11 чисел по 60 делителей мы нашли, но я не нашел сообщения о том, что мы ее нашли :-(


Она у меня нашлась, и обязательно было сообщение в этой теме. Кстати, она есть в файле Хуго с датой 18-05-2022, соответственно, близко к этой дате и было сообщенние о нахождении от меня.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение17.06.2022, 12:55 


05/06/22
293
VAL в сообщении #1557705 писал(а):
(В частности, мне казалось, что цепочку из 11 чисел по 60 делителей мы нашли, но я не нашел сообщения о том, что мы ее нашли :-( )


You emailed me about it on 18th May ("A292580 next update" thread).

The rest of the table matches what I know of, except I think I've proven M(84) <= 21, I'll see if I can work out where that came from.

 Профиль  
                  
 
 Re: Пентадекатлон мечты
Сообщение17.06.2022, 13:02 
Аватара пользователя


11/12/16
13850
уездный город Н
VAL
Кстати, писал ранее, но повторюсь.
Из этого перечня мы не считали с ускорителями цепочки с 24, 48, 72 и 96 делителями. Значит там можно улучшить на 1-2 позиции. Если Дмитрий ускорители сделает для них, конечно.
И очень обидно, что ускорители Дмитрия всё никак не пересекутся с Вашими вычислительными мощностями. Это тоже может дать улучшение на 1-2 позиции. Например, у Вас будет неплохой шанс найти 14-ку на 36 делителей, а если повезет, то и 15-ку....

Хуго обновил файл 14 июня, но в него не вошли цепочки длинной 7 и 8 на 84 делителя, которые нашел Дмитрий сразу, как сделал ускорители на 84 делителя.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3218 ]  На страницу Пред.  1 ... 74, 75, 76, 77, 78, 79, 80 ... 215  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group