cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 6, 6, 6, 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
Offset: 1

Views

Author

Terence Tao, May 25 2024

Keywords

Comments

a(n) >= A373114(n).
a(n) ~ n (Erdős-Sárközy-Sós).
a(n+1)-a(n) is either 0 or 1 for any n.
If "three" is replaced by "two" one obtains A013928. If "three" is replaced by "one", one obtains A028391. If "three" is replaced by "any odd", one obtains A373114.

Examples

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

Links

Crossrefs

Cf. A013928, A028391, A373114, A373119, A373178, A373195.

Programs

  • PARI
    \\ See PARI link
  • Python
    from math import isqrt
def is_square(n):
    return isqrt(n) ** 2 == n
def valid_subset(A):
    length = len(A)
    for i in range(length):
        for j in range(i + 1, length):
            for k in range(j + 1, length):
                if is_square(A[i] * A[j] * A[k]):
                    return False
    return True
def largest_subset_size(N):
    from itertools import combinations
    max_size = 0
    for size in range(1, N + 1):
        for subset in combinations(range(1, N + 1), size):
            if valid_subset(subset):
                max_size = max(max_size, size)
    return max_size
for N in range(1, 11):
    print(largest_subset_size(N))
  • Python
    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 A372306(n):
    if n==1: return 1
    i = A372306(n-1)+1
    if sum(1 for p in combinations(range(1,n),2) if is_square(n*prod(p))) > 0:
        a = [set(p) for p in combinations(range(1,n+1),3) 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

Formula

From David A. Corneth, May 29 2024: (Start)
a(k^2) = a(k^2 - 1) for k >= 3.
a(p) = a(p - 1) + 1 for prime p. (End)

Extensions

a(18)-a(36) from Michael S. Branicky, May 25 2024
a(37)-a(38) from Michael S. Branicky, May 26 2024
a(39)-a(63) from Martin Ehrenstein, May 26 2024
a(64)-a(76) from David A. Corneth, May 29 2024, May 30 2024

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

Original entry on oeis.org

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

Views

Author

Terence Tao, May 26 2024

Keywords

Comments

a(n) >= A000720(n).
a(n) ~ n/log n (Erdős-Sárközy-Sós). Best bounds currently are due to Pach-Vizer.
a(n+1)-a(n) is either 0 or 1 for any n. (Is equal to 1 when n+1 is prime.)
If "four" is replaced by "one", "two", "three", "five", or "any odd", one obtains A028391, A013928, A372306, A373178, and A373114 respectively.

Examples

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

Links

Crossrefs

Cf. A028391, A013928, A372306, A373114, A373178, A373195.
Lower bounded by A000720.

Programs

  • Python
    from math import isqrt
def is_square(n):
    return isqrt(n) ** 2 == n
def valid_subset(A):
    length = len(A)
    for i in range(length):
        for j in range(i + 1, length):
            for k in range(j + 1, length):
                for l in range(k + 1, length):
                    if is_square(A[i] * A[j] * A[k] * A[l]):
                        return False
    return True
def largest_subset_size(N):
    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):
                return size
for N in range(1, 23):
    print(largest_subset_size(N))
  • Python
    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 A373119(n):
    if n==1: return 1
    i = A373119(n-1)+1
    if sum(1 for p in combinations(range(1,n),3) if is_square(n*prod(p))) > 0:
        a = [set(p) for p in combinations(range(1,n+1),4) 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

Extensions

a(22)-a(37) from Michael S. Branicky, May 26 2024
a(38)-a(63) from Martin Ehrenstein, May 27 2024
a(64)-a(69) from Jinyuan Wang, Dec 30 2024

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

Views

Author

Terence Tao, May 26 2024

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

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

Programs

  • Python
    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)))
  • Python
    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

Extensions

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

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

Original entry on oeis.org

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

Views

Author

Terence Tao, May 27 2024

Keywords

Comments

a(n) >= A000720(n) + A000720(n/2).
a(n) ~ 3n/2log n (Erdős-Sárközy-Sós). Best bounds currently are due to Pach-Vizer.
a(n+1)-a(n) is either 0 or 1 for any n. (Is equal to 1 when n+1 is prime.)
If "six" is replaced by "one", "two", "three", "four", "five", or "any odd", one obtains A028391, A013928, A372306, A373119, A373178, and A373114 respectively.

Examples

			a(9)=8, because {1,2,3,4,5,7,8,9} does not contain six distinct elements that multiply to a square, but {1,2,3,4,5,6,7,8,9} has 1*2*3*4*6*9 = 36^2.

Links

Crossrefs

Similar to A013928, A028391, A372306, A373114, A373119, A373178.
Cf. A000720.

Programs

  • Python
    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):
                        for n in range(m + 1, N + 1):
                            if is_square(i * j * k * l * m * n):
                                tuples.append((i, j, k, l, m, n))
    return tuples
def valid_subset(A, tuples):
    set_A = set(A)
    for i, j, k, l, m, n 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 and n 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)))
  • Python
    from math import prod
from itertools import combinations
from functools import lru_cache
from sympy.ntheory.primetest import is_square
@lru_cache(maxsize=None)
def A373195(n):
    if n==1: return 1
    i = A373195(n-1)+1
    if sum(1 for p in combinations(range(1,n),5) if is_square(n*prod(p))) > 0:
        a = [set(p) for p in combinations(range(1,n+1),6) 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

Formula

From David A. Corneth, May 29 2024: (Start)
a(p) = a(p-1) + 1 for prime p.
a(k^2) = a(k^2 - 1) for k >= 3. (End)

Extensions

a(26)-a(27) from Paul Muljadi, May 28 2024
a(28)-a(35) from Michael S. Branicky, May 29 2024
a(36)-a(37) from David A. Corneth, May 29 2024
a(38)-a(69) from Jinyuan Wang, Dec 30 2024
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.