интерактивный курс: введение в программирование на PARI/GP

[maxal]

Свежий пример на использование функции algdep в PARI/GP:

maxal в сообщении #1052631 писал(а):

То есть, для заданного вещественного числа $\alpha$ нужно решить уравнение $\sqrt{m} - n = \alpha$ в целых числах $m,n$.
Переписывая $m = (n+\alpha)^2$, получаем, что $\alpha$ и $\alpha^2$ связаны целочисленным соотношением:

$$\alpha^2 + 2n\alpha + (n^2-m) = 0.$$

Есть множество алгоритмов для поиска таких соотношения.

Например, в PARI/GP можно воспользоваться функций lindep или, в случае степеней одного и того числа, как в этой задаче, функцией algdep. Используя пример с $\sqrt{10191265429393}$, имеем:

? q = frac( sqrt(10191265429393) )
%1 = 0.14158999127174780972955238643553005622
? f = algdep(q,2)
%2 = x^2 + 6384752*x - 904017
? n = polcoeff(f,1)/2
%3 = 3192376
? m = n^2 - polcoeff(f,0)
%4 = 10191265429393

Как видим, число $10191265429393$ успешно восстановлено по дробной части его корня.

[Nataly-Mak]

maxal в сообщении #120724 писал(а):

строчка

parisize = 8000000, primelimit = 500000

говорит нам о том, что под свои нужды PARI/GP захапала 8000000 байтов памяти (примерно 8 мегабайт) и создала список всех простых чисел меньших 500000. Простые числа используются во многих встроенных процедурах и их готовый список ускоряет вычисления.

Меня это о-ч-ч-ч-е-н-ь напугало. Это где ж мне столько памяти взять?
У меня её всего-то 2 Мб.

Я небольшую программку написала с помощью maxal и Begemot82:

for(n=865805100000, 1000000000000, if( ispseudoprime(n*30030+7433) && nextprime((n*30030+7433)+1)= 
n*30030+7433+6 && nextprime((n*30030+7433+6)+1)=n*30030+7433+24 && nextprime((n*30030+7433+24)+1)= 
n*30030+7433+30 && nextprime((n*30030+7433+30)+1)=n*30030+7433+54 && nextprime((n*30030+7433+54)+1)= 
n*30030+7433+66 && nextprime((n*30030+7433+66)+1)=n*30030+7433+84 && nextprime((n*30030+7433+84)+1)= 
n*30030+7433+90 && nextprime((n*30030+7433+90)+1)=n*30030+7433+96 && nextprime((n*30030+7433+96)+1)= 
n*30030+7433+114 && nextprime((n*30030+7433+114)+1)=n*30030+7433+126 && nextprime((n*30030+7433+126)+1)= 
n*30030+7433+150 && nextprime((n*30030+7433+150)+1)=n*30030+7433+156 && nextprime((n*30030+7433+156)+1)= 
n*30030+7433+174 && nextprime((n*30030+7433+174)+1)=n*30030+7433+180, print(n); ); );

Прошу прокомментировать: это правильно?

[Begemot82]

Nataly-Mak в сообщении #1058128 писал(а):

У меня её всего-то 2 Мб.

Как же живете? 2Гб все же.

[Nataly-Mak]

Ax, правда, 2 Гб.
Заскок

[iifat]

Nataly-Mak в сообщении #1058128 писал(а):

У меня её всего-то 2 Мб

Имеется в виду, подозреваю, виртуальная. При 2 Гб оперативки 8 Гб будет более или менее нормально работать.

[Nataly-Mak]

iifat
разобрались уже
Конечно, оперативная память у моего компьютера 2Гб, а не 2 Мб.

[Nataly-Mak]

maxal в сообщении #121142 писал(а):

Или вот так можно напечатать все простые числа вида $n^2+1$, где $150\leq n\leq 300$:

? for(n=150,300, t=n^2+1; if( isprime(t), print1(t,", ") ) )
22501, 24337, 25601, 28901, 30977, 32401, 33857, 41617, 42437, 44101, 50177, 52901, 55697, 57601, 62501, 65537, 67601, 69697, 72901, 78401, 80657, 90001,

Из этого примера мы узнаем о конструкции if( условие, код_если_выполнено ), которая в более общем виде выглядит как if( условие, код_если_выполнено, код_если_не_выполнено ), а также о функции isprime(), которая тестирует целые числа на простоту. Она возвращает 1, если аргумент является простым числом, 0 в противном случае.

maxal
в коде, который вы прислали мне вчера, функция проверки числа на простоту имеет вид

ispseudoprime(n*30030+7433)

Почему это отличается от того, что мы видим в цитате?

-- Чт окт 01, 2015 18:46:06 --

Скачала exe-программу, на которую указал Begemot82:

Begemot82 в сообщении #1058074 писал(а):

Для изучения я скачивал один ехе-шник gp64-readline-2-7-4.exe. На первых порах достаточно.

Запустила эту программу, вот увидела окно.
Задала вопрос о функции ispseudoprime(x), мне что-то даже ответили



А что мне дальше делать? Как выполнить свою программку?
Сейчас буду снова перечитывать лекции, может быть, что-то там найду.
Может, этой программы мало, чтобы свои программы выполнять?
Товарищи, может, кто-нибудь подскажет, чтобы быстрее получилось?

-- Чт окт 01, 2015 18:56:18 --

Программка моя ещё раз с некоторыми изменениями:

for(n=865805100000,1000000000000, if( ispseudoprime(n*30030+7433) && nextprime((n*30030+7433)+1)== 
n*30030+7433+6 && nextprime((n*30030+7433+6)+1)==n*30030+7433+24 && nextprime((n*30030+7433+24)+1)== 
n*30030+7433+30 && nextprime((n*30030+7433+30)+1)==n*30030+7433+54 && nextprime((n*30030+7433+54)+1)== 
n*30030+7433+66 && nextprime((n*30030+7433+66)+1)==n*30030+7433+84 && nextprime((n*30030+7433+84)+1)== 
n*30030+7433+90 && nextprime((n*30030+7433+90)+1)==n*30030+7433+96 && nextprime((n*30030+7433+96)+1)== 
n*30030+7433+114 && nextprime((n*30030+7433+114)+1)==n*30030+7433+126 && nextprime((n*30030+7433+126)+1)== 
n*30030+7433+150 && nextprime((n*30030+7433+150)+1)==n*30030+7433+156 && nextprime((n*30030+7433+156)+1)== 
n*30030+7433+174 && nextprime((n*30030+7433+174)+1)==n*30030+7433+180, print(n) ) )

-- Чт окт 01, 2015 19:03:41 --

Это что, всю программу надо вручную набирать в этом окошке?
Никакого копирования из буфера обмена нет? Я попыталась, ни черта не получается.
Как вставить-то код программы в это окошко?

[maxal]

Nataly-Mak в сообщении #1058157 писал(а):

maxal
в коде, который вы прислали мне вчера, функция проверки числа на простоту имеет вид

ispseudoprime(n*30030+7433)

Почему это отличается от того, что мы видим в цитате?

См. post1023160.html#p1023160
Вкратце - ispseudoprime работает гораздо быстрее чем isprime, и для практических приложений вполне достаточна (хотя и не гарантирует простоту на 100%).

Nataly-Mak в сообщении #1058157 писал(а):

А что мне дальше делать? Как выполнить свою программку?

См. post255964.html#p255964

[Nataly-Mak]

Сначала вставлю результат своих мучений, набрала код 5 раз и всё не так


А что не так?
Всё по-английски, ни черта не понимаю.
Нет, похоже, этот PARI/GP не для меня.

-- Чт окт 01, 2015 21:00:06 --

Создала файл с программкой.
Пишу команду

\r A45.gp

Выдаётся ошибка

? \r A45.gp
  ***   error opening input file: `A45.gp'.
  ***   Break loop: type 'break' to go back to GP prompt
break>

Что не так?

-- Чт окт 01, 2015 21:16:31 --

Содержимое файла A45.gp

{for(n=865805100000,1000000000000, 
if( ispseudoprime(n*30030+7433), nextprime((n*30030+7433)+1)==n*30030+7433+6, 
nextprime((n*30030+7433+6)+1)==n*30030+7433+24, nextprime((n*30030+7433+24)+1)==n*30030+7433+30, 
nextprime((n*30030+7433+30)+1)==n*30030+7433+54, nextprime((n*30030+7433+54)+1)==n*30030+7433+66,
nextprime((n*30030+7433+66)+1)==n*30030+7433+84, nextprime((n*30030+7433+84)+1)==n*30030+7433+90,
nextprime((n*30030+7433+90)+1)==n*30030+7433+96, nextprime((n*30030+7433+96)+1)==n*30030+7433+114,
nextprime((n*30030+7433+114)+1)==n*30030+7433+126, nextprime((n*30030+7433+126)+1)== n*30030+7433+150, 
nextprime((n*30030+7433+150)+1)==n*30030+7433+156, nextprime((n*30030+7433+156)+1)==n*30030+7433+174, 
nextprime((n*30030+7433+174)+1)==n*30030+7433+180, print(n) ) )
}

maxal
пожалуйста, скажите, где ошибки.
Файл читаться не хочет

[maxal]

Nataly-Mak, код на экране отличается от того, что приведен вами выше в post1058157.html#p1058157
Например, у вас почему-то отсутствуют знаки && между условиями (вместо них откуда-то взялись запятые - это ошибка).
По поповоду загрузки файла -- PARI/GP у вас его не находит. Либо положите в ту же директорию откуда вы запускаете PARI/GP, либо при загрузке указывайте с полным путем:
\r C:\MyDirectory\A5.gp или \r "C:\MyDirectory\A5.gp" (не знаю как точно, это выглядит в виндоус)

[Nataly-Mak]

Файл у меня в той же директории находится.
Сейчас изменила запятые на &&,

{for(n=865805100000,1000000000000, 
if( ispseudoprime(n*30030+7433) && nextprime((n*30030+7433)+1)==n*30030+7433+6 && 
nextprime((n*30030+7433+6)+1)==n*30030+7433+24 && nextprime((n*30030+7433+24)+1)==n*30030+7433+30 && 
nextprime((n*30030+7433+30)+1)==n*30030+7433+54 && nextprime((n*30030+7433+54)+1)==n*30030+7433+66 &&
nextprime((n*30030+7433+66)+1)==n*30030+7433+84 && nextprime((n*30030+7433+84)+1)==n*30030+7433+90 &&
nextprime((n*30030+7433+90)+1)==n*30030+7433+96 && nextprime((n*30030+7433+96)+1)==n*30030+7433+114 &&
nextprime((n*30030+7433+114)+1)==n*30030+7433+126 && nextprime((n*30030+7433+126)+1)== n*30030+7433+150 && 
nextprime((n*30030+7433+150)+1)==n*30030+7433+156 && nextprime((n*30030+7433+156)+1)==n*30030+7433+174 && 
nextprime((n*30030+7433+174)+1)==n*30030+7433+180 && print(n); );
);
}

всё равно файл не открывается.
В конце не знаю, нужны ";" или нет.
У вас они были. Begemot82 говорит, что они не нужны, у него с ними ошибки.

Не открывается файл, выдаётся та же самая ошибка. Почему PARI/GP его не находит, если он в той же директории находится?
Может быть, формат файла не тот?
У меня файл A45 первоначально был в текстовом формате. Я записала в него программку. Потом переименовала его, сделав расширение gp. Это правильно?

[Begemot82]

Nataly-Mak в сообщении #1058222 писал(а):

В конце не знаю, нужны ";" или нет.
У вас они были. Begemot82 говорит, что они не нужны, у него с ними ошибки.

Не пойму, сейчас и с ними и без них работает.
Перед print запятая.

-- 01.10.2015, 20:46 --

Расширение может быть любым.
Переименуйте файл, возможно "А" русская

[Nataly-Mak]

Кажется, поняла.
Дело действительно в формате файла.
maxal
входной файл обязательно должен иметь расширение gp?
А расширение txt не годится?
Тогда я не знаю, как сделать у текстового файла расширение gp.

-- Чт окт 01, 2015 21:58:55 --

Теперь файл загрузился, но... программа всё равно не выполняется

? \r A45.txt
? runme(2)
  ***   at top-level: runme(2)
  ***                 ^--------
  ***   not a function in function call
  ***   Break loop: type 'break' to go back to GP prompt
break>

Чего сейчас не хватает? Что за ошибка тут выдаётся?
О-о-о-о-о-о!

-- Чт окт 01, 2015 22:04:54 --

Ну конечно:

? \r myprog.gp
? runme(2)

тут совершенно специфический запуск программы (как вызов функции).

А мне-то как запускать
Пробовала просто командой run, не получилось.

-- Чт окт 01, 2015 22:05:26 --

Интерактивность нулевая

-- Чт окт 01, 2015 22:22:00 --

Кажется так:

\r A45.txt

и запускает программу, записанную в этом файле.
Больше ничего не надо писать.
Сейчас увеличила интервал для переменной цикла, программа вроде работает. Жду.

-- Чт окт 01, 2015 22:35:37 --

{for(n=865805100000,1000000000000, 
if( ispseudoprime(n*30030+7433) && nextprime((n*30030+7433)+1)==n*30030+7433+6 && 
nextprime((n*30030+7433+6)+1)==n*30030+7433+24 && nextprime((n*30030+7433+24)+1)==n*30030+7433+30 && 
nextprime((n*30030+7433+30)+1)==n*30030+7433+54 && nextprime((n*30030+7433+54)+1)==n*30030+7433+66 &&
nextprime((n*30030+7433+66)+1)==n*30030+7433+84 && nextprime((n*30030+7433+84)+1)==n*30030+7433+90 &&
nextprime((n*30030+7433+90)+1)==n*30030+7433+96 && nextprime((n*30030+7433+96)+1)==n*30030+7433+114 &&
nextprime((n*30030+7433+114)+1)==n*30030+7433+126 && nextprime((n*30030+7433+126)+1)== n*30030+7433+150 && 
nextprime((n*30030+7433+150)+1)==n*30030+7433+156 && nextprime((n*30030+7433+156)+1)==n*30030+7433+174 && 
nextprime((n*30030+7433+174)+1)==n*30030+7433+180 && print(n); );
);
}

В конце, перед print исправила && на запятую.

Нет, надо программу тестировать. Что она там выполняет или ни черта не выполняет?
Просто висит и ничего не говорит.

-- Чт окт 01, 2015 22:48:23 --

Ага, вот и сказала:

? \r A45.txt
865895788180
?

Это я, правда, оставила только совпадение 7 элементов паттерна.
Сейчас проверю в WA, правильно это посчитано.
А чего искать 15 совпадений, когда и 7 крайне редки, а ведь 15 совпадений без 7 невозможны

[Nataly-Mak]

Ого, класс!

Select[Range[0,180],PrimeQ[(865895788180*30030+7433)+#]&]
{0, 6, 24, 30, 54, 66, 84, 90, 96, 126, 174}

Сравните с паттерном

0  6  24  30  54  66  84  90  96  114  126  150  156  174  180

Решение с 4 "дырками"

Уф, кажется, вырулила

maxal
большое вам спасибо за техподдержку!

[maxal]

Nataly-Mak, не за что. Просьба в этой теме обсуждать только непосредственно PARI/GP.