ISC Practicals and Theory - Lucky Numbers (OOP)

Lucky numbers are the numbers that survive a special sieve on the list 1, 2, 3, ..., $n$: delete every 2nd number, then every 3rd of what is left, then every 7th, and so on. This version is written as a class Lucky with data members, a parameterised constructor and methods that each do one job, and main creates an object and calls them.

Definition

Write 1, 2, 3, ..., $n$. Delete every 2nd number. The 2nd number now left is 3, so delete every 3rd number of the list left. The 3rd number left is 7, so delete every 7th number, and so on: the number at the next position gives the next gap. Stop when the gap is larger than the count of numbers left. The numbers never deleted are the lucky numbers: 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, ...

For $n = 30$ the lucky numbers are 1, 3, 7, 9, 13, 15, 21, 25. The range accepted is 1 to 100.

Algorithm

1. main reads the limit into num and creates the object with new Lucky(num). The parameterised constructor Lucky(int nn) stores it in n and sets size to 0; the array a is created later.
2. isValid() returns true when $1 \le n \le 100$. If it returns false, main prints an error message and stops.
3. fill() creates a of size $n$, stores 1, 2, ..., $n$ in it and sets size = n.
4. sieve() calls deleteEvery(2), then sets k = 1 and, while k < size and a[k] <= size, calls deleteEvery(a[k]) and increases k.
5. deleteEvery(step) copies each number to the front unless its position i + 1 is a multiple of step:
   • j is where the next survivor is stored, starting from 0.
   • If (i + 1) % step != 0, then a[j] = a[i] and j increases.
   • At the end size = j.
6. display() prints a[0] to a[size - 1] and then size as the count.

Program

The constructor sets up the object, isValid() checks the range, fill() stores the numbers, deleteEvery(int) does one round of deleting by shifting, sieve() repeats the rounds and display() prints the result.

import java.util.Scanner;

/**
 * Class Lucky prints all lucky numbers from 1 to n.
 * Start with 1, 2, 3, ..., n. Delete every 2nd number; then the 2nd number
 * left (3) says delete every 3rd number of what is left; then the next
 * surviving number (7) says delete every 7th, and so on.
 */
public class Lucky
{
    int n;       // upper limit up to which lucky numbers are to be found
    int[] a;     // holds the numbers still not deleted, packed at the front
    int size;    // how many numbers are still in a[] (a[0] to a[size - 1])

    /**
     * Parameterised constructor.
     * @param nn the upper limit, stored in n
     */
    Lucky(int nn)
    {
        n = nn;
        a = null; // the array is created later, in fill()
        size = 0;
    }

    /**
     * Checks whether n is in the allowed range.
     * @return true if 1 <= n <= 100, otherwise false
     */
    boolean isValid()
    {
        return n >= 1 && n <= 100;
    }

    /** Stores 1, 2, 3, ..., n in the array. */
    void fill()
    {
        a = new int[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = i + 1; // a[i] holds the number i + 1
        }
        size = n;
    }

    /**
     * Deletes every step-th number of the numbers now left, by shifting
     * the survivors to the front of the array.
     * @param step the gap: delete positions step, 2 * step, 3 * step, ... (counting from 1)
     */
    void deleteEvery(int step)
    {
        int j = 0; // position where the next survivor is to be stored
        for (int i = 0; i < size; i++)
        {
            // the number at index i is at position i + 1; keep it unless that is a multiple of step
            if ((i + 1) % step != 0)
            {
                a[j] = a[i];
                j++;
            }
        }
        size = j; // only j numbers survive
    }

    /** Repeats the deletions: the number at index k gives the next step. */
    void sieve()
    {
        deleteEvery(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)
        // stop when there is no number at index k, or its value is more than the numbers left
        while (k < size && a[k] <= size)
        {
            deleteEvery(a[k]);
            k++; // the next surviving number gives the next step
        }
    }

    /** Prints the lucky numbers and their count. */
    void display()
    {
        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);
    }

    /** Reads n, creates the object and calls the methods in order. */
    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 num = sc.nextInt();              // limit entered by the user
        Lucky ob = new Lucky(num);           // object holding the limit
        if (ob.isValid())
        {
            ob.fill();
            ob.sieve();
            ob.display();
        }
        else
        {
            System.out.println("Invalid input. n must be from 1 to 100.");
        }
    }
}

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: num = 30, so n = 30. After fill(), a holds 1 to 30 and size = 30.

Now k = 4 and a[4] = 13 is more than size = 8, so the loop ends. display() prints 1 3 7 9 13 15 21 25 and Count of lucky numbers = 8. This matches 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. Lucky primes "Print the numbers up to n that are both lucky and prime."