A365740 -id:A365740 - cp's OEIS frontend

A365741 a(n) = A365740(10^n).

Original entry on oeis.org

1, 5, 31, 189, 1261, 9595, 77681, 654249, 5650472

Offset: 0

Chai Wah Wu, Sep 17 2023

Pollack et al. listed a(4)-a(6).

Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M2(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.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A365737, A365740, A365742, A061070.

from bisect import bisect
from sympy import totient
def A365741(n):
    k = 10**n
    plist = tuple(totient(i) for i in range(1,k+1) if not isprime(i))
    m = len(plist)
    qlist, c = [0]*(m+1), 0
    for i in range(m):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c

A365739 a(n)=A365339(10^n)-A365740(10^n).

Original entry on oeis.org

0, 2, 3, 4, 15, 61, 881, 10394, 111047

Offset: 0

Chai Wah Wu, Sep 17 2023

Pollack et al. conjectured that a(n) > 2 for n > 4.

Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M↑(n) and M2(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.

Cf. A000010, A000720.

Cf. A365339, A365398, A365399, A365400, A365474, A365737, A061070.

A365738 a(n) = A365737(10^n).

Original entry on oeis.org

1, 3, 12, 32, 92, 292, 995, 3029, 9651, 31817

Offset: 0

Chai Wah Wu, Sep 17 2023

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.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A365737, A365740, A365741, A061070.

from bisect import bisect
from sympy import totient
def A365738(n):
    k = 10**n
    plist, qlist, c = tuple(-totient(i) for i in range(1,k+1)), [0]*(k+1), 0
    for i in range(k):
        qlist[a:=bisect(qlist,plist[i],lo=1,hi=c+1,key=lambda x:plist[x])]=i
        c = max(c,a)
    return c

a(9) from Chai Wah Wu, Oct 13 2023

A365742 Length of the largest subset of 1,...,n on which the Euler totient function phi A000010 is constant.

Original entry on oeis.org

1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10

Offset: 1

Chai Wah Wu, Sep 17 2023

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..10000
R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331-361.
Paul Erdős, On the normal number of prime factors of p - 1 and some related problems concerning Euler’s phi-function, Quart J. Math 6 (1935), 205-213.
Paul Pollack, Carl Pomerance and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M0(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.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A365737, A365738, A365740, A365741, A061070.

from collections import Counter
from sympy import totient
def A365742(n): return max(Counter(totient(i) for i in range(1,n+1)).values())

Pollack et al. showed that A365737(n)-a(n) > n^0.18 for large n.

A365748 a(n) = A365742(10^n).

Original entry on oeis.org

1, 3, 10, 30, 72, 247, 937, 2844, 9261, 30742

Offset: 0

Chai Wah Wu, Sep 17 2023

R. Baker and G. Harman, Shifted primes without large prime factors, Acta Arithmetica 83 (1998), pp. 331-361.
Paul Pollack, Carl Pomerance, and Enrique Treviño, Sets of monotonicity for Euler's totient function, preprint. See M0(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.

Cf. A000010, A000720.

Cf. A365398, A365399, A365400, A365474, A365737, A365738, A365740, A365741, A365742, A061070.

from collections import Counter
from sympy import totient
def A365748(n): return max(Counter(totient(i) for i in range(1,10**n+1)).values())

Baker and Harman showed that a(n) >= 10^(0.7038n) for all large enough n. - Chai Wah Wu, Oct 17 2023

A371156 Length of the longest subsequence of 1, ..., n on which the Dedekind psi function (A001615) is nondecreasing.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 9, 10, 10, 11, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 17, 17, 18, 18, 19, 19, 19, 20, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 25, 26, 26, 27, 27, 27, 27, 28, 28, 29, 29, 29, 29, 30, 30, 31, 31, 31, 32, 33, 33, 34, 34, 34

Offset: 1

Chai Wah Wu, Apr 10 2024

nonn

The envelope max_{i<=n} (a(i)-A000720(i)) appears to be slowly increasing as n increases. For instance, a(1)-A000720(1)=1, whereas a(374598)-A000720(374598)=91 and a(642852)-A000720(642852)=96.

			a(7) = 6 because A001615 is nondecreasing on 1,2,3,4,5,6 or 1,2,3,4,5,7 but not on 1,2,3,4,5,6,7.

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Terence Tao, Monotone non-decreasing sequences of the Euler totient function, arXiv:2309.02325 [math.NT], 2023. See Remark 4.7.

Cf. A000720, A001615, A365339, A365399, A365397, A365398, A365740.

Length[LongestOrderedSequence[#]] & /@ Rest[FoldList[Append, {}, Table[n DivisorSum[n, MoebiusMu[#]^2/# &], {n, 20}]]] (* Eric W. Weisstein, Mar 09 2025 *)

from math import prod
from bisect import bisect
from sympy import primefactors
def A371156(n):
    def f(n):
        r = primefactors(n)
        return n*prod(p+1 for p in r)//prod(r)
    plist, qlist, c = tuple(f(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

0 <= a(n+1) - a(n) <= 1.

a(n) >= A000720(n)+1 since A001615(p) = p+1 for p prime.

cp's OEIS Frontend

A365741 a(n) = A365740(10^n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A365739 a(n)=A365339(10^n)-A365740(10^n).

Views

Author

Keywords

Comments

Links

Crossrefs

A365738 a(n) = A365737(10^n).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A365742 Length of the largest subset of 1,...,n on which the Euler totient function phi A000010 is constant.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A365748 a(n) = A365742(10^n).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A371156 Length of the longest subsequence of 1, ..., n on which the Dedekind psi function (A001615) is nondecreasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula