cp's OEIS Frontend

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.

%I A379604 #31 Feb 03 2025 21:26:55
%S A379604 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,
%T A379604 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,
%U A379604 9,9,9,9,10,10,10,10,10,10,10,10,9,10,10,10
%N 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.
%C A379604 With uniformly distributed input, the maximum number of items in a bucket is ceiling(n/B).
%C A379604 If B divides n then all buckets hold the same number of items, which is when n is in A006446.
%H A379604 Paolo Xausa, <a href="/A379604/b379604.txt">Table of n, a(n) for n = 1..10000</a>
%H A379604 Wikipedia, <a href="https://en.wikipedia.org/wiki/Bucket_sort">Bucket sort</a>
%F A379604 a(n) = ceiling(n/floor(sqrt(n))).
%e A379604 For n = 10 a(10) = 4 because:
%e A379604 Input array: [0,1,2,3,4,5,6,7,8,9] and floor(sqrt(10)) = 3.
%e A379604 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.
%t A379604 A379604[n_] := Ceiling[n/Floor[Sqrt[n]]]; Array[A379604, 100] (* _Paolo Xausa_, Feb 03 2025 *)
%o A379604 (Python)
%o A379604 from sympy.core.intfunc import isqrt
%o A379604 a = lambda n: ((n-1) // isqrt(n)) + 1
%o A379604 print([a(n) for n in range(1,85)])
%Y A379604 Cf. A000196, A000196, A006446.
%K A379604 nonn,easy
%O A379604 1,2
%A A379604 _Darío Clavijo_, Dec 28 2024