A246849 -id:A246849 - cp's OEIS frontend

A143301 Decimal expansion of the Hall-Montgomery constant.

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

Offset: 0

Eric W. Weisstein, Aug 05 2008

Named after Richard Roxby Hall and Hugh Lowell Montgomery. - Amiram Eldar, Aug 25 2020

			0.17150049314153606586...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, pp. 205-207.

Thomas Bloom, Problem 121, Erdős Problems.
Andrew Granville and Kannan Soundararajan, The spectrum of multiplicative functions, Annals of Mathematics, Vol. 153, No. 2 (2001), pp. 407-470.
R. R. Hall, Proof of a conjecture of Heath-Brown concerning quadratic residues, Proceedings of the Edinburgh Mathematical Society, Vol. 39, No. 3 (1996), pp. 581-588.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024. See page 2, (1.2).
Terence Tao, Erdős problem database, see no. 121.
Eric Weisstein's World of Mathematics, Hall-Montgomery Constant.

Cf. A126689, A246849.

RealDigits[1+Pi^2/6+2PolyLog[2,-Sqrt[E]],10,120][[1]] (* Harvey P. Dale, Jul 18 2013 *)

from mpmath import mp, pi, e, polylog, sqrt
mp.dps=106
print([int(z) for z in list(str(1 + pi**2/6 + 2* polylog(2, - sqrt(e)))[2:-1])]) # Indranil Ghosh, Jul 04 2017

Equals 1 + Pi^2/6 + 2*PolyLog(2, -sqrt(e)).
Equals (1 - A126689)/2. - Amiram Eldar, Aug 25 2020
Equals 1 - A246849. - Hugo Pfoertner, May 25 2024

A373114 Cardinality of the largest subset of {1,...,n} such that no odd number of terms from this subset multiply to a square.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16, 17, 18, 19, 19, 20, 20, 20, 21, 21, 21, 22, 23, 23, 24, 25, 26, 27, 28, 29, 30, 31, 31, 31, 31, 32, 33, 34, 34, 34, 35, 36, 37, 38, 39, 40, 41, 42, 42, 42, 43, 44, 45, 46, 46, 47

Offset: 1

Terence Tao, May 25 2024

			For n=6, {2,3,5} is the largest set without an odd product being a square, so a(6)=3.

Martin Ehrenstein, Table of n, a(n) for n = 1..550 (terms 72..181 calculated from A360659)
Thomas Bloom, Problem 121, Erdős Problems.
Andrew Granville and K. Soundararajan, The spectrum of multiplicative functions, Ann. Math. 153 (2001), 407-470; preprint, arXiv:math/9909190 [math.NT], 1999.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.
Terence Tao, Erdős problem database, see no. 121.

Closely related to A360659, A372306, A373119, A373178, A373195.

Cf. A055038, A246849.

F(n, b)={vector(n, k, my(f=factor(k)); prod(i=1, #f~, if(bittest(b, primepi(f[i, 1])-1), 1, -1)^f[i, 2]))}
a(n)={my(m=oo); for(b=0, 2^primepi(n)-1, m=min(m, vecsum(F(n, b)))); (n-m)/2} \\ adapted from Andrew Howroyd, Feb 16 2023 at A360659 by David A. Corneth, May 25 2024

import itertools
import sympy
def generate_all_completely_multiplicative_functions(primes):
    combinations = list(itertools.product([-1, 1], repeat=len(primes)))
    functions = []
    for combination in combinations:
        func = dict(zip(primes, combination))
        functions.append(func)
    return functions
def evaluate_function(f, n):
    if n == 1:
        return 1
    factors = sympy.factorint(n)
    value = 1
    for prime, exp in factors.items():
        value *= f[prime] ** exp
    return value
def compute_minimum_sum(N: int):
    primes = list(sympy.primerange(1, N + 1))
    functions = generate_all_completely_multiplicative_functions(primes)
    min_sum = float("inf")
    for func in functions:
        total_sum = 0
        for n in range(1, N + 1):
            total_sum += evaluate_function(func, n)
        if total_sum < min_sum:
            min_sum = total_sum
    return min_sum
results = [(N - compute_minimum_sum(N)) // 2 for N in range(1, 12)]
print(", ".join(map(str, results)))

from itertools import product
from sympy import primerange, primepi, factorint
def A373114(n):
    a = dict(zip(primerange(n+1),range(c:=primepi(n))))
    return n-min(sum(sum(e for p,e in factorint(m).items() if b[a[p]])&1^1 for m in range(1,n+1)) for b in product((0,1),repeat=c)) # Chai Wah Wu, May 31 2024

n-2*a(n) = A360659(n) (see Footnote 2 of the linked paper of Tao).
Asymptotically, a(n)/n converges to log(1+sqrt(e)) - 2*Integral_{t=1..sqrt(e)} log(t)/(t+1) dt = A246849 ~ 0.828499... (essentially due to Granville and Soundararajan).
a(n+1)-a(n) is either 0 or 1 for any n.
a(n) >= A055038(n).

More terms from David A. Corneth, May 25 2024 using b-file from A360659 and formula n-2*a(n) = A360659(n)

A373178 Cardinality of the largest subset of {1,...,n} such that no five distinct elements of this subset multiply to a square.

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9, 10, 10, 10, 11, 11, 12, 12, 13, 13, 14, 15, 15, 16, 17, 18, 19, 19, 20, 20, 20, 21, 21, 21, 22, 23, 23, 24, 25, 26, 27, 28, 29, 30, 31, 31, 31, 31, 32, 33, 34, 34, 34, 35, 36, 37, 38, 39, 40, 41, 42, 42, 42, 43, 44, 45, 46, 46

Offset: 1

Terence Tao, May 26 2024

a(n) >= A373114(n).
The limiting value of a(n)/n is unknown, but (if it exists), it is strictly less than 1, and at least A246849 ~ 0.828499... (see cited paper of Tao).
a(n+1)-a(n) is either 0 or 1 for any n.
If "five" is replaced by "one", "two", "three", "four", or "odd number of", one obtains A028391, A013928, A372306, A373119, A373114 respectively.

			a(8)=7, because the set {1,2,3,4,5,7,8} has no five distinct elements multiplying to a square, but {1,2,3,4,5,6,7,8} has 1*2*3*4*6 = 12^2.

Thomas Bloom, Problem 121, Erdős Problems.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.
Terence Tao, Erdős problem database, see no. 121.

Similar to A028391, A013928, A372306, A373119. Lower bounded by A373114.

from math import isqrt
def is_square(n):
    return isqrt(n) ** 2 == n
def precompute_tuples(N):
    tuples = []
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            for k in range(j + 1, N + 1):
                for l in range(k + 1, N + 1):
                    for m in range(l + 1, N + 1):
                        if is_square(i * j * k * l * m):
                            tuples.append((i, j, k, l, m))
    return tuples
def valid_subset(A, tuples):
    set_A = set(A)
    for i, j, k, l, m in tuples:
        if i in set_A and j in set_A and k in set_A and l in set_A and m in set_A:
            return False
    return True
def largest_subset_size(N, tuples):
    from itertools import combinations
    for size in reversed(range(1, N + 1)):
        for subset in combinations(range(1, N + 1), size):
            if valid_subset(subset, tuples):
                return size
for N in range(1, 26):
    print(largest_subset_size(N, precompute_tuples(N)))

from math import prod
from functools import lru_cache
from itertools import combinations
from sympy.ntheory.primetest import is_square
@lru_cache(maxsize=None)
def A373178(n):
    if n==1: return 1
    i = A373178(n-1)+1
    if sum(1 for p in combinations(range(1,n),4) if is_square(n*prod(p))) > 0:
        a = [set(p) for p in combinations(range(1,n+1),5) if is_square(prod(p))]
        for q in combinations(range(1,n),i-1):
            t = set(q)|{n}
            if not any(s<=t for s in a):
                return i
        else:
            return i-1
    else:
        return i # Chai Wah Wu, May 30 2024

a(26)-a(38) from Michael S. Branicky, May 27 2024
a(39)-a(47) from Michael S. Branicky, May 30 2024
a(48)-a(70) from Martin Ehrenstein, May 31 2024

A246848 Decimal expansion of 1/(1+sqrt(e)), a constant appearing in the computation of a limiting probability concerning the number of cycles of a given length in a random permutation.

Original entry on oeis.org

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

Offset: 0

Jean-François Alcover, Sep 05 2014

1/(1+sqrt(e)) is the value of x that maximizes the expression Pi^2/6 - log(x) - log(x)^2 - 2*Li_2(x), where Li_2 is the dilogarithm function.

			0.37754066879814543536109943425449152124672063469108983694...

Steven R. Finch, Errata and Addenda to Mathematical Constants, p. 29.
Michael Lugo, The number of cycles of specified normalized length in permutations, arXiv:0909.2909 [math.CO]

Cf. A143301, A246849.

RealDigits[1/(1 + Sqrt[E]), 10, 101] // First

1/(1+sqrt(exp(1))) \\ Michel Marcus, Sep 05 2014

A248080 Decimal expansion of P_0(xi), the maximum limiting probability that a random n-permutation has no cycle exceeding a given length.

Original entry on oeis.org

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

Offset: 0

Jean-François Alcover, Oct 14 2014

			0.098711754480714692493721308237020679933333354780844...

Steven R. Finch, Errata and Addenda to Mathematical Constants, arXiv:2001.00578 [math.HO], 2020, p. 29.
Michael Lugo, The number of cycles of specified normalized length in permutations, arXiv:0909.2909 [math.CO], 2009.

Cf. A143301, A246849.

xi = 1/(1 + Sqrt[E]); P0[x_] := Log[x]^2/2 + Log[x] + PolyLog[2, x] - Pi^2/12 + 1; Join[{0}, RealDigits[P0[xi], 10, 101] // First]

from mpmath import *
mp.dps=102
xi=1/(1 + sqrt(e))
C = log(xi)**2/2 + log(xi) + polylog(2, xi) - pi**2/12 + 1
print([int(n) for n in list(str(C)[2:-1])]) # Indranil Ghosh, Jul 04 2017

(1/2)*log(1 + sqrt(e))^2 - log(1 + sqrt(e)) + Li_2(1/(1 + sqrt(e))) - Pi^2/12 + 1.

A248791 Decimal expansion of P_2(xi), the maximum limiting probability that a random n-permutation has exactly two cycles exceeding a given length.

Original entry on oeis.org

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

Offset: 0

Jean-François Alcover, Oct 14 2014

			0.0727887386608213733667186633181914296889295494487...

Steven R. Finch, Errata and Addenda to Mathematical Constants, arXiv:2001.00578 [math.HO], 2020, p. 29.
Michael Lugo, The number of cycles of specified normalized length in permutations, arXiv:0909.2909 [math.CO] 2009.

Cf. A143301, A246849, A248080.

xi = 1/(1 + Sqrt[E]); P2[x_] := -Pi^2/12 + (1/2)*Log[x]^2 + PolyLog[2, x]; Join[{0}, RealDigits[P2[xi], 10, 100] // First]

from mpmath import *
mp.dps=101
xi=1/(1 + sqrt(e))
C = -pi**2/12 + (1/2)*log(xi)**2 + polylog(2, xi)
print([int(n) for n in list(str(C)[2:-1])]) # Indranil Ghosh, Jul 03 2017

-Pi^2/12 + (1/2)*log(1 + sqrt(e))^2 + Li_2(1/(1 + sqrt(e))).

cp's OEIS Frontend

A143301 Decimal expansion of the Hall-Montgomery constant.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

A373114 Cardinality of the largest subset of {1,...,n} such that no odd number of terms from this subset multiply to a square.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Python

Formula

Extensions

A373178 Cardinality of the largest subset of {1,...,n} such that no five distinct elements of this subset multiply to a square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Extensions

A246848 Decimal expansion of 1/(1+sqrt(e)), a constant appearing in the computation of a limiting probability concerning the number of cycles of a given length in a random permutation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A248080 Decimal expansion of P_0(xi), the maximum limiting probability that a random n-permutation has no cycle exceeding a given length.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A248791 Decimal expansion of P_2(xi), the maximum limiting probability that a random n-permutation has exactly two cycles exceeding a given length.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula