Count the number of times a function runs This is a teaser a friend of mine sent. It seems straightforward, but I can't seem to get my head around it, probably due to my lack of sleep.


You have 16 bits available. 
Compose a function, and find a way to know when the function has run approximately one million times.
You MAY NOT use any additional memory space other than the 16 bits given. 
Recursion may be used for efficiency, but, again, you MAY NOT use
memory definition inside the recursion frames: only the 16 bits.
One-million in binary is equal to 11110100001001000000 (20 bits).  Thus, we cannot implement a simple counter for this.  

Instead, the max number we can represent with 16 bits is 1111111111111111 = 65,535.  Since the answer requires that we only need to approximate 1 million function runs, we could add one to the counter approximately once every 16 function runs, and know that the function has run about 1 million times when the counter reaches 1000000/16 = 62500.  

Below is the pseudocode of a potential solution, assuming that counter is a positive integer stored in 16 bits.  Also, this assumes that calls such as random(1,16) do not count towards memory as long as they are not stored in a variable.  Last, the random(x,y) function should give a random integer between x and y inclusive.

counter = 0;

function amIAttaBoutaMillionYet(){
    if(random(1,16)==16 &amp;&amp; counter&lt;62501){
        counter++;
    }
    if(counter==62500){
        return true;
    }
    return false;
}


UPDATE

Fixed function so that it won't show true after about 2 million+, 3 million+, etc.   function runs.  (thanks trinithis!)