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

[Aether]

Да,действительно, я хотел добавить if, спасибо всё заработало:

fordiv(105,d, if(isok(d), print(d)))

, причем всё работает с запятой.

-- 23.02.2017, 20:41 --

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

Хоть это уже и не нужно, но всё же:

Спасибо, это как-раз-таки тоже нужно.

[Dmitriy40]

Aether в сообщении #1194833 писал(а):

причем всё работает с запятой.

Дык, в таком виде, внутри оператора if, оно и должно работать именно с запятой. Вы бы разобрались чем запятая отличается от точки с запятой, а?

Да, и matsize()[2] разумеется неправильно работает с вертикальными векторами (которые создаются функцией vectorv), хорошо что они применяются весьма ограниченно.

[Aether]

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

Вы бы разобрались чем запятая отличается от точки с запятой, а?

Так я не против, но не знаю где про это можно посмотреть? Помню в теме что-то про это где-то было.

[Dmitriy40]

Aether
Запятая разделяет аргументы функций и элементы в списках, а точка с запятой разделяет несколько операторов так, чтобы они воспринимались как один длинный оператор - тогда это позволит написать несколько операторов там, где допустим лишь один. Пример на ";":

for(i=1,10, n=i+1; k=n*2; print(k+i))

хотя в for допустим лишь ровно один оператор, тут написали аж три, что и позволила ";" между ними. Другой такой же пример был с функцией ismn() (о чём я сам не сразу вспомнил).

Ещё точка с запятой в конце строки подавляет вывод на консоль результата операций, сравните результаты ввода строк v=1 и v=2;, но этим в программах пользуются редко.

[Aether]

Dmitriy40, Спасибо, понял. Я давно обратил внимание на подавление вывода на консоль.

-- 23.02.2017, 21:36 --

У меня получился такой код:

for(n=1,105, print1(n, ": "); fordiv(n,d, if(isok(d), print1(d, ", "))); print()) 

, который выводит для каждого n в пределах 1-105 его делители, являющиеся степенями чисел Мерсенна. Но мне необходимо не просто выводить эти значения на печать, а иметь возможность работать с ними.Т.е. их необходимо сохранять, например создавать переменные, либо записывать их в вектор. Количество таких переменных неизвестно для каждого числа или необходимо создать вектор неизвестной длины. Что здесь лучше использовать? В дальнейшем, перебирая различные произведения этих переменных или значений вектора, получаемых для конкретного n, необходимо будет выяснить, можно ли получить в результате такого умножения n.

[Dmitriy40]

Aether в сообщении #1194839 писал(а):

Но мне необходимо не просто выводить эти значения на печать, а иметь возможность работать с ними.Т.е. их необходимо сохранять, например создавать переменные, либо записывать их в вектор. Количество таких переменных неизвестно для каждого числа или необходимо создать вектор неизвестной длины. Что здесь лучше использовать?

Насчёт лучше не знаю, но вектор сюда просится, да и сделать несложно:

v=[]; for(n=1,105, fordiv(n,d, if(isok(d), v=vecsort(concat(v,d),,8)))); print(v)

vecsort с флагом 8 пришлось применить для исключения дублей (возникают для разных n). Решение наверняка далеко не оптимально. Вектор создаётся общий для всех n, как сделать отдельный для каждого n и сохранить их все сходу не придумывается. Но вероятно можно весь анализ встроить внутрь for, тогда сохранять вектора для разных n и не нужно.

[Aether]

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

-- 23.02.2017, 22:32 --

Проблему бы решило наличие в языке функции, дающей множество разложений числа на множители. Но при этом всё придется начинать сначала.

[Dmitriy40]

Aether в сообщении #1194853 писал(а):

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

Чем в данном месте не устраивает обычный for?

a=1; b=105; for(n=a,b, for(i=n,b+n, print(i)))

Для прохода по вектору произвольной длины вполне себе работает:

v=[1,2,3,7,9]; for(i=1,matsize(v)[2], print(v[i]))

Aether в сообщении #1194853 писал(а):

функции, дающей множество разложений числа на множители.

Кажется на это уже отвечал: divisors, factor, factorint. Формируете первой вектор всех возможных делителей, потом двумя циклами по нему проходите и проверяете произведение или чего там хотите. Или циклом fordiv проверяете все делители на своё условие, подходящие пишите в вектор, а потом двумя циклами по этому вектору идёте и проверяете произведение. Ещё можно не двумя циклами идти, а по вектору сформировать сразу квадратную матрицу всех произведений командой типа

w=matsize(v)[2]; m=matrix(w,w,x,y,v[x]*v[y])

чего правда потом с ней делать ещё не придумал.
В общем варианты есть и выше были примеры.

[Aether]

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

а потом двумя циклами по этому вектору идёте и проверяете произведение.

Например число 651 имеет делители, являющиеся степенями чисел Мерсенна: 1,3,7,31. Чтобы убедиться, что данное число представимо в виде произведения данных делителей, сначала необходимо перемножить делители попарно всеми возможными вариантами, затем по 3, всеми возможными способами. Число 630 имеет уже 6 делителей удовлетворяющих условию, но оно не представимо в виде их произведения, чтобы в этом убедится, необходимо рассмотреть все варианты перемножения по 2, по 3, по 4 и по 5 множителей. Но может попасться и число, имеющее 50 подходящих делителей, тогда их необходимо будет сначала перемножать попарно и сравнивать результат, затем по 3, затем по 4, затем по 30 например, прежде чем мы удостоверимся, что число можно представить в виде произведения таких делителей, или вовсе придется рассматривать все варианты вплоть до 49 множителей, если число непредставимо в виде своих, удовлетворяющих условию делителей. Что-то я не особо себе представляю как всё это уложить в 2 цикла.

-- 24.02.2017, 00:04 --

Средствами Wolfram Mathematica удалось создать код, разрешающий данную задачу и генерирующий искомую последовательность. Надеюсь, что средствами PARI/GP это также можно сделать, иначе изучать калькулятор не имеет смысла. Возможно, необходимо знание каких-то математических фактов, чтобы упростить код. Или какой-то другой подход. Но пока что я не вижу как это возможно решить.

[Dmitriy40]

Aether
Ну так да, двумя не обойдётся, да и любым заранее заданным тоже.
Тогда я пас. Всё что приходит в голову - делать руками факторизацию в базисе чисел Мерсенна (благо их не так много и легко вычисляются). Тупо циклом по числам Мерсенна вплоть до получения единицы делить исходное число на каждое число Мерсенна пока делится. Надеюсь речь не идёт про числа типа $10^{100}$.
Хотя почему пас, сделал кажется, именно факторизацию, но работает весьма не быстро:

forstep(x=3,100000,2, t=x; v=[]; for(n=2,16, m=2^n-1; while(t%m==0, t=t\m; v=concat(v,m))); if(t==1, print(x,":",v)))

Не знаю это ли было надо.

[Aether]

Спасибо, но немного не то. Вы похоже сделали факторизацию по простым числам Мерсенна, а надо было сделать разложение на множители, являющиеся степенями любых чисел Мерсенна. Например туда должно входить число $15=(2^1-1)(2^4-1)$

Например в эту последовательность должны входить числа подобные $(2^4-1)^3(2^7-1)^2(2^9-1)(2^{13-1})^6........$

[Dmitriy40]

Нет, надо было похоже не совсем это, $15$ в список не попало. Ну тогда можно сменить порядок перебора чисел Мерсенна на обратный:

forstep(x=3,100000,2, t=x; v=[]; forstep(n=16,2,-1, m=2^n-1; while(t%m==0, t=t\m; v=concat(v,m))); if(t==1, print(x,":",v)))

Теперь есть числа, которые не попали в список?

PS. Ну и формула у Вас в MATHEMATICA, мрак.

[Aether]

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

Теперь есть числа, которые не попали в список?

почему-то нет.

-- 24.02.2017, 01:11 --

Видимо в математике неспроста такой код.

Прошу прощения, последний код выдал правильную последовательность, это я не туда смотрел. Да, этот код действительно существенно короче чем код математики. PARI/GP заслуживает внимания, в чем Вы меня убедили своим блестящим решением. Спасибо.

-- 24.02.2017, 01:28 --

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

PS. Ну и формула у Вас в MATHEMATICA, мрак.

Было бы неплохо, если бы Вы добавили в последовательность свой код.

[Dmitriy40]

Ну не надо, вовсе оно не блестящее, сделано всё втупую. Почти уверен что есть несложный признак делимости на число вида $2^n-1$ (как и на 9 в десятичной системе), задействовав который вычисления упростятся или ускорятся. Но для задачи публикации в A282572 примера программы достаточно и этого кода (если убрать упоминания вектора).

[Aether]

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

Ну не надо, вовсе оно не блестящее, сделано всё втупую.

Ну не скромничайте, всё кратко и работает. Я сожалею, что не дошел до этого решения сам, тогда я разместил бы этот код сам.

forstep(x=3,100000,2, t=x; v=[]; forstep(n=16,2,-1, m=2^n-1; while(t%m==0, t=t\m; v=concat(v,m))); if(t==1, print(x,":",v)))

Я не понял, как Вы организовали факторизацию по числам вида $2^n-1$ и что здесь означает t%m, а также t\m?

Вы организовали цикл от 3 до 100000 с шагом 2, где определили переменную t=x и нулевой вектор v. Внутри этого цикла организовали ещё один цикл, от 16 до 2 с шагом -1. Нельзя ли поподробнее объяснить, что происходит в цикле while?