Twin Primes

A Math oriented question asked at a recent Amazon interview.

Q : Given any twin prime pair, prove that the number between the twin primes is always divisible by 6.

Twin Prime (from Wiipedia) :

A twin prime is a prime number that differs from another prime number by two. Except for the pair (2, 3), this is the smallest possible difference between two primes. Some examples of twin prime pairs are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), ... (821, 823), etc. Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin.

Three Distance Theorem

While learning from this video lecture by Steve Skiena on Discrete Mathematics, he explains the Three Distance Theorem (at time 37:32).


The Three Distance Theorem goes like this : 
For any irrational number 'a', if the sequence of points {i*a}, where 0 <= i <= n, are plotted on a unit distance / circle (wrapped at unit distance), then : 

1. The points divide the circle / line into n+1 distances
2. The maximum number of distinct distances defined is 3
3. The minimum number of distinct distances defined is 2
4. Of the three distinct distances, one is a sum of the other two

Here is a single page PDF explaining the theorem nicely : http://myweb1.lsbu.ac.uk/~whittyr/MathSci/TheoremOfTheDay/NumberTheory/ThreeDistance/TotDThreeDistance.pdf

The findings are really awesome - as Prof Skiena explains and proves the theorem in the lecture.


Application To Hashing
I think because of the distinct distance generation property of the theorem, the theorem can be an effective way to avoid collisions by the basic multiplication method. Ofcourse the other limitations of open addressing apply, but if that approach is chosen, this theorem might be helpful.


The basic idea for collision resoluton would be hashing in this order : 

h(k, 1) = H(K*1*a)

h(k, 2) = H(K*2*a) ...
where 
h(k, l) - hash for the key k, being hashed for the lth time
k - key to insert / lookup
a - an irrational number
1, 2 - the first, second lookup. The l+1th lookup should be performed only if lth lookup had a collision

Tower of Hanoi with a restriction of no direct transfers

We need to solve the Tower of Hanoi problem, with this additional restriction : direct moves between the origin and destination towers is disallowed. All other restrictions still apply  as-is.

For example, if a single disk is to be moved from Tower A to Tower B (using Tower C), then moving the disk directly from A to B is not allowed. The disk must be first transferred to Tower C and then to Tower B.

The purpose is to find the shortest sequence / number of moves we can do this in : 

• T(0) = 0 (basis case, nothing to move)
• T(1) = 2 (from above)
• T(n-discs) = ???

Source : Concrete Mathematics (2nd Edition) Ex. 1.2

Find the summation of first 'n' odd numbers

Find a simple formula for the summation of the first 'n' odd numbers (1, 3, 5.....).
More formally, find a general solution for :  
n
Σ (2k-1)
k=1

Source : CLRS A.1-1

100 Switches & 100 bulbs

There are 100 switches in a room operating 100 bulbs. At iteration '0' all switches are OFF. For every iteration 'i', all switches that are multiples of 'i' are toggled (turn OFF if ON, turn ON if OFF).

You need to find the state of the 'k'th switch/bulb (1<=100) after the 'i' th iteration

Expected O(1) time and space complexity.