most recent 30 from http://mathoverflow.net 2013-05-23T10:53:45Z http://mathoverflow.net/feeds/question/49643 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49643/hash-table-and-fibonacci Nasooh Alavi 2010-12-16T13:15:27Z 2010-12-17T13:19:09Z

<p>Suppose we are building a hash table of size $m = F_{k}$ using the hash function $$h(x) = (F_{k−1} · x) \bmod {F_{k}} $$ Prove that if the consecutive integers $0, 1, 2, . . . , F_{k−1}$ are inserted in order into an initially empty table, each integer is hashed into one of the largest contiguous empty intervals in the table.</p> <p>I found this problem as graduate algorithm's homework at UIUC in 2007. I think a lot on it, but i have no progress.</p> <p>Do you have any idea?</p> <p>After edit: $F_{k}$ is the $k^{th}$ Fibonacci number.</p> <p>P.S. $\textit{It works for any pair of relatively prime integer}$ </p>