A028391 -id:A028391 - cp's OEIS frontend

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

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

A056847 Nearest integer to n - sqrt(n).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Dec 07 2000

nonn

B. Alspach, K. Heinrich and G. Liu, Orthogonal factorizations of graphs, pp. 13-40 of Contemporary Design Theory, ed. J. H. Dinizt and D. R. Stinson, Wiley, 1992 (see Theorem 2.7).

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A000194, A028391.

[n-Floor(Sqrt(n)+1/2):n in [0..80]]; // Marius A. Burtea, May 13 2019

0,seq(seq(n-k, n=k^2-k+1..k^2+k),k=1..10); # Robert Israel, Jun 13 2018

Table[Round[n-Sqrt[n]],{n,0,70}] (* Harvey P. Dale, Jun 15 2014 *)

a(n) = round(n - sqrt(n)); \\ Michel Marcus, May 13 2019

from math import isqrt
def A056847(n): return n-(m:=isqrt(n))-int(n>m*(m+1)) # Chai Wah Wu, Jun 05 2025

From Robert Israel, Jun 13 2018: (Start)
a(n) = n-k for k^2-k+1 <= n <= k^2+k, k >= 1.
G.f.: x/(1-x)^2 - Theta_2(0,x)*x^(3/4)/(2*(1-x)) where Theta_2 is a Jacobi theta function. (End)
a(n) = n - floor(sqrt(n) + 1/2) = n - A000194(n). - Ridouane Oudra, May 13 2019

A135675 a(n) = ceiling(n^(4/3) - n).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 18, 20, 22, 25, 27, 30, 32, 35, 37, 40, 43, 46, 49, 52, 54, 58, 61, 64, 67, 70, 73, 77, 80, 83, 87, 90, 94, 97, 101, 104, 108, 112, 116, 119, 123, 127, 131, 135, 139, 143, 147, 151, 155

Offset: 1

Mohammad K. Azarian, Dec 01 2007

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A135660, A135661, A135662, A135663, A135664, A135665, A028391, A135668, A135671, A135672, A135673, A135674.

[Ceiling(n^(4/3) - n): n in [1..100]]; // Vincenzo Librandi, Feb 16 2013

Table[Ceiling[n^(4/3) - n], {n, 100}] (* Vincenzo Librandi, Feb 16 2013 *)

Offset corrected by Mohammad K. Azarian, Nov 19 2008

A173517 a(n) = k if n is the k-th nonsquare, zero otherwise.

Original entry on oeis.org

0, 0, 1, 2, 0, 3, 4, 5, 6, 0, 7, 8, 9, 10, 11, 12, 0, 13, 14, 15, 16, 17, 18, 19, 20, 0, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 0, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 0, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 0, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67

Offset: 0

Reinhard Zumkeller, Feb 20 2010

a(A000037(n)) = n; a(A000290(n)) = 0.

a(n)*A037213(n) = 0 for all n.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

Cf. A000037, A000196, A000290, A010052, A028391, A037213.

a173517 n = (1 - a010052 n) * a028391 n
-- Reinhard Zumkeller, Dec 15 2013

a(n)=if(issquare(n), 0, n-sqrtint(n)) \\ Charles R Greathouse IV, Sep 02 2015

a(n) = (1 - A010052(n))*A028391(n).

Definition revised by Reinhard Zumkeller, Dec 15 2013, at the suggestion of Antti Karttunen, who further edited the name

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

Terence Tao, May 27 2024

nonn

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.

			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.

P. Erdős, A. Sárközy, and V. T. Sós, On Product Representations of Powers, I, Europ. J. Combinatorics 16 (1995), 567-588.
P. Pach and M. Vizer, Improved Lower Bounds for Multiplicative Square-Free Sequences, The Electronic Journal of Combinatorics, Volume 30, Issue 4 (2023), P4.31.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.

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

Cf. A000720.

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

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

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)

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

A135676 a(n) = floor(n^(4/3) - n).

Original entry on oeis.org

0, 0, 1, 2, 3, 4, 6, 8, 9, 11, 13, 15, 17, 19, 21, 24, 26, 29, 31, 34, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 76, 79, 82, 86, 89, 93, 96, 100, 103, 107, 111, 115, 118, 122, 126, 130, 134, 138, 142, 146, 150, 154, 158

Offset: 1

Mohammad K. Azarian, Dec 01 2007

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A135660, A135661, A135662, A135663, A135664, A135665, A028391, A135668, A135671, A135672, A135673, A135674, A135675.

[Floor(n^(4/3)-n): n in [1..100]]; // Vincenzo Librandi, Feb 18 2013

Table[Floor[n^(4/3) - n], {n, 100}] (* Vincenzo Librandi, Feb 18 2013 *)

a(n)=sqrtnint(n^4,3)-n \\ Charles R Greathouse IV, Feb 07 2025

Offset corrected by Mohammad K. Azarian, Nov 19 2008

A037458 a(1)=1; for n > 1, a(n) = n - a(n-floor(sqrt(n))).

Original entry on oeis.org

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

Offset: 1

Benoit Cloitre, Dec 22 2002

nonn

Cf. A028391, A053615.

PARI
```
a(n)=if(n<2,1,n-a(n-sqrtint(n)))
```

a(n) = (1/2)*(n + A053615(n)).

Corrected by Franklin T. Adams-Watters, Oct 25 2006

A065651 a(n) = Sum_{k=1..n} (-1)^tau(k) = n - 2*floor(sqrt(n)).

Original entry on oeis.org

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

Offset: 2

Vladeta Jovovic, Dec 03 2001

Harry J. Smith, Table of n, a(n) for n = 2..1000

Cf. A000005 (tau), A000196, A028391, A028392.

Table[n-2*Floor[Sqrt[n]],{n,2,80}] (* Harvey P. Dale, Jul 27 2012 *)

a(n) = n - 2*sqrtint(n); \\ Harry J. Smith, Oct 25 2009

import math
def a(n): return n - 2 * math.isqrt(n) # Darío Clavijo, Apr 23 2023

A112045 Positions of primes (A000040) among nonsquares A000037.

Original entry on oeis.org

1, 2, 3, 5, 8, 10, 13, 15, 19, 24, 26, 31, 35, 37, 41, 46, 52, 54, 59, 63, 65, 71, 74, 80, 88, 91, 93, 97, 99, 103, 116, 120, 126, 128, 137, 139, 145, 151, 155, 160, 166, 168, 178, 180, 183, 185, 197, 209, 212, 214, 218, 224, 226, 236, 241, 247, 253, 255, 261

Offset: 1

Antti Karttunen, Aug 27 2005

nonn

Also: Distance of prime(n) from the integer part of its square root. - M. F. Hasler, Oct 19 2018

Cf. A000037, A000040, A028391, A071403 (the original name describes this sequence).

f[n_]:=n-IntegerPart[Sqrt[n]]; lst={};Do[p=Prime[n];AppendTo[lst,f[p]],{n,5!}];lst (* Vladimir Joseph Stephan Orlovsky, Jul 24 2009 *)

apply( A112045=n->(n=prime(n))-sqrtint(n), [1..200]) \\ M. F. Hasler, Oct 19 2018

from math import isqrt
from sympy import prime
def A112045(n): return (p:=prime(n))-isqrt(p) # Chai Wah Wu, Jun 05 2025

a(n) = A028391(A000040(n)), where A028391(x) = x - floor(sqrt(x)).

a(n) ~ 6/Pi^2 * n log n. - Charles R Greathouse IV, May 29 2013

Erroneous name corrected by Antti Karttunen, Jun 03 2014

A135677 a(n) = ceiling(n^(4/3)+n).

Original entry on oeis.org

2, 5, 8, 11, 14, 17, 21, 24, 28, 32, 36, 40, 44, 48, 52, 57, 61, 66, 70, 75, 79, 84, 89, 94, 99, 104, 108, 114, 119, 124, 129, 134, 139, 145, 150, 155, 161, 166, 172, 177, 183, 188, 194, 200, 206, 211, 217, 223, 229, 235, 241

Offset: 1

Mohammad K. Azarian, Dec 01 2007

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A135660, A135661, A135662, A135663, A135664, A135665, A028391, A135668, A135671, A135672, A135673, A135674, A135675, A135676.

[Ceiling(n^(4/3)+n): n in [1..100]]; // Vincenzo Librandi, Feb 16 2013

Table[Ceiling[n^(4/3) + n], {n, 100}] (* Vincenzo Librandi, Feb 16 2013 *)

cp's OEIS Frontend

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

A056847 Nearest integer to n - sqrt(n).

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A135675 a(n) = ceiling(n^(4/3) - n).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Extensions

A173517 a(n) = k if n is the k-th nonsquare, zero otherwise.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula

Extensions

A135676 a(n) = floor(n^(4/3) - n).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A037458 a(1)=1; for n > 1, a(n) = n - a(n-floor(sqrt(n))).

Views

Author

Keywords

Crossrefs

Programs

PARI