Вызов наибольшего делителя n меньшего m (PARI)

[kthxbye]

Существует ли на 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})$, то задача становится уже достаточно проблематичной.

[wrest]

kthxbye в сообщении #1548854 писал(а):

и наконец от числа $6$ мы отнимаем его наибольший делитель, меньший $2$, т.е. $1$, получаем $5$

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

[kthxbye]

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

kthxbye в сообщении #1548854 писал(а):

и наконец от числа $6$ мы отнимаем его наибольший делитель, меньший $2$, т.е. $1$, получаем $5$

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

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

[wrest]

Я ничего не понял. Да, так вот. Если нужен наибольший делитель, меньший половины $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 д.б. целые и больше единицы.

[kthxbye]

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))]

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