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

Author

Darío Clavijo, Dec 28 2024

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000
• Wikipedia, Bucket sort

Crossrefs

Cf. A000196, A000196, A006446.

Programs

Mathematica

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

Python

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

Formula

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