Let $\varphi(m)$ for integers $m\geq 1$ the Euler's totient function. Then for integers $n\geq 1$ we define the recurrence $$a_{n+1}=n\cdot\varphi(a_n)+a_{\varphi(n)}\tag{1}$$ with seed value $a_1=1$.

Question. I suspect (my computational evidence is very small since I've calculated only the first 80 terms) that $$\log a_n=O(n)\tag{2}$$ as $n\to\infty$. Am I right? Many thanks.

Computational facts and remarks as a motivation to study the recurrence. The sequence $a_n$ starts as $$1, 2, 3, 8, 18, 38, 110, 318, 840, 1766\ldots$$ And seems (it isn't related to our Question) that maybe the sequence $$-1+a_n$$ for $n>1$ has infinitely many terms without repeated prime factors. The most obvious fact about the Euler's totient is $\varphi(m)\leq m$ (maybe using this inequality and Stirling's approximation can be deduced a statement, but I believe that it doesn't improve my conjecture $(2)$). Finally in next Appendix I add a program that I've used with a Pari/GP calculator to plot the sequence $$b_n:=\log a_n$$ for $1\leq n\leq 80$.


N = 80;
a = vector(N); a[1]=1;
for( k = 1,  N-1, { a[k+1] = k*eulerphi(a[k])+a[eulerphi(k)];});
b = vector(N);
for( k = 1,  N, { b[k] = log(a[k]);});
x = vector(N); for( k = 1,  N, { x[k] = k;});
  • 1
    $\begingroup$ This sequence is very difficult to calculate! It grows very fast and we need the factorization of the previous term. $\endgroup$ – Peter Jun 17 '18 at 21:17
  • $\begingroup$ Many thanks for your attention @Peter , but the sequence grows much more faster than my conjecture $(1)$? $\endgroup$ – user243301 Jun 17 '18 at 21:40
  • $\begingroup$ I am currently at entry $96$. Could be a very hard factorization. I have no clue yet whether your asymptotic holds. We would, of course, need more entries, but this could be difficult. $\endgroup$ – Peter Jun 17 '18 at 21:48
  • $\begingroup$ What about the $80$ entries you calculated ? It could be helpful to show numerical results about this range. I decided to quit and to recalculate the values upto entry $95$. $\endgroup$ – Peter Jun 17 '18 at 21:50
  • 1
    $\begingroup$ Using non-linear regression with Arndt-Brünners math-site , I figured out that $$\ln(a_n) \approx 0.41\cdot n^{1.41}-1.13\ln(n)$$ but I am not sure whether the approximation keeps good for larger values. $\endgroup$ – Peter Jun 17 '18 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy