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

[Robert Gerbicz]

2013/2/20 Charles Greathouse <charles.greathouse at case.edu>:
> 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/

Computed (and added) the terms up to a(1024) with gmp. It took 100
minutes and roughly 800MB Ram. Just for comparison it takes 12 seconds
to get all terms up to a(256) (use N=256).

Define A[n][m][v]:=|{f(1..n)->(1..m): every |preimage|<=v}|, use that
A[n][m][v]=A[n][m][v-1]+sum(i=1,inf,A[n-i*v][m-i][v-1]*n!/(v!^i*(n-v*i)!)*binomial(m,i))
here you can use only a two dimensional array if you calculate this
from v=0,1,2,..
in memory and in speed this beats the Mathematica code. Obviously you
can get a(n) with the A array.

ps. It would use less memory with Chinese Remainder Theorem (use that
a(n)<=n^(n+1)), but that would be slower in time.