chanllage

in 悬而未决

有一些有趣但是大概需要高深数学知识的计算机问题悬而未决，特此记录。

张帆猜想

哈希冲突概率

有等式$(a_1^k+a_2^k+…+a_n^k) % 2^{64}=(b_1^k+b_2^k+…+b_n^k)% 2^{64}$，

定义“冲突“为：满足上述等式的两个多重集合{an}{bn}不完全相同。

希望说明：当n为1e5的级别时，k=2时冲突概率极高，而当k>=3时冲突的概率就会降低到一个可以接受的程度。

集合{an}{bn}的元素可能可以认为是在[0, 2^64)均匀分布的，不过这一点没有仔细考究，也没有造若干数据进行检验。