fbpx

C++: Ludic Numbers

Bjarne-stroustrup
 


Ludic numbers are related to prime numbers as they are generated by a sieve quite like the Sieve of Eratosthenes is used to generate prime numbers.

The first ludic number is 1.
To generate succeeding ludic numbers create an array of increasing integers starting from 2

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ...

(Loop)

  • Take the first member of the resultant array as the next Ludic number 2.
  • Remove every 2’nd indexed item from the array (including the first).
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ...
  • (Unrolling a few loops…)
  • Take the first member of the resultant array as the next Ludic number 3.
  • Remove every 3’rd indexed item from the array (including the first).
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 ...
  • Take the first member of the resultant array as the next Ludic number 5.
  • Remove every 5’th indexed item from the array (including the first).
5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 ...
  • Take the first member of the resultant array as the next Ludic number 7.
  • Remove every 7’th indexed item from the array (including the first).
7 11 13 17 23 25 29 31 37 41 43 47 53 55 59 61 67 71 73 77 83 85 89 91 97 ...
  • Take the first member of the current array as the next Ludic number L.
  • Remove every L’th indexed item from the array (including the first).
Task
  • Generate and show here the first 25 ludic numbers.
  • How many ludic numbers are there less than or equal to 1000?
  • Show the 2000..2005’th ludic numbers.
  • A triplet is any three numbers x, x + 2, x + 6 where all three numbers are also ludic numbers. Show all triplets of ludic numbers < 250 (Stretch goal)

#include <vector>
#include <iostream>
using namespace std;
 
class ludic
{
public:
    void ludicList()
    {
        _list.push_back( 1 );
 
        vector<int> v;
        for( int x = 2; x < 22000; x++ )
            v.push_back( x );
 
        while( true )
        {
            vector<int>::iterator i = v.begin();
            int z = *i;
            _list.push_back( z );
 
            while( true )
            {
                i = v.erase( i );
                if( distance( i, v.end() ) <= z - 1 ) break;
                advance( i, z - 1 );
            }
            if( v.size() < 1 ) return;
        }
    }
 
    void show( int s, int e )
    {
        for( int x = s; x < e; x++ )
            cout << _list[x] << " ";
    }
 
    void findTriplets( int e )
    {
        int lu, x = 0;
        while( _list[x] < e )
        {
            lu = _list[x];
            if( inList( lu + 2 ) && inList( lu + 6 ) )
                cout << "(" << lu << " " << lu + 2 << " " << lu + 6 << ")\n";
            x++;
        }
    }
 
    int count( int e )
    {
        int x = 0, c = 0;
        while( _list[x++] <= 1000 ) c++;
        return c;
    }
 
private:
    bool inList( int lu )
    {
        for( int x = 0; x < 250; x++ )
            if( _list[x] == lu ) return true;
        return false;
    }
 
    vector<int> _list;
};
 
int main( int argc, char* argv[] )
{
    ludic l;
    l.ludicList();
    cout << "first 25 ludic numbers:" << "\n";
    l.show( 0, 25 );
    cout << "\n\nThere are " << l.count( 1000 ) << " ludic numbers <= 1000" << "\n";
    cout << "\n2000 to 2005'th ludic numbers:" << "\n";
    l.show( 1999, 2005 );
    cout << "\n\nall triplets of ludic numbers < 250:" << "\n";
    l.findTriplets( 250 );
    cout << "\n\n";
    return system( "pause" );
}
Output:
first 25 ludic numbers:
1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 107

There are 142 ludic numbers <= 1000

2000 to 2005'th ludic numbers:
21475 21481 21487 21493 21503 21511

all triplets of ludic numbers < 250:
(1 3 7)
(5 7 11)
(11 13 17)
(23 25 29)
(41 43 47)
(173 175 179)
(221 223 227)
(233 235 239)

SOURCE

Content is available under GNU Free Documentation License 1.2.