A371156 - OEIS

%I #42 Apr 12 2024 10:47:16

%S 1,2,3,4,5,6,6,7,8,9,9,10,10,11,12,13,13,14,14,15,15,16,16,17,17,17,

%T 17,18,18,19,19,19,20,21,21,22,22,22,22,23,23,24,24,24,25,26,26,27,27,

%U 27,27,28,28,29,29,29,29,30,30,31,31,31,32,33,33,34,34,34

%N Length of the longest subsequence of 1, ..., n on which the Dedekind psi function (A001615) is nondecreasing.

%C The envelope max_{i<=n} (a(i)-A000720(i)) appears to be slowly increasing as n increases. For instance, a(1)-A000720(1)=1, whereas a(374598)-A000720(374598)=91 and a(642852)-A000720(642852)=96.

%H Chai Wah Wu, <a href="/A371156/b371156.txt">Table of n, a(n) for n = 1..10000</a>

%H Terence Tao, <a href="https://arxiv.org/abs/2309.02325">Monotone non-decreasing sequences of the Euler totient function</a>, arXiv:2309.02325 [math.NT], 2023. See Remark 4.7.

%F 0 <= a(n+1) - a(n) <= 1.

%F a(n) >= A000720(n)+1 since A001615(p) = p+1 for p prime.

%e a(7) = 6 because A001615 is nondecreasing on 1,2,3,4,5,6 or 1,2,3,4,5,7 but not on 1,2,3,4,5,6,7.

%o (Python)

%o from math import prod

%o from bisect import bisect

%o from sympy import primefactors

%o def A371156(n):

%o     def f(n):

%o         r = primefactors(n)

%o         return n*prod(p+1 for p in r)//prod(r)

%o     plist, qlist, c = tuple(f(i) for i in range(1,n+1)), [0]*(n+1), 0

%o     for i in range(n):

%o         qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i

%o         c = max(c,a)

%o     return c

%Y Cf. A000720, A001615, A365339, A365399, A365397, A365398, A365740.

%K nonn

%O 1,2

%A _Chai Wah Wu_, Apr 10 2024