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

[wrest]

Soul Friend в сообщении #1436708 писал(а):

Надо проверить число $n$, что оно не является суммой каких либо элементов вектора $A$.
Есть ли для этого готовая функция на PARI/GP, если нет - то, как это реализовать ?
$n \neq (k_1 + ... + k_i) $
где $k_x$ - элементы множества $A$.

1. $k_x$ -- натуральные, целые, вещественные?
2. Нужно ли думать о какой-то оптимизации (например $i$ чему может быть равно?)

В чём у вас собсно трудность? "Тупой" алгоритм будет генерировать все сочетания из $i$ чисел по $j=1 \dots i$ штук и считать их суммы. Это медленно для вас?

[Dmitriy40]

Soul Friend
Нечто подобное делал вот здесь (и рядом там посмотрите). Встроенной функции не знаю.
Вы бы уточнили порядок задачи, сколько $n$ надо проверить, длину вектора $A$, их тип, диапазон значений, фиксированы ли они или могут меняться по ходу решения ...

[Soul Friend]

wrest
1) $n, k_x \in \mathbb N$
2) $i$ - не фиксированное значение, ведь надо проверять все $2^m$ комбинации, где $m$ - количество элементов вектора $A$.
Не знаю даже как это тупым перебором сделать, вряд ли это возможно с двумя переменными $i, j$ .

Dmitriy40 в сообщении #1436787 писал(а):

Вы бы уточнили порядок задачи, сколько $n$ надо проверить, длину вектора $A$, их тип, диапазон значений, фиксированы ли они или могут меняться по ходу решения

Много $n$ надо проверять, если $n$ удовлетворяет неравенству, то добавляется к вектору $A$, поэтому количество элементов вектора $A$ растёт со временем.
Возможное решение - создать новый вектор $B$ для записи всех сумм.

[Soul Friend]

Soul Friend в сообщении #1436806 писал(а):

все $2^m$ комбинации

$2^m-m$ комбинации.

[wrest]

Soul Friend в сообщении #1436806 писал(а):

ведь надо проверять все $2^m$ комбинации, где $m$ - количество элементов вектора $A$.
Не знаю даже как это тупым перебором сделать, вряд ли это возможно

В качестве первого шага, запустите вот эти две строчки:
A=[1,8,5,9];
forsubset(#A,x,print("Sum",vecextract(A,x),"=",vecsum(vecextract(A,x))))
Задаются 4 элемента. Генерируются все сочетания от 0 до 4 элементов из этих 4 элементов, вычисляются их (сочетаний) суммы. Магия!
Теперь запускаем ещё пару строк:
n=14;
forsubset(#A,x,v=vecextract(A,x);if(vecsum(v)==n,print("Sum",v,"=",vecsum(v))))
Результат: печатаются только суммы, равные 14. Черная магия!

[Soul Friend]

wrest
Спасибо.

wrest в сообщении #1436816 писал(а):

forsubset(#A,x

означает перебрать $x$ от одного до $\#b$ как я понял?

[wrest]

Soul Friend в сообщении #1436836 писал(а):

означает перебрать $x$ от одного до $\#b$ как я понял?

Нет, не это. Вот тут гляньте https://pari.math.u-bordeaux.fr/dochtml ... ments.html есть описание что делает оператор forsubset.
Это итератор по всем подмножествам множества заданной мощности. При этом имеется в виду, что исходное множество например мощности $n$ -- это множество натуральных чисел от единицы до $n$.
Чтобы нагляднее понять, запустите команду
forsubset(4,x,print(x))

[Soul Friend]

Dmitriy40 в сообщении #1329592 писал(а):

У vecsort есть третий параметр, им можно например исключить дубли

а что это за параметр и как его использовать? Очень надо убрать повторения в векторе, мешают, и код из-за этого выдаёт не то что нужно.
из вектора $b$ надо убрать все повторяющиеся числа которые встречаются в векторе $a$.
Пример:
$b=[1, 3, 5, 1, 3, 3, 3, 9]$
$a=[1, 3, 7, 11, 13]$
результат должен быть:
$b=[5, 9]$
У меня получается убрать только первые два числа, в итоге получается $b=[5, 1, 3, 3, 3, 9]$
Набирал:

for(i=1, #a, b=vecsort(b, , a[i]) )

тоже выдает некий фантастический результат.

upd:
получилось только так:

b=setminus(vecsort(b), a)

но то ли это?
2) Вот этот код у меня работает на смартфоне, но на компе выдает ошибку:

forsubset(#a, x, b=concat(b, [vecsum(vecextract(a, x))]))

vecextract: incorrect type in vecextract [mask] (t_POL).

[wrest]

Soul Friend в сообщении #1436954 писал(а):

из вектора $b$ надо убрать все повторяющиеся числа которые встречаются в векторе $a$.
Пример:
$b=[1, 3, 5, 1, 3, 3, 3, 9]$
$a=[1, 3, 7, 11, 13]$
результат должен быть:
$b=[5, 9]$

А если
$b=[1,3,5]$
$a=[2,3,4]$
То какой результат должен быть?

[Soul Friend]

wrest в сообщении #1436961 писал(а):

А если
$b=[1,3,5]$
$a=[2,3,4]$
То какой результат должен быть?

$b=[1,5]$
Подсмотрел на Rozettacode, повторения в самом векторе убираются значением "8" :

b=vecsort(b, , 8)

Soul Friend в сообщении #1436954 писал(а):

2) Вот этот код у меня работает на смартфоне, но на компе выдает ошибку:
Код:

forsubset(#a, x, b=concat(b, [vecsum(vecextract(a, x))]))


vecextract: incorrect type in vecextract [mask] (t_POL).

Всё ещё не работает, пробовал и вручную набирать, и копипастить, выдает ту же ошибку, хотя на смартфоне работает.

[wrest]

Soul Friend в сообщении #1436964 писал(а):

Всё ещё не работает, пробовал и вручную набирать, и копипастить, выдает ту же ошибку, хотя на смартфоне работает.

Дополните так:
b=[];forsubset(#a, x, print("b=",b," a=",a," x=",x);b=concat(b, [vecsum(vecextract(a, x))]))
Что печатает?

-- 26.01.2020, 16:23 --

Soul Friend в сообщении #1436964 писал(а):

$b=[1,5]$
Подсмотрел на Rozettacode, повторения в самом векторе убираются значением "8" :

Тогда вместо
"из вектора b надо убрать все повторяющиеся числа которые встречаются в векторе a."
вы имеете в виду
"из вектора b надо убрать повторы чисел, а также все числа, которые встречаются в векторе a."
Через множества это делается так:
b=setminus(Set(b),Set(a))
Вообще множества в PARI/GP:
-- всегда упорядочены по возрастанию
-- не имеют повторяющихся элементов
То есть, если вы объединяете множество [1,2,3] и множество [2,3], то получаете множество [1,2,3]
Оператор объединения множеств setunion(x,y)

[Soul Friend]

wrest
Спасибо

wrest в сообщении #1437012 писал(а):

Что печатает?

Всё также выдавала ошибку, переустановил pari/gp, и заработала!

[kotenok gav]

Пару вопросов.
1. Как проверить число на простоту? На целость? На квадратность?
2. Как генерировать примитивные пифогоровы тройки?
3. Как генерировать примитивные пифогоровы тройки с заданым c?

[wrest]

kotenok gav
На прoстоту isprime(n) или ispseudoprime(n) Второе быстрей, но алгоритм вероятностный
На квадратичность issquare(n)
Насчет проверки на целость -- уточните вопрос. Или проверять тип (что он целый) или что дробная часть равна нулю. Второе например так isinteger(x)=if(frac(x)==0,1,0)

О пифагоровых тройках -- ну тут наверное много способов, тема же про калькулятор pari/gp, так что eсли у вас есть алгоритм, поможем с перекладыванием его на pari/gp

[kotenok gav]

Так у меня вопрос про пиф. тройки в PARI. Там есть встроенный алгоритм?