OFFSET
1,2
COMMENTS
a(n+1) is equal to a(n) or a(n) + 1 for every n.
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).
Conjecture is true for n = 10^8 and n = 10^9. - Chai Wah Wu, Sep 05 2023
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..10000
Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M(n).
Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, Ramanujan J. 30 (2013), no. 3, 379--398.
Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023.
FORMULA
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
EXAMPLE
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.
MATHEMATICA
Table[Length[LongestOrderedSequence[Table[EulerPhi[i], {i, n}]]], {n, 100}]
PROG
(Python)
import math
def phi(n):
result = n
for i in range(2, math.isqrt(n) + 1):
if n % i == 0:
while n % i == 0:
n //= i
result -= result // i
if n > 1:
result -= result // n
return result
# This code uses dynamic programming to print the first N=100 values of M.
N=100
M = [0 for i in range(N)]
dynamic = [0 for i in range(N+1)]
for n in range(1, N+1):
i = phi(n)
new = dynamic[i] + 1
while (i<=N and dynamic[i] < new):
dynamic[i] = new
i+= 1
M[n-1] = dynamic[N]
print(M)
(Python)
from bisect import bisect
from sympy import totient
def A365339(n):
plist, qlist, c = tuple(totient(i) for i in range(1, n+1)), [0]*(n+1), 0
for i in range(n):
qlist[a:=bisect(qlist, plist[i], lo=1, hi=c+1, key=lambda x:plist[x])]=i
c = max(c, a)
return c # Chai Wah Wu, Sep 03 2023
(Julia) # Computes the first N terms of the sequence.
function A365339List(N)
phi = [i for i in 1:N + 1]
for i in 2:N + 1
if phi[i] == i
for j in i:i:N + 1
phi[j] -= div(phi[j], i)
end end end
lst = zeros(Int64, N)
dyn = zeros(Int64, N)
for n in 1:N
p = phi[n]
nxt = dyn[p] + 1
while p <= N && dyn[p] < nxt
dyn[p] = nxt
p += 1
end
lst[n] = dyn[n]
end
return lst
end
println(A365339List(69)) # Peter Luschny, Sep 02 2023
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Terence Tao, Sep 01 2023
STATUS
approved