|
%I #53 Dec 08 2023 10:32:49
%S 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 15,16,16,17,17,17,17,18,18,19,19,19,19,20,20,21,21,21,21,22,22,22,22,
%U 22,22,23,23,23,23,23,23,24,24,25,25,25,25,26,26,27,27,27
%N Length of the longest subsequence of 1,...,n on which the Euler totient function phi A000010 is nondecreasing.
%C a(n+1) is equal to a(n) or a(n) + 1 for every n.
%C 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 Conjecture is true for n = 10^8 and n = 10^9. - _Chai Wah Wu_, Sep 05 2023
%H Alois P. Heinz, <a href="/A365339/b365339.txt">Table of n, a(n) for n = 1..10000</a>
%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, 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.
%F Tao proves that a(n) ~ n/log n. a(n) >= pi(n) + 64 for all n >= 31957; conjecturally this is an equality. - _Charles R Greathouse IV_, Dec 08 2023
%e 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 Table[Length[LongestOrderedSequence[Table[EulerPhi[i],{i,n}]]], {n,100}]
%o (Python)
%o import math
%o def phi(n):
%o result = n
%o for i in range(2, math.isqrt(n) + 1):
%o if n % i == 0:
%o while n % i == 0:
%o n //= i
%o result -= result // i
%o if n > 1:
%o result -= result // n
%o return result
%o # This code uses dynamic programming to print the first N=100 values of M.
%o N=100
%o M = [0 for i in range(N)]
%o dynamic = [0 for i in range(N+1)]
%o for n in range(1,N+1):
%o i = phi(n)
%o new = dynamic[i] + 1
%o while (i<=N and dynamic[i] < new):
%o dynamic[i] = new
%o i+= 1
%o M[n-1] = dynamic[N]
%o print(M)
%o (Python)
%o from bisect import bisect
%o from sympy import totient
%o def A365339(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 c # _Chai Wah Wu_, Sep 03 2023
%o (Julia) # Computes the first N terms of the sequence.
%o function A365339List(N)
%o phi = [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 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 lst[n] = dyn[n]
%o end
%o return lst
%o end
%o println(A365339List(69)) # _Peter Luschny_, Sep 02 2023
%Y Cf. A000010, A000720.
%Y Cf. A365398, A365399, A365400, A365474, A061070.
%K nonn,easy
%O 1,2
%A _Terence Tao_, Sep 01 2023
|
