hash(n)==n in Python, large numbers, and Curiosity
I recently ran across this curious discussion on stackoverflow about the the largest number in Python where hash(n) == n.
So, someone noticed that in Python, for small integers, hash(n) is the same as n. And also noticed that this is not true for really large numbers (hash(2**100) != 2**100). He then decided to find out what is the largest number for which hash(n) == n, investigated using a binary search algorithm, no less, and found out that in Python 2.x this number is 2305843009213693950.
Next he wondered what is special about this number. This is not 2⁶³-1 or 2⁶⁴-1 (the largest numbers that can be stored in one word on a 64-bit machine).
Turns out the answer is that it is 2⁶¹-1. The largest Mersenne Prime number that fits in 64-bits.
See the full discussion. It is fascinating, and goes into many other details of prime numbers and hashing across different data types.
Question for an average software guys is this:
- Would you have wondered if hash(n) == n
- If yes, would you have tried to figure out what is the largest n for which this is true?
- And when you discovered that the answer is not easy to find (it’s not a small number), would you have used a binary search algorithm to find the number
- And then, would you have been curious about what is special about this number?
- No, I wouldn’t expect you to know or realize that the number in question was a Mersenne Prime, but when you did find out it was, did you wonder as to what does a Mersenne Prime have to do this this problem?
This is the stuff curiosity if made of. Curiosity is a good thing. You should cultivate it. It’s like a muscle — improves with exercise.
[Note: if you’re not into Maths or Computer Science, I don’t expect you to feel curious about the things I mentioned above, but there should be similar adjacent areas in your own field — things that are not directly related, or apparently relevant to your job, your work — but you should feel curious about.]