In number theory, a lucky number is a natural number in a set which is generated by a “sieve” similar to the Sieve of Eratosthenes that generates the primes. In this post I would demonstrate an easy method for generating lucky numbers in Java. The emphasis would be  more on elegance than complex/clever code and therefore we would be using an extra array to reduce the number of loops in the program. This problem was asked in the ISC Computer Science, Paper 2, that is, in ISC Computer Practical 2001.

An animation demonstrating the lucky number sieve. The numbers in red are lucky numbers.

Lets us say we want to generate lucky number for N=25. Take a list of all natural numbers up to N and remove every second number. From the remaining numbers remove every third number. The process stops when it’s not possible to eliminate any more numbers and the survivors are known as lucky numbers.

Example:

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

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

1 3 7 9 13 15 19 21 25

1 3 7 13 15 19 25

1 3 7 13 19 25

1 3 7 13 19

The Java program for generating lucky numbers is as follows:

class LuckyNumbers{
    public static void main( String args[] ){
        int arr[] = getLuckyNumbers( 25 );
        for( int n: arr ){
            System.out.print( n + " " );
        }
        System.out.println();
    }
    public static int[] getLuckyNumbers( int N ){
        int a[] = new int[ N ], lucky[] = {};
        for( int i = 0; i < a.length; i++ ){
            a[i] = i + 1;
        }
        int offset=1;
        while( ++offset <= a.length ){
            lucky = new int[ a.length - ( a.length / offset ) ];
            for( int i=0, c=0; i < a.length; i++ ){
                if( ( i + 1 )%offset != 0 ){
                    lucky[ c++ ] = a[ i ];
                }
            }
            a = lucky;
        }
        return lucky;
    }
}

In the above program the main logic is inside the function getLuckyNumbers() which accepts an integer array up to which the list is to be generated and returns an integer  array containing the lucky numbers. The variable offset stores the step value in terms of which cancellation is to be carried out and is incremented by one before each iteration. When the offset exceeds the number of elements in the array lucky, we stop the cancellation process. Note that this logic would require extra memory which is actually a trade-off for simplicity and elegance. The amount of memory required would decrease with each iteration and since garbage collection is automatic in Java, the memory not being referenced by any reference variable would be returned to the free pool by the JVM. Note that we could have easily assigned zero ( or any other illegal value, that is any negative number) to the original array, to mark the cancellation, thereby removing the requirement of the second array and printing the array within the function. But, I usually prefer to return the result from a function so that the end user may use it for further calculations if required.

We are using the enhanced for loop construct for displaying the array in the main function. Readers may follow the link to know more about it.

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.