ISC Practicals and Theory - Lucky Numbers

Lucky numbers are the numbers that survive a special sieve. We write the numbers 1, 2, 3, ..., $n$ in an array and delete numbers in rounds; the number that gives the gap for each round is itself taken from the numbers still left. This program, written in the main method alone, reads $n$, runs the sieve on an int array and prints all the lucky numbers up to $n$ and how many there are.

Definition

Start with the list 1, 2, 3, 4, 5, ... up to $n$.

1. Delete every 2nd number (2, 4, 6, ...). What is left is 1, 3, 5, 7, 9, ...
2. The 2nd number left is 3. Delete every 3rd number of the list now left (5, 11, 17, ...). What is left is 1, 3, 7, 9, 13, 15, ...
3. The 3rd number left is 7. Delete every 7th number of the list now left. Then the 4th number left, 9, gives the next gap, and so on.
4. Continue, taking the number at the next position as the gap, until the gap is larger than the count of numbers left (so nothing more can be deleted).

The numbers that are never deleted are lucky numbers. The first few are 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, ...

For $n = 30$: after step 1 the list is 1, 3, 5, ..., 29 (15 numbers). Deleting every 3rd leaves 1, 3, 7, 9, 13, 15, 19, 21, 25, 27 (10 numbers). Deleting every 7th removes 19, and deleting every 9th removes 27. The lucky numbers up to 30 are 1, 3, 7, 9, 13, 15, 21, 25.

Positions are counted from 1 in each round, and the list is counted again after every round. The program accepts $n$ from 1 to 100.

Algorithm

1. Read n. If it is not from 1 to 100, print an error message and stop.
2. Fill the array a with the numbers 1 to n (a[i] = i + 1) and set size = n, the number of values still in the array.
3. Set step = 2 (the first round deletes every 2nd number) and k = 1, the index of the number that will give the next step.
4. Repeat the round:
   • delete every step-th value: copy only the survivors to the front of the array (a[j] = a[i] when (i + 1) % step != 0, counting them in j) and set size = j;
   • if k < size and a[k] <= size, the next surviving number a[k] gives the next step; add 1 to k and do another round. Otherwise stop.
5. Print a[0] to a[size - 1], which are the lucky numbers, and their count size.

Program

In main, the outer while loop is one round of the sieve in each pass, and the inner for loop packs the survivors at the front of the array.

import java.util.Scanner;
public class Lucky
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);   // reads the input from the keyboard
        System.out.print("Enter n (1 to 100): ");
        int n = sc.nextInt();                  // upper limit up to which lucky numbers are to be found
        if (n < 1 || n > 100)
        {
            System.out.println("Invalid input. n must be from 1 to 100.");
        }
        else
        {
            int[] a = new int[n];              // holds the numbers still not deleted, packed at the front
            for (int i = 0; i < n; i++)
            {
                a[i] = i + 1;                  // a[i] holds the number i + 1
            }
            int size = n;                      // how many numbers are still in a[] (a[0] to a[size - 1])
            int step = 2;                      // first step: delete every 2nd number (the numbers 2, 4, 6, ...)
            int k = 1;                         // index of the number that gives the next step (a[1] is now 3)
            boolean more = true;               // false when no further step is possible
            while (more)
            {
                int j = 0;                     // position where the next survivor is to be stored
                for (int i = 0; i < size; i++)
                {
                    if ((i + 1) % step != 0)   // every step-th place is deleted
                    {
                        a[j] = a[i];
                        j++;
                    }
                }
                size = j;                      // only j numbers survive
                if (k < size && a[k] <= size)  // the next surviving number gives the next step
                {
                    step = a[k];
                    k++;
                }
                else
                    more = false;
            }
            System.out.println("Lucky numbers up to " + n + ":");
            for (int i = 0; i < size; i++)
            {
                System.out.print(a[i] + " ");
            }
            System.out.println();
            System.out.println("Count of lucky numbers = " + size);
        }
    }
}

Variable description table

Sample input and output

Enter n (1 to 100): 30
Lucky numbers up to 30:
1 3 7 9 13 15 21 25 
Count of lucky numbers = 8

Enter n (1 to 100): 100
Lucky numbers up to 100:
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99 
Count of lucky numbers = 23

Enter n (1 to 100): 1
Lucky numbers up to 1:
1 
Count of lucky numbers = 1

Enter n (1 to 100): 101
Invalid input. n must be from 1 to 100.

Dry run

Input: n = 30. After the array is filled, a holds 1 to 30 and size = 30.

Now k = 4 and a[4] = 13 is more than size = 8, so the while loop ends. The program prints 1 3 7 9 13 15 21 25 and Count of lucky numbers = 8. This matches the output of the first sample run.

Variations

1. Test one number "Accept a number and check whether it is a lucky number."
2. Range "Print all lucky numbers between m and n."
3. Sum of lucky numbers "Find the sum of all lucky numbers up to n."
4. Lucky primes "Print the numbers up to n that are both lucky and prime."