techInterview Discussion

There is a squence of numbers...1,2,3.....N.Now we delete every 2nd number...so the series becomes...1,3,5,7,.....:now delete every 3rd number i.e delete 5,11..etc then every 4th element...now how can you predict whether a number x will survive in the series after m number of deletions

This is an MS question...consider the position of the number after each deletion

A numbers position is moved forward X number of spaces each round, where X is (position / (step)), e,g. 1111 is moved foward (1111 / 2 ) steps the first round to 556, then moved foward (556 / 3) to 371 in the 2nd round and so on.  Using this, each round you only have to check to see if the current position modulus the current step amount == 0, whether or not the new position is below a "safe" threshold (e.g. it can no longer be eliminated) or whether we've gone through as many rounds as we'll go through. 

I think this is right.  I'm probably doing something dumb with the division but the idea should be correct. 

C#
class Program
{
    static void Main( string[] args )
    {
        int rounds = 10;
        int number = 12412411;
        int safe = 1;
        int pos = number;
        var i = 0;
        for( i = 0; i <= rounds; i++ )
        {
            safe += ( i * 2 );
        
            if( number <= safe )
                break;

            if( pos % ( i + 2 ) == 0 )
                break;

            pos -=  (int)((pos - 1) / (i+2));
        }

        if( i == rounds )
            Console.WriteLine( "Number will be safe through " + rounds.ToString() + " rounds." );
        else
            if( number > safe )
                Console.WriteLine( "Number will be eliminated on round : " +(i+1).ToString() );
                else
                Console.WriteLine( "Number will be untouchable in round : " + (i+1).ToString() );
        }
    }

concept of lucky numbers
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

above link was  incorrect..
http://en.wikipedia.org/wiki/Lucky_number

A lucky number is not what the OP posted about.  Does anyone know the name of the sequence that the OP posted about?

Sincerely,

Gene Wirchenko

Step 1: Compute sequence.


>>> lst = list(xrange(1, 1000))
>>> for skip in xrange(2, 1000):
...  del lst[skip - 1::skip]
...
>>> print lst
[1, 3, 7, 13, 19, 27, 39, 49, 63, 79, 91, 109, 133, 147, 181, 207, 223, 253, 289, 307, 349, 387, 399, 459, 481, 529, 567, 613, 649, 709, 763, 807, 843, 927, 949]


Step 2: Look up on OEIS.

http://www.research.att.com/~njas/sequences/index.html?q=1%2C+3%2C+7%2C+13%2C+19%2C+27%2C+39%2C+49%2C+63%2C+79&language=english&go=Search

Dear Wirchenko,

In a list of integers after particular sieving process yields certain numbers that permanently escape getting killed. That's why they are "lucky."

so dont get confused with "ULAM LUCKEY NUMBER" with the general term lucky numbers.