cp's OEIS Frontend

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

%I A371156 #49 Mar 09 2025 13:54:11
%S A371156 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 A371156 17,18,18,19,19,19,20,21,21,22,22,22,22,23,23,24,24,24,25,26,26,27,27,
%U A371156 27,27,28,28,29,29,29,29,30,30,31,31,31,32,33,33,34,34,34
%N A371156 Length of the longest subsequence of 1, ..., n on which the Dedekind psi function (A001615) is nondecreasing.
%C A371156 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 A371156 Chai Wah Wu, <a href="/A371156/b371156.txt">Table of n, a(n) for n = 1..10000</a>
%H A371156 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 A371156 0 <= a(n+1) - a(n) <= 1.
%F A371156 a(n) >= A000720(n)+1 since A001615(p) = p+1 for p prime.
%e A371156 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.
%t A371156 Length[LongestOrderedSequence[#]] & /@ Rest[FoldList[Append, {}, Table[n DivisorSum[n, MoebiusMu[#]^2/# &], {n, 20}]]] (* _Eric W. Weisstein_, Mar 09 2025 *)
%o A371156 (Python)
%o A371156 from math import prod
%o A371156 from bisect import bisect
%o A371156 from sympy import primefactors
%o A371156 def A371156(n):
%o A371156     def f(n):
%o A371156         r = primefactors(n)
%o A371156         return n*prod(p+1 for p in r)//prod(r)
%o A371156     plist, qlist, c = tuple(f(i) for i in range(1,n+1)), [0]*(n+1), 0
%o A371156     for i in range(n):
%o A371156         qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
%o A371156         c = max(c,a)
%o A371156     return c
%Y A371156 Cf. A000720, A001615, A365339, A365399, A365397, A365398, A365740.
%K A371156 nonn
%O A371156 1,2
%A A371156 _Chai Wah Wu_, Apr 10 2024