## Oct 22, 2013

### Prime Power Math Puzzle

Source: IBM Ponder This - June 2012 - Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB)

Problem:

Two players starts with the number N and play in turns. In each turn the player chooses a prime power p^m > 1, which divides N and updates N to be N/(p^m). The player who sets N to be 1 - wins.
What are all the winning moves from the initial state of N=1,506,009,006,001,500,000,000 ?

We are looking for all the moves the first player can make which, assuming he plays correctly, can guarantee him winning the game.

Update (24 June 2014):
Solution: Posted by Gowtham Kumar (PhD Student, Stanford, IITM Alumnus) and me in comments!

2. First we factor N= 1,506,009,006,001,500,000,000.
So the factorization of N is 2^8 * 3^1 * 5^9 * 7^4 * 11^4 * 13^4.

Then we note that the game is a actually the classic game of Nim in disguise.

The initial state is (8,1,9,4,4,4)

Nim Game on Wikipedia: http://en.wikipedia.org/wiki/Nim

3. Great thanks a lot !

### Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...