2014 dxdy logo

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

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




 
 Вызов наибольшего делителя n меньшего m (PARI)
Сообщение15.02.2022, 16:21 
Аватара пользователя
Существует ли на PARI функция вызова наибольшего делителя $n$ меньшего $m$?

Например нам нужно осуществить трансформацию:
$$27-18-12-8-6-5$$

Осуществляется она следующим образом:

  • первым делом мы отнимаем от числа $27$ его наибольший делитель, меньший $27$, т.е. $9$, получаем $18$
  • затем от числа $18$ мы отнимаем его наибольший делитель, меньший $9$, т.е. $6$, получаем $12$
  • после этого от числа $12$ мы отнимаем его наибольший делитель, меньший $6$, т.е. $4$, получаем $8$
  • затем от числа $8$ мы отнимаем его наибольший делитель, меньший $4$, т.е. $2$, получаем $6$
  • и наконец от числа $6$ мы отнимаем его наибольший делитель, меньший $2$, т.е. $1$, получаем $5$

Очевидно, что дальше двигаться уже нельзя. Значит интересующее нас число это $5$. То же самое, но без вызова наибольшего делителя $n$ меньшего $m$ можно реализовать через
$$\begin{bmatrix}
27 & - \\
27 & 26 \\
27 & 25 \\
27 & 24 \\
27 & 23 \\
27 & 22 \\
27 & 21 \\
27 & 20 \\
27 & 19 \\
27 & 18 \\
27 & 17 \\
27 & 16 \\
27 & 15 \\
27 & 14 \\
27 & 13 \\
27 & 12 \\
27 & 11 \\
27 & 10 \\
18 & 9 \\
18 & 8 \\
18 & 7 \\
12 & 6 \\
12 & 5 \\
8 & 4 \\
8 & 3 \\
6 & 2 \\
5 & 1
\end{bmatrix}$$
Т.е. здесь у нас
$$a(n,m)=\begin{cases}
m,&\text{если $n=0$;}\\
a(n-1,m)-(m-n),&\text{если $a(n-1,m)\operatorname{mod}(m-n)=0$;}\\
a(n-1,m),&\text{в противном случае.}
\end{cases}$$
Вот простейшая программка:
Код:
a(n)=local(A=n, D); for(i=1, n-1, D=n-i; A=if(A%D==0,A-D,A)); return(A)

Работает неплохо, когда надо сгенерить немного первых значений $a(n)$, но когда речь заходит об $a(\frac{3^n+1}{2})$, то задача становится уже достаточно проблематичной.

 
 
 
 Re: Вызов наибольшего делителя n меньшего m (PARI)
Сообщение15.02.2022, 17:47 
kthxbye в сообщении #1548854 писал(а):
и наконец от числа $6$ мы отнимаем его наибольший делитель, меньший $2$, т.е. $1$, получаем $5$

Схема сбилась: до этого везде отнимали делитель меньший половины, т.е. для $6$ это меньше $3$, а не $2$.

 
 
 
 Re: Вызов наибольшего делителя n меньшего m (PARI)
Сообщение15.02.2022, 17:51 
Аватара пользователя
wrest в сообщении #1548861 писал(а):
kthxbye в сообщении #1548854 писал(а):
и наконец от числа $6$ мы отнимаем его наибольший делитель, меньший $2$, т.е. $1$, получаем $5$

Схема сбилась: до этого везде отнимали делитель меньший половины, т.е. для $6$ это меньше $3$, а не $2$.

Меньший числа после "т.е." в предыдущей строке.

 
 
 
 Re: Вызов наибольшего делителя n меньшего m (PARI)
Сообщение15.02.2022, 18:09 
Я ничего не понял. Да, так вот. Если нужен наибольший делитель, меньший половины $n$, то его вернёт вам функция
k(n)=my (v=divisors(n));if(n>2,if(v[2]==2, v[#v-2],v[#v-1]),1)

-- 15.02.2022, 18:33 --

А, теперь понял. Ну чтоб не париться самостоятельно с сортировками и переборами, предлагаю такую функцию, будет делать что спрашиваете:
k(n,m)=my(s=Set(divisors(n)));s=setunion(s,Set(m));s[setsearch(s,m)-1]
Проверок не делается, n и m д.б. целые и больше единицы.

 
 
 
 Re: Вызов наибольшего делителя n меньшего m (PARI)
Сообщение15.02.2022, 18:56 
Аватара пользователя
wrest в сообщении #1548866 писал(а):
А, теперь понял. Ну чтоб не париться самостоятельно с сортировками и переборами, предлагаю такую функцию, будет делать что спрашиваете:
k(n,m)=my(s=Set(divisors(n)));s=setunion(s,Set(m));s[setsearch(s,m)-1]
Проверок не делается, n и m д.б. больше единицы.

Благодарю, работает отменно. Сам пока мучился слепил такой вариант:
Код:
row(n)=Vecrev(divisors(n))
row1(n,m)=row(n)[numdiv(n)+1-sum(j=1,numdiv(n),if(row(n)[j]<m,1,0))]

Ваш работает гораздо быстрее, еще раз благодарю.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group