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

Robert Gerbicz robert.gerbicz at gmail.com
Wed Feb 20 21:02:11 CET 2013


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.


More information about the SeqFan mailing list