Posted on by Kalkicode
Code Number

Lucky numbers program

The Lucky Numbers program aims to determine whether a given number is a "lucky number" or not. Lucky numbers are a concept from number theory and are defined as follows: Starting with a list of integers from 1, we perform a filtering process where we remove every second number from the list. Next, we repeat the process, removing every third number from the remaining list. We continue this process, removing every nth number from the current list, where n is the next number in the list that has not been removed. If the given number survives this process and remains in the list, it is considered a lucky number.

Problem Statement

The program is designed to take an integer as input and determine whether it is a lucky number or not. It employs a loop-based algorithm to simulate the lucky number filtering process and outputs whether the given number survives or not.

Example

Let's understand the lucky number filtering process with the number 9 as an example: 1, 2, 3, 4, 5, 6, 7, 8, 9 -> Start with a list of integers from 1 to 9 1, X, 3, X, 5, X, 7, X, 9 -> Remove every second number (even numbers) 1, X, 3, X, 5, X, 7, X, X -> Remove every third number (next non-removed number is 7) 1, X, 3, X, 5, X, X, X, X -> Remove every seventh number (next non-removed number is 9)

After the filtering process, the number 9 remains in the list. Hence, 9 is a lucky number.

Pseudocode

isLuckyNo(num)
	Input: num - The integer to check if it is a lucky number or not

	Set n = num
	Set position = 2
	Set result = 0

	While result == 0
		If position > n
			Set result = 1 // The number is lucky
		Else if n % position == 0
			Set result = -1 // The number is not lucky
		Else
			Set n = n - n / position
			Increment position by 1

	If result == 1
		Print "num is a lucky number"
	Else
		Print "num is not a lucky number"

Algorithm Explanation

  1. The isLuckyNo function takes an input integer num.
  2. It initializes n to num, which will be used to simulate the filtering process.
  3. The variable position starts at 2, representing the second number to remove.
  4. The variable result is initialized to 0. During the loop, it will store the status of the number being lucky or not (0: undecided, 1: lucky, -1: not lucky).
  5. The loop continues until result is decided (either 1 or -1).
  6. Inside the loop, it checks if position is greater than n, in which case the number is considered lucky (since it survived all filtering steps).
  7. If n is divisible by position, the number is not lucky, and the loop exits.
  8. If none of the above conditions is met, the algorithm reduces the value of n and increments position.
  9. The process repeats until result is determined.
  10. The function then prints whether the number is lucky or not based on the value of result.

Code Solution

Here given code implementation process.

// C program
// Lucky numbers program
#include <stdio.h>

void isLuckyNo(int num)
{
	// Define some auxiliary variables
	int n = num;
	int position = 2;
	int result = 0;
	// Execute the loop until not decide given number is 
	// lucky or not
	while (result == 0)
	{
		if (position > n)
		{
			// When number is Lucky
			result = 1;
		}
		else if ((n % position) == 0)
		{
			// When n is divisible by position
			result = -1;
		}
		else
		{
			// Change n
			n = n - n / position;
			// Increase position
			position++;
		}
	}
	if (result == 1)
	{
		printf(" %d is lucky number\n", num);
	}
	else
	{
		printf(" %d is not lucky number\n", num);
	}
}
int main(int argc, char
	const *argv[])
{
	// Test
	isLuckyNo(9);
	isLuckyNo(1);
	isLuckyNo(21);
	isLuckyNo(13);
	isLuckyNo(1321);
	return 0;
}

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number
// Java program
// Lucky numbers program
// iterative solution
public class LuckyNumber
{
	// Lucky numbers program
	public void isLuckyNo(int num)
	{
		// Define some auxiliary variables
		int n = num;
		int position = 2;
		int result = 0;
		// Execute the loop until not decide given number is 
		// lucky or not
		while (result == 0)
		{
			if (position > n)
			{
				// When number is Lucky
				result = 1;
			}
			else if ((n % position) == 0)
			{
				// When n is divisible by position
				result = -1;
			}
			else
			{
				// Change n
				n = n - n / position;
				// Increase position
				position++;
			}
		}
		if (result == 1)
		{
			System.out.print(" " + num + " is lucky number\n");
		}
		else
		{
			System.out.print(" " + num + " is not lucky number\n");
		}
	}
	public static void main(String[] args)
	{
		LuckyNumber task = new LuckyNumber();
		// Test
		task.isLuckyNo(9);
		task.isLuckyNo(1);
		task.isLuckyNo(21);
		task.isLuckyNo(13);
		task.isLuckyNo(1321);
	}
}

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number
// Include header file
#include <iostream>
using namespace std;

// C++ program
// Lucky numbers program
// iterative solution

class LuckyNumber
{
	public:
		// Lucky numbers program
		void isLuckyNo(int num)
		{
			// Define some auxiliary variables
			int n = num;
			int position = 2;
			int result = 0;
			// Execute the loop until not decide given number is
			// lucky or not
			while (result == 0)
			{
				if (position > n)
				{
					// When number is Lucky
					result = 1;
				}
				else if ((n % position) == 0)
				{
					// When n is divisible by position
					result = -1;
				}
				else
				{
					// Increase position
					// Change n
					n = n - n / position;
					position++;
				}
			}
			if (result == 1)
			{
				cout << " " << num << " is lucky number\n";
			}
			else
			{
				cout << " " << num << " is not lucky number\n";
			}
		}
};
int main()
{
	LuckyNumber task = LuckyNumber();
	// Test
	task.isLuckyNo(9);
	task.isLuckyNo(1);
	task.isLuckyNo(21);
	task.isLuckyNo(13);
	task.isLuckyNo(1321);
	return 0;
}

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number
// Include namespace system
using System;
// C# program
// Lucky numbers program
// iterative solution
public class LuckyNumber
{
	// Lucky numbers program
	public void isLuckyNo(int num)
	{
		// Define some auxiliary variables
		int n = num;
		int position = 2;
		int result = 0;
		// Execute the loop until not decide given number is
		// lucky or not
		while (result == 0)
		{
			if (position > n)
			{
				// When number is Lucky
				result = 1;
			}
			else if ((n % position) == 0)
			{
				// When n is divisible by position
				result = -1;
			}
			else
			{
				// Increase position
				// Change n
				n = n - n / position;
				position++;
			}
		}
		if (result == 1)
		{
			Console.Write(" " + num + " is lucky number\n");
		}
		else
		{
			Console.Write(" " + num + " is not lucky number\n");
		}
	}
	public static void Main(String[] args)
	{
		LuckyNumber task = new LuckyNumber();
		// Test
		task.isLuckyNo(9);
		task.isLuckyNo(1);
		task.isLuckyNo(21);
		task.isLuckyNo(13);
		task.isLuckyNo(1321);
	}
}

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number
<?php
// Php program
// Lucky numbers program
// iterative solution
class LuckyNumber
{
	// Lucky numbers program
	public	function isLuckyNo($num)
	{
		// Define some auxiliary variables
		$n = $num;
		$position = 2;
		$result = 0;
		// Execute the loop until not decide given number is
		// lucky or not
		while ($result == 0)
		{
			if ($position > $n)
			{
				// When number is Lucky
				$result = 1;
			}
			else if (($n % $position) == 0)
			{
				// When n is divisible by position
				$result = -1;
			}
			else
			{
				// Increase position
				// Change n
				$n = $n - intval($n / $position);
				$position++;
			}
		}
		if ($result == 1)
		{
			echo " ". $num ." is lucky number\n";
		}
		else
		{
			echo " ". $num ." is not lucky number\n";
		}
	}
}

function main()
{
	$task = new LuckyNumber();
	$task->isLuckyNo(9);
	$task->isLuckyNo(1);
	$task->isLuckyNo(21);
	$task->isLuckyNo(13);
	$task->isLuckyNo(1321);
}
main();

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number
// Node Js program
// Lucky numbers program
// iterative solution
class LuckyNumber
{
	// Lucky numbers program
	isLuckyNo(num)
	{
		// Define some auxiliary variables
		var n = num;
		var position = 2;
		var result = 0;
		// Execute the loop until not decide given number is
		// lucky or not
		while (result == 0)
		{
			if (position > n)
			{
				// When number is Lucky
				result = 1;
			}
			else if ((n % position) == 0)
			{
				// When n is divisible by position
				result = -1;
			}
			else
			{
				// Increase position
				// Change n
				n = n - parseInt(n / position);
				position++;
			}
		}
		if (result == 1)
		{
			process.stdout.write(" " + num + " is lucky number\n");
		}
		else
		{
			process.stdout.write(" " + num + " is not lucky number\n");
		}
	}
}

function main()
{
	var task = new LuckyNumber();
	// Test
	task.isLuckyNo(9);
	task.isLuckyNo(1);
	task.isLuckyNo(21);
	task.isLuckyNo(13);
	task.isLuckyNo(1321);
}
main();

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number
#  Python 3 program
#  Lucky numbers program
#  iterative solution
class LuckyNumber :
	#  Lucky numbers program
	def isLuckyNo(self, num) :
		#  Define some auxiliary variables
		n = num
		position = 2
		result = 0
		#  Execute the loop until not decide given number is 
		#  lucky or not
		while (result == 0) :
			if (position > n) :
				#  When number is Lucky
				result = 1
			
			elif((n % position) == 0) :
				#  When n is divisible by position
				result = -1
			else :
				#  Change n
				n = n - int(n / position)
				#  Increase position
				position += 1
			
		
		if (result == 1) :
			print(" ", num ," is lucky number")
		else :
			print(" ", num ," is not lucky number")
		
	

def main() :
	task = LuckyNumber()
	#  Test
	task.isLuckyNo(9)
	task.isLuckyNo(1)
	task.isLuckyNo(21)
	task.isLuckyNo(13)
	task.isLuckyNo(1321)

if __name__ == "__main__": main()

Output

  9  is not lucky number
  1  is lucky number
  21  is not lucky number
  13  is lucky number
  1321  is lucky number
#  Ruby program
#  Lucky numbers program
#  iterative solution
class LuckyNumber 
	#  Lucky numbers program
	def isLuckyNo(num) 
		#  Define some auxiliary variables
		n = num
		position = 2
		result = 0
		#  Execute the loop until not decide given number is 
		#  lucky or not
		while (result == 0) 
			if (position > n) 
				#  When number is Lucky
				result = 1
			elsif((n % position) == 0) 
				#  When n is divisible by position
				result = -1
			else 
				#  Change n
				n = n - n / position
				#  Increase position
				position += 1
			end

		end

		if (result == 1) 
			print(" ", num ," is lucky number\n")
		else 
			print(" ", num ," is not lucky number\n")
		end

	end

end

def main() 
	task = LuckyNumber.new()
	#  Test
	task.isLuckyNo(9)
	task.isLuckyNo(1)
	task.isLuckyNo(21)
	task.isLuckyNo(13)
	task.isLuckyNo(1321)
end

main()

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number
// Scala program
// Lucky numbers program
// iterative solution
class LuckyNumber
{
	// Lucky numbers program
	def isLuckyNo(num: Int): Unit = {
		// Define some auxiliary variables
		var n: Int = num;
		var position: Int = 2;
		var result: Int = 0;
		// Execute the loop until not decide given number is
		// lucky or not
		while (result == 0)
		{
			if (position > n)
			{
				// When number is Lucky
				result = 1;
			}
			else if ((n % position) == 0)
			{
				// When n is divisible by position
				result = -1;
			}
			else
			{
				// Increase position
				// Change n
				n = n - (n / position).toInt;
				position += 1;
			}
		}
		if (result == 1)
		{
			print(" " + num + " is lucky number\n");
		}
		else
		{
			print(" " + num + " is not lucky number\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: LuckyNumber = new LuckyNumber();
		// Test
		task.isLuckyNo(9);
		task.isLuckyNo(1);
		task.isLuckyNo(21);
		task.isLuckyNo(13);
		task.isLuckyNo(1321);
	}
}

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number
// Swift 4 program
// Lucky numbers program
// iterative solution
class LuckyNumber
{
	// Lucky numbers program
	func isLuckyNo(_ num: Int)
	{
		// Define some auxiliary variables
		var n: Int = num;
		var position: Int = 2;
		var result: Int = 0;
		// Execute the loop until not decide given number is
		// lucky or not
		while (result == 0)
		{
			if (position > n)
			{
				// When number is Lucky
				result = 1;
			}
			else if ((n % position) == 0)
			{
				// When n is divisible by position
				result = -1;
			}
			else
			{
				// Increase position
				// Change n
				n = n - n / position;
				position += 1;
			}
		}
		if (result == 1)
		{
			print(" ", num ," is lucky number");
		}
		else
		{
			print(" ", num ," is not lucky number");
		}
	}
}
func main()
{
	let task: LuckyNumber = LuckyNumber();
	// Test
	task.isLuckyNo(9);
	task.isLuckyNo(1);
	task.isLuckyNo(21);
	task.isLuckyNo(13);
	task.isLuckyNo(1321);
}
main();

Output

  9  is not lucky number
  1  is lucky number
  21  is not lucky number
  13  is lucky number
  1321  is lucky number
// Kotlin program
// Lucky numbers program
// iterative solution
class LuckyNumber
{
	// Lucky numbers program
	fun isLuckyNo(num: Int): Unit
	{
		// Define some auxiliary variables
		var n: Int = num;
		var position: Int = 2;
		var result: Int = 0;
		// Execute the loop until not decide given number is
		// lucky or not
		while (result == 0)
		{
			if (position > n)
			{
				// When number is Lucky
				result = 1;
			}
			else if ((n % position) == 0)
			{
				// When n is divisible by position
				result = -1;
			}
			else
			{
				// Increase position
				// Change n
				n = n - n / position;
				position += 1;
			}
		}
		if (result == 1)
		{
			print(" " + num + " is lucky number\n");
		}
		else
		{
			print(" " + num + " is not lucky number\n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: LuckyNumber = LuckyNumber();
	// Test
	task.isLuckyNo(9);
	task.isLuckyNo(1);
	task.isLuckyNo(21);
	task.isLuckyNo(13);
	task.isLuckyNo(1321);
}

Output

 9 is not lucky number
 1 is lucky number
 21 is not lucky number
 13 is lucky number
 1321 is lucky number

Resultant Output Explanation

The program tests the isLuckyNo function with different input numbers and prints the output for each case. The output indicates whether each number is a lucky number or not.

Output Explanation for Test Cases

  • 9 is not a lucky number because it gets removed after the filtering process.
  • 1 is a lucky number because it survives the filtering process as the last remaining number.
  • 21 is not a lucky number; it gets removed after the filtering process.
  • 13 is a lucky number; it remains after the filtering process.
  • 1321 is a lucky number; it survives the filtering process.

Time Complexity

The time complexity of the Lucky Numbers program is O(sqrt(n)), where n is the given input number. This complexity arises because the algorithm performs the filtering process until the position variable reaches the square root of the given number. The number of iterations in the loop is proportional to the square root of the input, making the algorithm efficient even for relatively large numbers.

Finally

The Lucky Numbers program determines whether a given number is a lucky number or not by simulating the filtering process through an efficient loop-based algorithm. It offers a clear example of how lucky numbers are defined and demonstrates the algorithm's effectiveness in determining a number's luckiness. With a time complexity of O(sqrt(n)), the program can efficiently handle large input numbers as well.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment