This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A365339 #55 Oct 01 2024 08:32:33
%S A365339 1,2,3,4,5,5,6,6,7,7,8,8,9,9,10,11,12,12,13,13,13,13,14,14,14,14,15,
%T A365339 15,16,16,17,17,17,17,18,18,19,19,19,19,20,20,21,21,21,21,22,22,22,22,
%U A365339 22,22,23,23,23,23,23,23,24,24,25,25,25,25,26,26,27,27,27
%N A365339 Length of the longest subsequence of 1,...,n on which the Euler totient function phi A000010 is nondecreasing.
%C A365339 a(n+1) is equal to a(n) or a(n) + 1 for every n.
%C A365339 It is conjectured that a(n) = pi(n) + 64 for all n >= 31957, which has been verified up to n = 10^7 (Pollack et al.), where pi is A000720. We always have a(n) >= pi(n).
%C A365339 Conjecture is true for n = 10^8 and n = 10^9. - _Chai Wah Wu_, Sep 05 2023
%H A365339 Alois P. Heinz, <a href="/A365339/b365339.txt">Table of n, a(n) for n = 1..10000</a>
%H A365339 Paul Pollack, Carl Pomerance and Enrique Treviño, <a href="https://math.dartmouth.edu/~carlp/MonotonePhi.pdf">Sets of monotonicity for Euler's totient function</a>, preprint. See M(n).
%H A365339 Paul Pollack, Carl Pomerance and Enrique Treviño, <a href="https://doi.org/10.1007/s11139-012-9386-6">Sets of monotonicity for Euler's totient function</a>, Ramanujan J. 30 (2013), no. 3, 379--398.
%H A365339 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.
%F A365339 Tao proves that a(n) ~ n/log n. a(n) >= pi(n) + 64 for all n >= 31957; Pollack, Pomerance, & Treviño conjecture that this is an equality. - _Charles R Greathouse IV_, Dec 08 2023
%e A365339 a(6) = 5 because phi is nondecreasing on 1,2,3,4,5 or 1,2,3,4,6 but not on 1,2,3,4,5,6.
%t A365339 Table[Length[LongestOrderedSequence[Table[EulerPhi[i],{i,n}]]], {n,100}]
%o A365339 (Python)
%o A365339 import math
%o A365339 def phi(n):
%o A365339 result = n
%o A365339 for i in range(2, math.isqrt(n) + 1):
%o A365339 if n % i == 0:
%o A365339 while n % i == 0:
%o A365339 n //= i
%o A365339 result -= result // i
%o A365339 if n > 1:
%o A365339 result -= result // n
%o A365339 return result
%o A365339 # This code uses dynamic programming to print the first N=100 values of M.
%o A365339 N=100
%o A365339 M = [0 for i in range(N)]
%o A365339 dynamic = [0 for i in range(N+1)]
%o A365339 for n in range(1,N+1):
%o A365339 i = phi(n)
%o A365339 new = dynamic[i] + 1
%o A365339 while (i<=N and dynamic[i] < new):
%o A365339 dynamic[i] = new
%o A365339 i+= 1
%o A365339 M[n-1] = dynamic[N]
%o A365339 print(M)
%o A365339 (Python)
%o A365339 from bisect import bisect
%o A365339 from sympy import totient
%o A365339 def A365339(n):
%o A365339 plist, qlist, c = tuple(totient(i) for i in range(1,n+1)), [0]*(n+1), 0
%o A365339 for i in range(n):
%o A365339 qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
%o A365339 c = max(c,a)
%o A365339 return c # _Chai Wah Wu_, Sep 03 2023
%o A365339 (Julia) # Computes the first N terms of the sequence.
%o A365339 function A365339List(N)
%o A365339 phi = [i for i in 1:N + 1]
%o A365339 for i in 2:N + 1
%o A365339 if phi[i] == i
%o A365339 for j in i:i:N + 1
%o A365339 phi[j] -= div(phi[j], i)
%o A365339 end end end
%o A365339 lst = zeros(Int64, N)
%o A365339 dyn = zeros(Int64, N)
%o A365339 for n in 1:N
%o A365339 p = phi[n]
%o A365339 nxt = dyn[p] + 1
%o A365339 while p <= N && dyn[p] < nxt
%o A365339 dyn[p] = nxt
%o A365339 p += 1
%o A365339 end
%o A365339 lst[n] = dyn[n]
%o A365339 end
%o A365339 return lst
%o A365339 end
%o A365339 println(A365339List(69)) # _Peter Luschny_, Sep 02 2023
%Y A365339 Cf. A000010, A000720.
%Y A365339 Cf. A365398, A365399, A365400, A365474, A061070.
%K A365339 nonn,easy
%O A365339 1,2
%A A365339 _Terence Tao_, Sep 01 2023