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 my last post I demonstrated an easy method for generating lucky numbers in Java. The last solution was using an iterative technique. In this post we would see a method for generating lucky numbers using recursion.

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

Lets us first recall the procedure for generating lucky numbers. Let us try 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 using recursion is as follows:

class LuckyNumbers{
    public static void main(String args[]){
        int l[] = getLuckyNumbersRecursive(25);
        for( int n: l ){
            System.out.print(n+ " ");
        }
        System.out.println();
    }
    public static int[] getLuckyNumbersRecursive( int N ){
        int a[] = new int[ N ], lucky[] = {};
        for( int i = 0; i < a.length; i++ ){
            a[i] = i+1;
        }
        return getLuckyNumbersRecursive( a, 2 );
    }
    private static int[] getLuckyNumbersRecursive( int a[], int offset ){
       if( offset > a.length ) return a;
       int 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];
           }
       }
       return getLuckyNumbersRecursive( lucky, offset+1 );
    }
}

In the above program the function getLuckyNumbersRecursive() is overloaded. The public function getLuckyNumbersRecursive(int)  would be invoked by the end user to generate lucky numbers for a given value of N. This private function would then invoke the public function by the same name which implements the cancellation procedure. This main logic is inside the private function getLuckyNumbers() which accepts an integer array up to which the list is to be generated along with the offset value 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 before each recursive call. 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 since the memory would remain occupied till the recursion is complete. The recursive implementation should be avoided in practice as its computationally expensive. It’s more of an intellectual exercise.

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.