%I #11 Sep 06 2023 18:09:22
%S 63,63,63,62,62,62,62,62,61,61,61,61,61,61,60,59,59,59,59,59,59,59,59,
%T 59,59,59,58,58,58,58,58,58,58,58,57,57,57,57,57,57,57,57,57,57,57,57,
%U 57,57,57,57,57,57,57,57,57,57,57,57,57,57,57,57,57,57,56
%N a(n) = 64 + A000720(n) - A365339(n).
%C It is conjectured that A365339(n) = PrimePi(n) + 64 for all n >= 31957 (Pollack et al.). Assuming this conjecture a(n) = 0 for n > 31956.
%C a is not monotonically decreasing.
%H 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 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, pp. 379-398.
%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.
%o (Julia) # Computes the first N terms of the sequence.
%o using Nemo
%o function A365400List(N)
%o phi = Int64[i for i in 1:N + 1]
%o for i in 2:N + 1
%o if phi[i] == i
%o for j in i:i:N + 1
%o phi[j] -= div(phi[j], i)
%o end end end
%o lst = zeros(Int64, N)
%o dyn = zeros(Int64, N)
%o pi = 64
%o for n in 1:N
%o p = phi[n]
%o nxt = dyn[p] + 1
%o while p <= N && dyn[p] < nxt
%o dyn[p] = nxt
%o p += 1
%o end
%o pi += is_prime(n) ? 1 : 0
%o lst[n] = pi - dyn[n]
%o end
%o return lst
%o end
%o println(A365400List(32000))
%o (Python)
%o from bisect import bisect
%o from sympy import totient, primepi
%o def A365400(n):
%o plist, qlist, c = tuple(totient(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 64+primepi(n)-c # _Chai Wah Wu_, Sep 06 2023
%Y Cf. A000720, A365339, A365474.
%K nonn
%O 1,1
%A _Peter Luschny_, Sep 06 2023