A365737 -id:A365737 - cp's OEIS frontend

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

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. 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

A365740 Length of the longest subsequence of {m: 1<=m<=n, m not prime} on which the Euler totient function phi A000010 is nondecreasing.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 6, 7, 8, 9, 9, 9, 9, 10, 11, 11, 11, 11, 12, 12, 13, 13, 13, 13, 13, 14, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 22, 23, 23, 24, 24, 24, 24, 25, 25

Offset: 1

Chai Wah Wu, Sep 17 2023

nonn

Chai Wah Wu, 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 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.

from bisect import bisect
from sympy import totient, isprime
def A365740(n):
    plist = tuple(totient(i) for i in range(1,n+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

Pollack et al. conjectured that a(n) < A365339(n)-2 for all n >= 31957.

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

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

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.

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A365740 Length of the longest subsequence of {m: 1<=m<=n, m not prime} on which the Euler totient function phi A000010 is nondecreasing.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

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

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

Views

Author

Keywords

Comments

Links

Crossrefs