Ludic numbers are obtained by considering list of natural numbers (starting from 2) and removing i-th number in i-th iteration (where i begins with 2). In every iteration, the first removed number is Ludic. 1 is considered as Ludic.
Process of generating Ludic numbers :
Ludic = {1, …}
Consider natural numbers from 2,
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 …Delete every 2nd number because first number is 2
3, 5, 7, 9, 11, 13, 15, 17, 19, 21 ..
Ludic = {1, 2, …}Delete every 3rd number because first number is 3
5, 7, 11, 13, 17, 19, 22 ..Ludic = {1, 2, 3, …}
Delete every 5th number because first number is 5
5, 7, 11, 13, 17, 19, 22 ..Ludic = {1, 2, 3, 5, ..}
This process continues..
The process is similar to the Sieve of Eratosthenes.
Given a number n, print all Ludic numbers smaller than or equal to n.
Examples :
Input : n = 10 Output : 1, 2, 3, 5, 7 Input : n = 25 Output : 1, 2, 3, 5, 7, 11, 13, 17, 23, 25
The idea to print Ludic Numbers is simple. We create a list of sizes and use the above-illustrated process. In each iteration, we delete every i-th number, we do not delete the current first number so that we can return it later.
C++
// C++ code to print Ludic // number smaller than or // equal to n. #include <bits/stdc++.h>using namespace std;// Returns a list containing // all Ludic numbers smaller // than or equal to n. vector<int> getLudic(int n) { // ludics list contain all // the ludic numbers vector<int> ludics; for (int i = 1; i <= n; i++) ludics.push_back(i); // Here we have to start with // index 1 and will remove nothing // from the list for (int index = 1; index < ludics.size(); index++) { // Here first item should be included in the list // and the deletion is referred by this first item // in the loop . int first_ludic = ludics[index]; // Remove_index variable is used to store // the next index which we want to delete int remove_index = index + first_ludic; while (remove_index < ludics.size()) { // Removing the next item auto it = ludics.begin(); it = it + remove_index; ludics.erase(it); // Remove_index is updated so that // we get the next index for deletion remove_index = remove_index + first_ludic - 1; } } return ludics; } // Driver codeint main(){ int n = 25; vector<int> ans = getLudic(n); cout << "["; for (int i = 0; i < ans.size() - 1; i++) { cout << ans[i] << ", "; } cout << ans[ans.size() - 1] << "]"; return 0;}// This code is contributed by divyeshrabadiya07 |
Java
// Java code to print Ludic number smaller than// or equal to n.import java.util.ArrayList;import java.util.List;public class Ludic { // Returns a list containing all Ludic numbers // smaller than or equal to n. public static List<Integer> getLudic(int n) { // ludics list contain all the ludic numbers List<Integer> ludics = new ArrayList<Integer>(n); for (int i = 1; i <= n; i++) ludics.add(i); // Here we have to start with index 1 and will remove nothing // from the list for (int index = 1; index < ludics.size(); index++) { // Here first item should be included in the list // and the deletion is referred by this first item // in the loop . int first_ludic = ludics.get(index); // remove_index variable is used to store // the next index which we want to delete int remove_index = index + first_ludic; while (remove_index < ludics.size()) { // removing the next item ludics.remove(remove_index); // remove_index is updated so that // we get the next index for deletion remove_index = remove_index + first_ludic - 1; } } return ludics; } public static void main(String[] srgs) { int n = 25; System.out.println(getLudic(n)); }} |
Python3
# Python3 code to print Ludic # number smaller than or equal # to n.# Returns a list containing all # Ludic numbers smaller than # or equal to n.def getLudic(n): # ludics list contain all # the ludic numbers ludics = [] for i in range(1, n + 1): ludics.append(i) # Here we have to start with # index 1 and will remove # nothing from the list index = 1 while(index != len(ludics)): # Here first item should be # included in the list and # the deletion is referred # by this first item # in the loop . first_ludic = ludics[index] # Remove_index variable is used # to store the next index which # we want to delete remove_index = index + first_ludic while(remove_index < len(ludics)): # Removing the next item ludics.remove(ludics[remove_index]) # Remove_index is updated so that # we get the next index for deletion remove_index = remove_index + first_ludic - 1 index += 1 return ludics# Driver code n = 25print(getLudic(n))# This code is contributed by avanitrachhadiya2155 |
C#
// C# code to print Ludic number smaller// than or equal to n. using System; using System.Collections;class GFG{ // Returns a list containing all Ludic// numbers smaller than or equal to n. public static ArrayList getLudic(int n) { // ludics list contain all the // ludic numbers ArrayList ludics = new ArrayList(); for(int i = 1; i <= n; i++) ludics.Add(i); // Here we have to start with index 1 // and will remove nothing from the list for(int index = 1; index < ludics.Count; index++) { // Here first item should be included // in the list and the deletion is // referred by this first item in the // loop . int first_ludic = (int)ludics[index]; // remove_index variable is used to store // the next index which we want to delete int remove_index = index + first_ludic; while (remove_index < ludics.Count) { // Removing the next item ludics.Remove(ludics[remove_index]); // remove_index is updated so that // we get the next index for deletion remove_index = remove_index + first_ludic - 1; } } return ludics; } // Driver code public static void Main(string[] srgs) { int n = 25; ArrayList tmp = getLudic(n); Console.Write("["); foreach(int x in tmp) { Console.Write(x + ", "); } Console.Write("]");} } // This code is contributed by rutvik_56 |
Javascript
<script>// Javascript code to print Ludic number smaller than// or equal to n.// Returns a list containing all Ludic numbers // smaller than or equal to n.function getLudic(n){ // ludics list contain all the ludic numbers let ludics = []; for (let i = 1; i <= n; i++) ludics.push(i); // Here we have to start with index 1 and will remove nothing // from the list for (let index = 1; index < ludics.length; index++) { // Here first item should be included in the list // and the deletion is referred by this first item // in the loop . let first_ludic = ludics[index]; // remove_index variable is used to store // the next index which we want to delete let remove_index = index + first_ludic; while (remove_index < ludics.length) { // removing the next item ludics.splice(remove_index,1); // remove_index is updated so that // we get the next index for deletion remove_index = remove_index + first_ludic - 1; } } return ludics;}let n = 25;document.write(getLudic(n));// This code is contributed by unknown2108.</script> |
Output:
[1, 2, 3, 5, 7, 11, 13, 17, 23, 25]
Time complexity: O(n) where n is count of numbers to be generated
Auxiliary Space : O(n)
References :
https://oeis.org/wiki/Ludic_numbers
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
