A379604 a(n) is the maximum number of items in a bucket for the bucket sort algorithm with input {0, 1, ..., n-1} and B = floor(sqrt(n)) buckets.

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

Offset

1,2

Comments

With uniformly distributed input, the maximum number of items in a bucket is ceiling(n/B).

If B divides n then all buckets hold the same number of items, which is when n is in A006446.

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Wikipedia, Bucket sort

Formula

a(n) = ceiling(n/floor(sqrt(n))).

Example

For n = 10 a(10) = 4 because:
Input array: [0,1,2,3,4,5,6,7,8,9] and floor(sqrt(10)) = 3.
Resulting 3 buckets of [0, 1, 2, 3], [4, 5, 6, 7], [8, 9] and the number of items in the buckets is [4,4,2], which is maximum a(10) = 4.

Mathematica

A379604[n_] := Ceiling[n/Floor[Sqrt[n]]]; Array[A379604, 100] (* Paolo Xausa, Feb 03 2025 *)

Prog

(Python)
from sympy.core.intfunc import isqrt
a = lambda n: ((n-1) // isqrt(n)) + 1
print([a(n) for n in range(1, 85)])

Crossrefs

Cf. A000196, A000196, A006446.

Sequence in context: A026256 A079715 A030397 * A257213 A205780 A204905

Adjacent sequences: A379595 A379602 A379603 * A379605 A379606 A379607

Keyword

nonn,easy

Author

Darío Clavijo, Dec 28 2024

Status

approved