Функция Эйлера через рекурсию

[kthxbye]

Пусть $a(n)$ это A007052. Здесь

$$a(n)=4a(n-1)-2a(n-2), a(0)=1, a(1)=3$$

Пусть $\varphi(n)$ это A000010, т.е. функция Эйлера. Тогда для

$$R_1(n,q)=\sum\limits_{j=0}^{\varphi(q+1)+1}R_1(n-1,j)$$

предположительно будем иметь

$$R_1(n,0)=a(n)$$

Вот простенькая прога на PARI/GP для проверки:

R1_upto(n)=my(v1, v2, v3); v1=vector(2*n+1, i, 1); v2=v1; v3=vector(n+1, i, 0); v3[1]=1; for(i=1, n, for(q=0, 2*(n-i), v2[q+1]=sum(j=0, eulerphi(q+1)+1, v1[j+1])); v1=v2; v3[i+1]=v1[1];); v3
a(n)=real((2 + quadgen(8))^(n+1)) / 2
test(n)=R1_upto(n)==vector(n+1,i,a(i-1))

Возникает вопрос: является ли $\varphi(n)$ единственной в своем роде или же существует другая функция $f(n)$, такая, что для

$$R_2(n,q)=\sum\limits_{j=0}^{f(q+1)+1}R_2(n-1,j)$$

будем иметь

$$R_2(n,0)=a(n)$$

Если она единственная, то можно ли каким-то образом восстановить значения $R_1(n,q)$ для $q>0$ если нам известны значения $R_1(n,0)$ и неизвестны значения $\varphi(n)$? В частности, наибольший интерес представляют $R_1(1,q)=\varphi(q+1)+2$. Если научиться их восстанавливать, мы сможем вычислять функцию Эйлера еще одним оригинальным способом.

-- 22.06.2023, 16:08 --

Что еще удалось заметить?

Пусть $\pi(n)$ это A000720, т.е. функция распределения простых чисел. Тогда для

$$R_3(n,q)=\sum\limits_{j=0}^{\pi(q+1)+1}R_3(n-1,j)$$

предположительно будем иметь

$$R_3(n,0)=\frac{3^n+1}{2}$$

Вопрос здесь аналогичен предыдущему: можно ли восстанавливать значения?

[kthxbye]

С функцией

$$R(n,q)=\sum\limits_{j=0}^{f(q)}R(n-1,j)$$

следует работать аккуратно. Когда $f(q)=q+1$, то она абсолютно рекуррентная, т.е. для вычисления $R(n,0)$ нужно знать все больше и больше значений $R(n,q)$. Но когда допустим $f(q)=\varphi(q+1)+1$, то первые четыре значения верхнего предела суммы это $2,2,3,3$. Т.е. будем иметь

$$R(n,0)=\sum\limits_{j=0}^{2}R(n-1,j)$$

$$R(n,1)=\sum\limits_{j=0}^{2}R(n-1,j)$$

$$R(n,2)=\sum\limits_{j=0}^{3}R(n-1,j)$$

$$R(n,3)=\sum\limits_{j=0}^{3}R(n-1,j)$$

И все! Этого достаточно чтобы вычислить сколько угодно значений $R(n,0)$. Аналогичная ситуация с $f(q)=\pi(q+1)+1$. Т.е. восстановить к сожалению ничего не получится.

Но это раскрывает глаза на природу $R(n,q)$: можно выбрать некоторое максимальное $m$, до которого можно суммировать $f(q)$ для $q<m$, а также учесть, что $f(m)\leqslant m$. Можно заняться изучением этого типа последовательностей и посмотреть какие $R(n,0)$ получаются в этом случае.