ISC COMPUTER SCIENCE PRACTICAL 2001 QUESTION 1 : LUCKY NUMBERS

Consider the sequence of natural number:-

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28........

Removing every second number produces the sequence

1,3,5,7,9,11,13,15,17,19,21,23,25,27.......

Removing every third number from the above sequence produces the sequence

1,3,7,9,13,15,19,21,25,27,......

This process continues indefinitely by removing the fourth, fifth and so on, till after a fixed number of steps,

certain natural numbers remain indefinitely. These are known as lucky numbers. Writes a program to

generate and print lucky numbers less than a given natural N, where N <= 50.

I will not be using any standard library function related to Array class to 

ease the coding. It is important to do all the coding logically rather than using

any short-cut method! To start with the program is quite simple in implementing.

Given a sequence we need to first delete all the elements at the even postion, next

for the new sequence we need to delete all the elements at position divisible by 3 and so on....

Untill there are no numbers left to be deleted. This part is important to understand, because

this is the point where the loop must be stopped. Or else you will see that the same sequence is
appearing for nth and n+1 th iteration. So when at the nth step we are supposed

to delete the elements at nth positon alternately the sequence should be of length greater than n.

To understand this let us examine one specific case where N = 18;

So, the initial sequnce is 

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18

After deleting all the elements at even positions, the new sequnce should be

1,3,5,7,9,11,13,15,17 and then all elemenst at postion divisible by 3 should be deleted...

For this we have inserted '-1' at all the even positions

So the sequnce should look like this:

1,-1,3,-1,5,-1,7,-1,9,-1,11,-1,13,-1,15,-1,17,-1

the following code achieves this, position_counter where is 2 and numb is 18

  for(int i=position_counter-1;i<numb;i +=position_counter) {

                          non_lucky++;

                          if(list_lucky_numbers[i]!=-1 ) {

                                 list_lucky_numbers[i]=-1;

                          }

                    }

Now for the next step, we need to get rid of all -1 to delete further elements

this has been achieved by the method

private void shiftLuckyNumbers(int[] list_lucky_numbers)

After this step the array will look like this

1,3,5,7,9,11,13,15,17,-1,-1,-1,-1,-1,-1,-1,-1,-1

Now we will repeat the same process on this sequnce for position_counter = 3

and ignoring all elemenst with value -1 because those are unlucky numbers.

import java.util.*;

public class ISC2001Q1 {

       public static void main(String[] args) {

       int N;

       Scanner in = new Scanner(System.in);

       do {

             System.out.println("Enter the value of N (less than 50):");

             N = in.nextInt();

             if(N >50)

                    System.out.println("INVALID INPUT,TRY AGAIN:");

             }while(N > 50);

       LuckyNumber obj = new LuckyNumber(N);

       obj.generateLuckyNumber();

       System.out.println();

       System.out.println("Lucky numbers less than "+N+" are:");

       obj.printLuckyNumber();

       in.close();

       }

}

class LuckyNumber{

       public void printLuckyNumber() {

             for(int j=0;j<numb;j++)

                    if(list_lucky_numbers[j]!=-1 && list_lucky_numbers[j] < numb)

                          System.out.print(list_lucky_numbers[j]+" ");

       }

       public void generateLuckyNumber() {

             int non_lucky;

             for(int j=0;j<numb;j++)

                    list_lucky_numbers[j] = j+1;

            

             while(position_counter <= numb ) {

                    /* # Just to print the steps */

                    for(int l=0;l<numb;l++)

                          if(list_lucky_numbers[l]!=-1)

                          System.out.print(+list_lucky_numbers[l]+" "); //#

                   

                    // deleting the alternate position in the sequence

                    non_lucky=0;

                    for(int i=position_counter-1;i<numb;i +=position_counter) {

                          non_lucky++;

                          if(list_lucky_numbers[i]!=-1 ) {

                                 list_lucky_numbers[i]=-1;

                          }

                    }

                    shiftLuckyNumbers(list_lucky_numbers);

                    System.out.println();

                    position_counter++;

                    // to break form the loop when no unlucky numbers are left

                    if(non_lucky < position_counter)

                                 break;

                   

                    System.out.println();

             }

                   

       }

       private void shiftLuckyNumbers(int[] list_lucky_numbers) {

             int pos;

             for(int k=0;k<numb;k++) {

                    if(list_lucky_numbers[k] == -1 ) {

                          pos = k;

                          while(list_lucky_numbers[pos] == -1 ) {

                                 if(pos>=numb-1)

                                       break;

                                 pos++;

                                 }

                          int tmp = list_lucky_numbers[k];

                          list_lucky_numbers[k] = list_lucky_numbers[pos];

                          list_lucky_numbers[pos]= tmp;

                          }

                    }

       }

       LuckyNumber(int N){

             numb = N;

             list_lucky_numbers = new int[numb];

             position_counter = 2;

       }

       private int numb;

       private int[] list_lucky_numbers;

       private int position_counter;

}