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,2

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.

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.

Formula

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

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

Example

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.

Prog

(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

Crossrefs

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

Sequence in context: A121604 A071520 A195918 * A176842 A278055 A291764

Adjacent sequences: A371153 A371154 A371155 * A371157 A371158 A371159

Keyword

nonn

Author

Chai Wah Wu, Apr 10 2024

Status

approved