A028391 -id:A028391 - cp's OEIS frontend

A000196 Integer part of square root of n. Or, number of positive squares <= n. Or, n appears 2n+1 times.

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

Offset: 0

N. J. A. Sloane

Also the integer part of the geometric mean of the divisors of n. - Amarnath Murthy, Dec 19 2001
Number of numbers k (<= n) with an odd number of divisors. - Benoit Cloitre, Sep 07 2002
Also, for n > 0, the number of digits when writing n in base where place values are squares, cf. A007961; A190321(n) <= a(n). - Reinhard Zumkeller, May 08 2011
The least monotonic left inverse of squares, A000290. That is, the lexicographically least nondecreasing sequence a(n) such that a(A000290(n)) = n. - Antti Karttunen, Oct 06 2017

			G.f. = x + x^2 + x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 + 2*x^8 + 3*x^9 + ...

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 73, problem 23.
Lionel Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.
Paul J. McCarthy, Introduction to Arithmetical Functions, Springer Verlag, 1986, p. 28.
N. J. A. Sloane and Allan Wilks, On sequences of Recaman type, paper in preparation, 2006.

Franklin T. Adams-Watters, Table of n, a(n) for n = 0..10000
Krassimir Atanassov, On Some of Smarandache's Problems
Krassimir Atanassov, On the 100-th, the 101-st and 102-nd Smarandache's problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 3, 94-96.
Henry Bottomley, Illustration of A000196, A048760, A053186.
Matthew Hyatt and Marina Skyers, On the Increases of the Sequence floor(k*sqrt(n)), Electronic Journal of Combinatorial Number Theory, Volume 15 (2015), #A17.
Lionel Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Paul Pollack and Joseph Vandehey, Besicovitch, Bisection, and the Normality of 0.(1)(4)(9)(16)(25)...., The American Mathematical Monthly 122.8 (2015): 757-765.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Florentin Smarandache, Only Problems, Not Solutions!, 1993.

Cf. A000290, A002162, A003056, A028391, A048760, A048766, A074704, A079051.

Column k=1 of A281871.

import Data.Bits (shiftL, shiftR)
a000196 :: Integer -> Integer
a000196 0 = 0
a000196 n = newton n (findx0 n 1) where
   -- find x0 == 2^(a+1), such that 4^a <= n < 4^(a+1).
   findx0 0 b = b
   findx0 a b = findx0 (a `shiftR` 2) (b `shiftL` 1)
   newton n x = if x' < x then newton n x' else x
                where x' = (x + n `div` x) `div` 2
a000196_list = concat $ zipWith replicate [1,3..] [0..]
-- Reinhard Zumkeller, Apr 12 2012, Oct 23 2010

a(n) = isqrt(n) # Paul Muljadi, Jun 03 2024

Magma
```
[Isqrt(n) : n in [0..100]];
```

Digits := 100; A000196 := n->floor(evalf(sqrt(n)));

Table[n, {n, 0, 20}, {2n + 1}] //Flatten (* Zak Seidov Mar 19 2011 *)
IntegerPart[Sqrt[Range[0, 110]]] (* Harvey P. Dale, May 23 2012 *)
Floor[Sqrt[Range[0, 99]]] (* Alonso del Arte, Dec 31 2013 *)
a[ n_] := SeriesCoefficient[ (EllipticTheta[ 3, 0, x]  - 1) / (2 (1 - x)), {x, 0, n}]; (* Michael Somos, May 28 2014 *)

PARI
```
{a(n) = if( n<0, 0, sqrtint(n))};
```

# from http://code.activestate.com/recipes/577821-integer-square-root-function/
def A000196(n):
  if n < 0:
    raise ValueError('only defined for nonnegative n')
  if n == 0:
    return 0
  a, b = divmod(n.bit_length(), 2)
  j = 2**(a+b)
  while True:
    k = (j + n//j)//2
    if k >= j:
      return j
    j = k
print([A000196(n)for n in range(102)])
# Jason Kimberley, Nov 09 2016

from math import isqrt
def a(n): return isqrt(n)
print([a(n) for n in range(102)]) # Michael S. Branicky, Feb 15 2023

;; The following implementation uses higher order function LEFTINV-LEASTMONO-NC2NC from my IntSeq-library. It returns the least monotonic left inverse of any strictly growing function (see the comment-section for the definition) and although it does not converge as fast to the result as many specialized integer square root algorithms, at least it does not involve any floating point arithmetic. Thus with correctly implemented bignums it will produce correct results even with very large arguments, in contrast to just taking the floor of (sqrt n).
;; Source of LEFTINV-LEASTMONO-NC2NC can be found under https://github.com/karttu/IntSeq/blob/master/src/Transforms/transforms-core.ss and the definition of A000290 is given under that entry.
(define A000196 (LEFTINV-LEASTMONO-NC2NC 0 0 A000290)) ;; Antti Karttunen, Oct 06 2017

a(n) = Card(k, 0 < k <= n such that k is relatively prime to core(k)) where core(x) is the squarefree part of x. - Benoit Cloitre, May 02 2002
a(n) = a(n-1) + floor(n/(a(n-1)+1)^2), a(0) = 0. - Reinhard Zumkeller, Apr 12 2004
From Hieronymus Fischer, May 26 2007: (Start)
a(n) = Sum_{k=1..n} A010052(k).
G.f.: g(x) = (1/(1-x))*Sum_{j>=1} x^(j^2) = (theta_3(0, x) - 1)/(2*(1-x)) where theta_3 is a Jacobi theta function. (End)
a(n) = floor(A000267(n)/2). - Reinhard Zumkeller, Jun 27 2011
a(n) = floor(sqrt(n)). - Arkadiusz Wesolowski, Jan 09 2013
Sum_{n>0} 1/a(n)^s = 2*zeta(s-1) + zeta(s), where zeta is the Riemann zeta function. - Enrique Pérez Herrero, Oct 15 2013
From Wesley Ivan Hurt, Dec 31 2013: (Start)
a(n) = Sum_{i=1..n} (A000005(i) mod 2), n > 0.
a(n) = (1/2)*Sum_{i=1..n} (1 - (-1)^A000005(i)), n > 0. (End)
a(n) = sqrt(A048760(n)), n >= 0. - Wolfdieter Lang, Mar 24 2015
a(n) = Sum_{k=1..n} floor(n/k)*lambda(k) = Sum_{m=1..n} Sum_{d|m} lambda(d) where lambda(j) is Liouville lambda function, A008836. - Geoffrey Critzer, Apr 01 2015
Sum_{n>=1} (-1)^(n+1)/a(n) = log(2) (A002162). - Amiram Eldar, May 02 2023

A028392 a(n) = n + floor(sqrt(n)).

Original entry on oeis.org

0, 2, 3, 4, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 76, 77, 78, 79

Offset: 0

N. J. A. Sloane

A171746 gives number of iterations to reach a square. - Reinhard Zumkeller, Oct 14 2010
From Carmine Suriano, Oct 15 2010: (Start)
Also the sequence of integers left after performing the following procedure:
1. Remove the element at 1st position (1) and compact the sequence;
2. Remove the element at 4th (2^2-th) position (5) and compact the sequence;
3. Remove the element at 9th (3^2-th) position (11) and compact the sequence;
....
n. Remove the element at (n-square)th position (n^2 + n - 1) and compact the sequence;
(End)

			G.f. = 2*x + 3*x^2 + 4*x^3 + 6*x^4 + 7*x^5 + 8*x^6 + 9*x^7 + 10*x^8 + 12*x^9 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
L. F. Klosinski, G. L. Alexanderson and A. P. Hillman, The William Lowell Putnam Mathematical Competition: Problem B4, Amer. Math. Monthly 91 (1984), 487-495.

Complement of A028387.

Cf. A000196. - Reinhard Zumkeller, Oct 14 2010

a028392 n = n + a000196 n  -- Reinhard Zumkeller, Oct 28 2012

Table[n + Floor[Sqrt[n]], {n, 0, 99}] (* Vladimir Joseph Stephan Orlovsky, Mar 29 2010 *)

{a(n) = if( n<0, 0, n + sqrtint(n))}; /* Michael Somos, Jun 11 2003 */

from math import isqrt
def A028392(n): return n+isqrt(n) # Chai Wah Wu, May 16 2023

(0 to 99).map(n => (n + Math.floor(Math.sqrt(n))).toInt) // Alonso del Arte, Nov 03 2019

a(n) = 2*n - A028391(n).

G.f.: x / (1 - x)^2 + (theta3(x) - 1) / (2 * (1 - x)). - Michael Somos, Mar 24 2012

A135668 a(n) = ceiling(n + sqrt(n)).

Original entry on oeis.org

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

Offset: 1

Mohammad K. Azarian, Nov 25 2007

Complement of A002061. - Kieren MacMillan, Dec 16 2007

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

Cf. A134914, A135660, A135661, A135662, A135663, A135664, A135665, A028391, A002061.

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

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

from sympy import integer_nthroot
def A135668(n): return n+(a:=integer_nthroot(n,2))[0]+(not a[1]) # Chai Wah Wu, Aug 26 2024

A135671 a(n) = ceiling(n - n^(2/3)).

Original entry on oeis.org

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

Offset: 1

Mohammad K. Azarian, Nov 25 2007

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

Cf. A135660, A135661, A135662, A135663, A135664, A135665, A028391, A135668, A135669, A135670.

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

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

a(n)=n-sqrtnint(n^2,3) \\ Charles R Greathouse IV, Sep 02 2015

Offset corrected by Mohammad K. Azarian, Nov 19 2008

A135672 a(n) = floor(n - n^(2/3)).

Original entry on oeis.org

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

Offset: 1

Mohammad K. Azarian, Nov 25 2007

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

Cf. A135660, A135661, A135662, A135663, A135664, A135665, A028391, A135668, A135669, A135670, A135671.

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

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

a(n)=n-sqrtnint(n^2-1,3)-1 \\ Charles R Greathouse IV, Sep 02 2015

Offset corrected by Mohammad K. Azarian, Nov 19 2008

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

Terence Tao, May 25 2024

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.

			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.

Jinyuan Wang, Table of n, a(n) for n = 1..200
Thomas Bloom, Problem 121, Erdős Problems.
David A. Corneth, PARI program
Paul Erdős, Andràs Sárközy, and Vera T. Sós, On Product Representations of Powers, I, Europ. J. Combinatorics 16 (1995), 567--588.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.
Terence Tao, Erdős problem database, see no. 121.

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

PARI
```
\\ See PARI link
```

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

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

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)

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

A135673 Ceiling(n + n^(2/3)).

Original entry on oeis.org

2, 4, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 25, 27, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 41, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 66, 68, 69, 70, 71, 72, 73, 75, 76, 77, 78, 79, 80, 82, 83

Offset: 1

Mohammad K. Azarian, Nov 25 2007

			a(6) = 10; ceiling(6 + 6^(2/3)) = ceiling(9.30192...) = 10.

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

Cf. A135660, A135661, A135662, A135663, A135664, A135665, A028391, A135668, A135669, A135670, A135671, A135672.

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

A135673:=n->ceil(n + n^(2/3)); seq(A135673(k), k=1..100); # Wesley Ivan Hurt, Nov 01 2013

Table[Ceiling[n+n^(2/3)],{n,60}] (* Harvey P. Dale, Nov 17 2012 *)

More terms from Wesley Ivan Hurt, Nov 01 2013

A135674 Floor(n+n^(2/3)).

Original entry on oeis.org

2, 3, 5, 6, 7, 9, 10, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 24, 26, 27, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 40, 42, 43, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 61, 62, 63, 64, 65, 67, 68, 69, 70, 71, 72, 74

Offset: 1

Mohammad K. Azarian, Nov 25 2007

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

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

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

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

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

Terence Tao, May 26 2024

nonn

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.

			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.

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.

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

Lower bounded by A000720.

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

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

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

cp's OEIS Frontend

A355147 Triangle read by rows: T(n,k) is the number of product-free subsets of {1,...,n} with cardinality k; n >= 0, 0 <= k <= A028391(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A000196 Integer part of square root of n. Or, number of positive squares <= n. Or, n appears 2n+1 times.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

A028392 a(n) = n + floor(sqrt(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Scala

Formula

A135668 a(n) = ceiling(n + sqrt(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Python

A135671 a(n) = ceiling(n - n^(2/3)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A135672 a(n) = floor(n - n^(2/3)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

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

Views

Author