LuckyNumber.java

package com.thealgorithms.maths;

/**
 * In number theory, a lucky number is a natural number in a set which is generated by a certain "sieve".
 * This sieve is similar to the sieve of Eratosthenes that generates the primes,
 * but it eliminates numbers based on their position in the remaining set,
 * instead of their value (or position in the initial set of natural numbers).
 *
 * Wiki: https://en.wikipedia.org/wiki/Lucky_number
 */
public final class LuckyNumber {

    private LuckyNumber() {
    }

    // Common validation method
    private static void validatePositiveNumber(int number) {
        if (number <= 0) {
            throw new IllegalArgumentException("Number must be positive.");
        }
    }

    // Function to check recursively for Lucky Number
    private static boolean isLuckyRecursiveApproach(int n, int counter) {
        // Base case: If counter exceeds n, number is lucky
        if (counter > n) {
            return true;
        }

        // If number is eliminated in this step, it's not lucky
        if (n % counter == 0) {
            return false;
        }

        // Calculate new position after removing every counter-th number
        int newNumber = n - (n / counter);

        // Recursive call for next round
        return isLuckyRecursiveApproach(newNumber, counter + 1);
    }

    /**
     * Check if {@code number} is a Lucky number or not using recursive approach
     *
     * @param number the number
     * @return {@code true} if {@code number} is a Lucky number, otherwise false
     */
    public static boolean isLuckyNumber(int number) {
        validatePositiveNumber(number);
        int counterStarting = 2;
        return isLuckyRecursiveApproach(number, counterStarting);
    }

    /**
     * Check if {@code number} is a Lucky number or not using iterative approach
     *
     * @param number the number
     * @return {@code true} if {@code number} is a Lucky number, otherwise false
     */
    public static boolean isLucky(int number) {
        validatePositiveNumber(number);

        int counter = 2; // Position starts from 2 (since first elimination happens at 2)
        int position = number; // The position of the number in the sequence

        while (counter <= position) {
            if (position % counter == 0) {
                return false;
            } // Number is eliminated

            // Update the position of n after removing every counter-th number
            position = position - (position / counter);
            counter++;
        }

        return true; // Survives all eliminations → Lucky Number
    }
}