Posted on by Kalkicode
Code Number

Check if a number is Flavius Number

The Flavius number problem is a mathematical puzzle named after the ancient historian Flavius Josephus. The problem involves a sequence of numbers where each term is obtained by removing every nth term from the previous sequence. The objective is to determine whether a given number is part of this sequence or not.

Problem Statement

Given an integer 'number,' we need to check whether it is a Flavius number or not. A Flavius number is one that exists in the sequence obtained by repeatedly removing every nth term from the original sequence, starting from 2.

Explanation with Suitable Example

Let's take an example to understand the Flavius number sequence. Suppose the given number is 20.

  1. The original sequence starts with all integers from 1 to the given number (20 in this case): 1, 2, 3, 4, 5, ..., 20.
  2. We start with 'n' = 2 and remove every 2nd term: 1, X, 3, X, 5, X, ..., 19. (X indicates the removed term)
  3. Next, we update 'n' to 3 and remove every 3rd term from the sequence obtained in the previous step: 1, X, X, X, 5, X, ..., 19.
  4. Continuing this process, we keep updating 'n' and removing every nth term until there is only one term left in the sequence.

In this example, the Flavius number sequence for 20 would be: 1, 5, 7, 11, 13, 17, and 19.

Pseudocode

Below is the pseudocode for the 'isFlavius' function:

isFlavius(number):
    status = 1
    if number < 1:
        status = 0
    n = 2
    series = number
    while status == 1 and n <= series:
        if series is divisible by n:
            status = 0
        else:
            series = series - (series / n)
        n = n + 1
    if status == 1:
        print(number + " is a Flavius Number")
    else:
        print(number + " is Not a Flavius Number")

Algorithm Explanation

  1. The function 'isFlavius' takes an integer 'number' as input and initializes the 'status' variable to 1, which indicates that the number is considered a Flavius number initially.
  2. If the given 'number' is less than 1, it means it does not belong to the Flavius sequence, so the 'status' is set to 0.
  3. We initialize 'n' to 2, which represents the starting term of the sequence to be removed.
  4. We create a variable 'series' and set it equal to the given 'number'. This variable will keep track of the current sequence being evaluated.
  5. We enter a 'while' loop that runs as long as the 'status' is 1 (indicating a potential Flavius number) and 'n' is less than or equal to 'series'.
  6. Within the loop, we check if 'series' is divisible by 'n'. If it is divisible, it means the 'number' cannot be a Flavius number, so we set 'status' to 0.
  7. If 'series' is not divisible by 'n', we remove the nth term by subtracting 'series / n' from 'series'.
  8. We then increment 'n' by 1 to move to the next term to be removed.
  9. Once the loop finishes, we check the final value of 'status'. If it is 1, we print that the 'number' is a Flavius number; otherwise, we print that it is not a Flavius number.

Code Solution

Here given code implementation process.

// C program
// Check if a number is Flavius Number
#include <stdio.h>

// Check whether given number is Flavius Number or not
void isFlavius(int number)
{
	int status = 1;
	if (number < 1)
	{
		status = 0;
	}
	// Start term
	int n = 2;
	// Get number
	int series = number;
	// Check that number exists in given term
	while (status == 1 && n <= series)
	{
		if (series % n == 0)
		{
			status = 0;
		}
		else
		{
			// Remove nth term
			series = series - (series / n);
		}
		// Visit to next term
		n++;
	}
	if (status == 1)
	{
		printf("\n [%d] Is Flavius Number", number);
	}
	else
	{
		printf("\n [%d] Is Not Flavius Number", number);
	}
}
int main()
{
	//Test case
	isFlavius(3);
	isFlavius(6668);
	isFlavius(49);
	return 0;
}

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number
/*
  Java Program 
  Check if a number is Flavius Number
*/
class FlaviusNumber
{
	// Check whether given number is Flavius Number or not
	public void isFlavius(int number)
	{
		boolean status = true;
		if (number < 1)
		{
			status = false;
		}
		// Start term
		int n = 2;
		// Get number
		int series = number;
		// Check that number exists in given term
		while (status == true && n <= series)
		{
			if (series % n == 0)
			{
				status = false;
			}
			else
			{
				// Remove nth term
				series = series - (series / n);
			}
			// Visit to next term
			n++;
		}
		if (status == true)
		{
			System.out.print("\n [" + number + "] Is Flavius Number");
		}
		else
		{
			System.out.print("\n [" + number + "] Is Not Flavius Number");
		}
	}
	public static void main(String[] args)
	{
		FlaviusNumber task = new FlaviusNumber();
		//Test case
		task.isFlavius(3);
		task.isFlavius(6668);
		task.isFlavius(49);
	}
}

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program 
  Check if a number is Flavius Number
*/
class FlaviusNumber
{
	public:
		// Check whether given number is Flavius Number or not
		void isFlavius(int number)
		{
			bool status = true;
			if (number < 1)
			{
				status = false;
			}
			// Start term
			int n = 2;
			// Get number
			int series = number;
			// Check that number exists in given term
			while (status == true && n <= series)
			{
				if (series % n == 0)
				{
					status = false;
				}
				else
				{
					// Remove nth term
					series = series - (series / n);
				}
				// Visit to next term
				n++;
			}
			if (status == true)
			{
				cout << "\n [" << number << "] Is Flavius Number";
			}
			else
			{
				cout << "\n [" << number << "] Is Not Flavius Number";
			}
		}
};
int main()
{
	FlaviusNumber *task = new FlaviusNumber();
	//Test case
	task->isFlavius(3);
	task->isFlavius(6668);
	task->isFlavius(49);
	return 0;
}

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number
// Include namespace system
using System;
/*
  Csharp Program 
  Check if a number is Flavius Number
*/
public class FlaviusNumber
{
	// Check whether given number is Flavius Number or not
	public void isFlavius(int number)
	{
		Boolean status = true;
		if (number < 1)
		{
			status = false;
		}
		// Start term
		int n = 2;
		// Get number
		int series = number;
		// Check that number exists in given term
		while (status == true && n <= series)
		{
			if (series % n == 0)
			{
				status = false;
			}
			else
			{
				// Remove nth term
				series = series - (series / n);
			}
			// Visit to next term
			n++;
		}
		if (status == true)
		{
			Console.Write("\n [" + number + "] Is Flavius Number");
		}
		else
		{
			Console.Write("\n [" + number + "] Is Not Flavius Number");
		}
	}
	public static void Main(String[] args)
	{
		FlaviusNumber task = new FlaviusNumber();
		//Test case
		task.isFlavius(3);
		task.isFlavius(6668);
		task.isFlavius(49);
	}
}

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number
<?php
/*
  Php Program 
  Check if a number is Flavius Number
*/
class FlaviusNumber
{
	// Check whether given number is Flavius Number or not
	public	function isFlavius($number)
	{
		$status = true;
		if ($number < 1)
		{
			$status = false;
		}
		// Start term
		$n = 2;
		// Get number
		$series = $number;
		// Check that number exists in given term
		while ($status == true && $n <= $series)
		{
			if ($series % $n == 0)
			{
				$status = false;
			}
			else
			{
				// Remove nth term
				$series = $series - ((int)($series / $n));
			}
			// Visit to next term
			$n++;
		}
		if ($status == true)
		{
			echo "\n [".$number.
			"] Is Flavius Number";
		}
		else
		{
			echo "\n [".$number.
			"] Is Not Flavius Number";
		}
	}
}

function main()
{
	$task = new FlaviusNumber();
	//Test case
	$task->isFlavius(3);
	$task->isFlavius(6668);
	$task->isFlavius(49);
}
main();

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number
/*
  Node JS Program 
  Check if a number is Flavius Number
*/
class FlaviusNumber
{
	// Check whether given number is Flavius Number or not
	isFlavius(number)
	{
		var status = true;
		if (number < 1)
		{
			status = false;
		}
		// Start term
		var n = 2;
		// Get number
		var series = number;
		// Check that number exists in given term
		while (status == true && n <= series)
		{
			if (series % n == 0)
			{
				status = false;
			}
			else
			{
				// Remove nth term
				series = series - (parseInt(series / n));
			}
			// Visit to next term
			n++;
		}
		if (status == true)
		{
			process.stdout.write("\n [" + number + "] Is Flavius Number");
		}
		else
		{
			process.stdout.write("\n [" + number + "] Is Not Flavius Number");
		}
	}
}

function main()
{
	var task = new FlaviusNumber();
	//Test case
	task.isFlavius(3);
	task.isFlavius(6668);
	task.isFlavius(49);
}
main();

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number
# Python 3 Program
# Check if a number is Flavius Number
class FlaviusNumber :
	# Check whether given number is Flavius Number or not
	def isFlavius(self, number) :
		status = True
		if (number < 1) :
			status = False
		
		n = 2
		series = number
		# Check that number exists in given term
		while (status == True and n <= series) :
			if (series % n == 0) :
				status = False
			else :
				# Remove nth term
				series = series - (int(series / n))
			
			# Visit to next term
			n += 1
		
		if (status == True) :
			print("\n [", number ,"] Is Flavius Number", end = "")
		else :
			print("\n [", number ,"] Is Not Flavius Number", end = "")
		
	

def main() :
	task = FlaviusNumber()
	# Test case
	task.isFlavius(3)
	task.isFlavius(6668)
	task.isFlavius(49)

if __name__ == "__main__": main()

input

 [ 3 ] Is Flavius Number
 [ 6668 ] Is Not Flavius Number
 [ 49 ] Is Flavius Number
# Ruby Program
# Check if a number is Flavius Number
class FlaviusNumber 
	# Check whether given number is Flavius Number or not
	def isFlavius(number) 
		status = true
		if (number < 1) 
			status = false
		end

		# Start term
		n = 2
		# Get number
		series = number
		# Check that number exists in given term
		while (status == true && n <= series) 
			if (series % n == 0) 
				status = false
			else 
				# Remove nth term
				series = series - (series / n)
			end

			# Visit to next term
			n += 1
		end

		if (status == true) 
			print("\n [", number ,"] Is Flavius Number")
		else 
			print("\n [", number ,"] Is Not Flavius Number")
		end

	end

end

def main() 
	task = FlaviusNumber.new()
	# Test case
	task.isFlavius(3)
	task.isFlavius(6668)
	task.isFlavius(49)
end

main()

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number
/*
  Scala Program 
  Check if a number is Flavius Number
*/
class FlaviusNumber()
{
	// Check whether given number is Flavius Number or not
	def isFlavius(number: Int): Unit = {
		var status: Boolean = true;
		if (number < 1)
		{
			status = false;
		}
		// Start term
		var n: Int = 2;
		// Get number
		var series: Int = number;
		// Check that number exists in given term
		while (status == true && n <= series)
		{
			if (series % n == 0)
			{
				status = false;
			}
			else
			{
				// Remove nth term
				series = series - ((series / n).toInt);
			}
			// Visit to next term
			n += 1;
		}
		if (status == true)
		{
			print("\n [" + number + "] Is Flavius Number");
		}
		else
		{
			print("\n [" + number + "] Is Not Flavius Number");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: FlaviusNumber = new FlaviusNumber();
		//Test case
		task.isFlavius(3);
		task.isFlavius(6668);
		task.isFlavius(49);
	}
}

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number
/*
  Swift 4 Program 
  Check if a number is Flavius Number
*/
class FlaviusNumber
{
	// Check whether given number is Flavius Number or not
	func isFlavius(_ number: Int)
	{
		var status: Bool = true;
		if (number < 1)
		{
			status = false;
		}
		// Start term
		var n: Int = 2;
		// Get number
		var series: Int = number;
		// Check that number exists in given term
		while (status == true && n <= series)
		{
			if (series % n == 0)
			{
				status = false;
			}
			else
			{
				// Remove nth term
				series = series - (series / n);
			}
			// Visit to next term
			n += 1;
		}
		if (status == true)
		{
			print("\n [", number ,"] Is Flavius Number", terminator: "");
		}
		else
		{
			print("\n [", number ,"] Is Not Flavius Number", terminator: "");
		}
	}
}
func main()
{
	let task: FlaviusNumber = FlaviusNumber();
	//Test case
	task.isFlavius(3);
	task.isFlavius(6668);
	task.isFlavius(49);
}
main();

input

 [ 3 ] Is Flavius Number
 [ 6668 ] Is Not Flavius Number
 [ 49 ] Is Flavius Number
/*
  Kotlin Program 
  Check if a number is Flavius Number
*/
class FlaviusNumber
{
	// Check whether given number is Flavius Number or not
	fun isFlavius(number: Int): Unit
	{
		var status: Boolean = true;
		if (number < 1)
		{
			status = false;
		}
		// Start term
		var n: Int = 2;
		// Get number
		var series: Int = number;
		while (status == true && n <= series)
		{
			if (series % n == 0)
			{
				status = false;
			}
			else
			{
				// Remove nth term
				series = series - (series / n);
			}
			// Visit to next term
			n += 1;
		}
		if (status == true)
		{
			print("\n [" + number + "] Is Flavius Number");
		}
		else
		{
			print("\n [" + number + "] Is Not Flavius Number");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: FlaviusNumber = FlaviusNumber();
	//Test case
	task.isFlavius(3);
	task.isFlavius(6668);
	task.isFlavius(49);
}

input

 [3] Is Flavius Number
 [6668] Is Not Flavius Number
 [49] Is Flavius Number

Resultant Output Explanation

Now, let's analyze the outputs for the given test cases:

  1. isFlavius(3): The Flavius sequence starting from 2 is 1, 3. Since the number 3 is present in this sequence, the output will be "[3] Is Flavius Number."
  2. isFlavius(6668): The Flavius sequence starting from 2 is 1, 5, 7, 11, ..., 3333, 3335, 3339, 3341, 4998, 5002, 5004, 5008, ..., 6665. The number 6668 is not part of this sequence, so the output will be "[6668] Is Not Flavius Number."
  3. isFlavius(49): The Flavius sequence starting from 2 is 1, 5, 7, ..., 21, 23, 27, 29, ..., 39, 41, 45, 47. The number 49 is present in this sequence, so the output will be "[49] Is Flavius Number."

Time Complexity of the Code

The time complexity of the 'isFlavius' function can be analyzed as follows:

  • The loop runs as long as 'n' is less than or equal to 'series', which means it runs approximately 'series / 2' times on average.
  • Inside the loop, basic operations like checking divisibility and subtracting numbers take constant time.
  • Therefore, the overall time complexity of the 'isFlavius' function is O(N), where N is the given 'number'.

Finally

The Flavius number problem involves generating a sequence of numbers by removing every nth term from the previous sequence. We have discussed the problem statement, explained it with a suitable example, provided the pseudocode and algorithm for checking whether a given number is a Flavius number or not, and analyzed the time complexity of the code. The function 'isFlavius' can be used to determine whether a number belongs to the Flavius sequence or not, providing a solution to this interesting mathematical puzzle.

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