Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a textbook based question. In The Art of Computer Programming Volume 3, Knuth says that for a hash function $h(k) = k \bmod M$, $M$ should not be a multiple of $3$.

The explanation given is:

If keys are alphabetic, two keys that differ only by permutation of letters would differ in numeric value by a multiple of 3. This occurs because $2^{2n} \bmod 3 = 1$ and $10^{n} \bmod 3 = 1$)."

I'd be grateful, if someone can clarify why this is so, and how that equation is connected to alphabetical keys and $M$ being a power of $3$.

share|cite|improve this question

migrated from Nov 1 '12 at 20:47

This question came from our site for theoretical computer scientists and researchers in related fields.

The question as stated is unclear. – Yuval Filmus Oct 26 '12 at 4:58

Observe that $2^{2n} = 4^n \equiv 1^n\equiv 1 \mod 3$ and $10^n \equiv 1^n\equiv 1 \mod 3$. The relevance of $2^{2n}$ is that exchanging two characters (stored in bytes with even numbers of bits) amounts to multiplying one part of a key by $2^{2n}$ for some $n$, and dividing another part by a like amount. (Also note, powers of 3 ($3^k$ for some $k$) are multiples of 3 ($3\cdot m$ for some $m$ if $k>0$) but multiples of 3 are much more common than its powers.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.