login
a(n) = 64 + A000720(n) - A365339(n).
10

%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