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

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, 17, 18, 18, 19, 19, 19, 20, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 26, 26, 27, 27, 27, 27, 28, 28, 29, 29, 29, 29, 30, 30, 31, 31, 31, 32, 33, 33, 34, 34, 34

Offset: 1

Author

Chai Wah Wu, Apr 10 2024

Keywords

• nonn

Comments

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.

Examples

			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.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000
• Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023. See Remark 4.7.

Crossrefs

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

Programs

Mathematica

Length[LongestOrderedSequence[#]] & /@ Rest[FoldList[Append, {}, Table[n DivisorSum[n, MoebiusMu[#]^2/# &], {n, 20}]]] (* Eric W. Weisstein, Mar 09 2025 *)

Python

from math import prod
from bisect import bisect
from sympy import primefactors
def A371156(n):
    def f(n):
        r = primefactors(n)
        return n*prod(p+1 for p in r)//prod(r)
    plist, qlist, c = tuple(f(i) for i in range(1,n+1)), [0]*(n+1), 0
    for i in range(n):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c

Formula

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

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