[seqfan] Re: A208250 and growth of the expected largest bucket

[hv at crypt.org]

Ah super, thanks very much.

Hugo

Charles Greathouse <charles.greathouse at case.edu> wrote:
:b(n) should be about log n/log log n. More precisely, b(n) = IGamma(n) -
:3/2 + o(1) where IGamma is the inverse gamma function, see
:
:G. H. Gonnet. Expected length of the longest probe sequence in hash code
:searching. Journal of the ACM, 28(2):289-304, 1981.
:
:Charles Greathouse
:Analyst/Programmer
:Case Western Reserve University
:
:
:On Wed, Feb 20, 2013 at 3:09 AM, <hv at crypt.org> wrote:
:
:> Could someone help me consider how to calculate more values of A208250,
:> or to approximate them? I'd like to find values for rather larger n,
:> but I'm struggling to think of an approach that will make it practical
:> to calculate for n substantially greater than the 19 already listed.
:>
:> Working a(4) by hand, for example, I get:
:>
:> (4,0,0,0) has largest bucket 4; can appear 4 ways; can be constructed in
:> only one order; contribution is 4 * 4 * 1 => 16.
:> (3,1,0,0) => largest bucket 3; 12 ways; 4 orders => 144.
:> (2,2,0,0) => 2 * 6 * 6 => 72.
:> (2,1,1,0) => 2 * 12 * 12 => 288.
:> (1,1,1,1) => 1 * 1 * 24 => 24.
:>   total 16+144+72+288+24 = 544
:> .. but an approach iterating over all partitions of n is not going to scale
:> very far.
:>
:> Motivation: for a programming-related issue I need to get a clearer picture
:> of how the expected size of largest bucket b(n) = A208250(n) / n^n will
:> grow,
:> particularly for n = 2^m. From the current values I get:
:>
:> b(2^0) = 1
:> b(2^1) = 1.5
:> b(2^2) = 2.125
:> b(2^3) = 2.597 (approx)
:> b(2^4) = 3.078 (approx)
:>
:> Hugo
:>
:> _______________________________________________
:>
:> Seqfan Mailing list - http://list.seqfan.eu/
:>
:
:_______________________________________________
:
:Seqfan Mailing list - http://list.seqfan.eu/