Generating a sequence using prime numbers 2, 3, and 5 only, and then displaying an nth term (C++)

Question

I'm working on a problem that asks to generate a sequence using prime numbers 2, 3, and 5, and then displaying then nth number in the sequence. So, if I ask the program to display the 1000th number, it should display it.

I can't be using arrays or anything like that, just basic decisions and loops.

I started working on it and hit a wall... here's what I got:

#include <iostream>

using namespace std;
int main() {
    unsigned int n=23;
    for(int i=2; i<n; i++){
        if(i%2==0){
            cout<<i<<", ";
        }else if(i%3==0){
            cout<<i<<", ";
        }else if(i%5==0){
            cout<<i<<", ";
        }
    }

    return 0;
}

Unfortunately, that code doesn't do what's required. It displays numbers such as 14, which includes a prime number 7.... The numbers can only be divided by the 3 specified primes (2,3,5).

I found some information that I'm trying to understand, and so far not sure how to implement it... maybe using lots of for() loops? So, it appears I have to use the concept of 2^n * 3^m * 5^k where n+m+k>0.

I guess I have to run a number through a test where it checks to see first if it's fully divisible by 2^1 * 3^0 * 5^0, then 2^0 * 3^1 * 5^0, then 2^0 * 3^0 * 5^1, and so on... Just not sure where to begin.

Answer 1

This is a famous problem, called Hamming's problem after Richard Hamming, and it's covered in the famous book A Discipline of Programming by Dijkstra. Mathematicians call these numbers (if you include 1) 5-smooth numbers, since their prime factorisations only contain primes less than or equal to 5.

What you're supposed to notice is that you can generate the numbers from each other. Here's one way to think about the problem:

#include <set>
#include <iostream>

using namespace std;

int
main()
{
    const unsigned n = 23;

    set<unsigned> s;
    s.insert(2);
    s.insert(3);
    s.insert(5);

    for (unsigned i = 0; i < n; ++i)
    {
        // This returns the smallest element in the set.
        unsigned x = *s.begin();
        cout << x << '\n';

        // Erase the smallest element.
        s.erase(s.begin());

        // Insert the multiples of x.
        s.insert(2*x);
        s.insert(3*x);
        s.insert(5*x);
    }
}

This takes O(n log n) time to print n numbers. It's possible to do it in O(n) time using a similar algorithm, by merging lazy streams. My solution used boost::transform_iterator and boost::iterator_facade, so I wouldn't recommend that for a beginner.

Answer 2

This code will do it. Breaking a problem down into smaller problems is often a good plan.

int main() {
    unsigned int n=23;

    unsigned int counter=0;
    unsigned int answer;
    for ( answer = 2; counter < n; ++answer ) {
        if ( isNotDivisibleByAPrimeGreaterThan5( i ) {
           ++counter;
        }
    }
    cout << answer;
    return 0;
}

Now you only have to write this function.

bool isNotDivisibleByAPrimeGreaterThan5( unsigned int i ) {
  // return true if i is not divisable by a prime greater than 5.
}

Answer 3

#include <type_traits>
#include <utility>
#include <iostream>

template<int... s>
struct seq {};

template<int n, typename seq, typename=void>
struct can_be_factored_into;

template<int n, int first, int... rest>
struct can_be_factored_into< n, seq<first, rest...>, typename std::enable_if< (n > 1) && (n%first) >::type >: can_be_factored_into< n, seq<rest...> > {};

template<int n, int first, int... rest>
struct can_be_factored_into< n, seq<first, rest...>, typename std::enable_if< (n > 1) && !(n%first) >::type >: can_be_factored_into< n/first, seq<first, rest...> > {};

template<int n, int... rest>
struct can_be_factored_into< n, seq<rest...>, typename std::enable_if< n == 1 >::type: std::true_type {};

template<int n>
struct can_be_factored_into< n, seq<>, typename std::enable_if< n != 1 >::type: std::false_type {};

template<int n>
using my_test = can_be_factored_into< n, seq<2,3,5> >;

template<template<int n>class test, int cnt, int start=1, typename=void>
struct nth_element;

template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< (cnt>1)&&test<start>::value >::type >:
  nth_element<test, cnt-1, start+1 > {};

template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< (cnt==1)&&test<start>::value >::type >
  { enum { value = start }; };

template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< !test<start>::value >::type >:
  nth_element<test, cnt, start+1 > {};

int main() {
  std::cout << nth_element< my_test, 1500 >::value << "\n";
}

Once you compile the above code, it will execute in far less than 1 minute.

The downside is that it will blow the compile time recursion limit of most compilers. (this was your daily understatement)

To improve this, nth_element needs to be rewritten to do an exponential blow up search and a divide and conquer within that range. You may also have to modify the code to work with 64 bit values, as the 1500th element of the mentioned sequence might be bigger than 2^32.

Or is having it compile fast also a requirement? :)

And here is a first pass at a Hamming implementation. Not compiled yet:

#include <iostream>
#include <utility>

template<long long... s>
struct seq;

template<long long cnt, typename seq, typename=void>
struct Hamming;

template<long long cnt, long long first, long long... rest>
struct Hamming<cnt, seq<first, rest...>, typename std::enable_if< cnt == 0 >::type> {
  static const long long value = first;
};

template<long long x, typename seq>
struct prepend;
template<long long x, long long... s>
struct prepend<x, seq<s...>>
{
  typedef seq<x, s...> type;
};

template<typename s1, typename s2, typename=void>
struct merge;

template<long long begin_s1, long long... s1, long long begin_s2, long long... s2>
struct merge< seq< begin_s1, s1... >, seq< begin_s2, s2... >, typename std::enable_if< (begin_s1 < begin_s2) >::type > {
  typedef typename prepend< begin_s1, typename merge< seq< s1... >, seq< begin_s2, s2... > >::type >::type type;
};

template<long long begin_s1, long long... s1, long long begin_s2, long long... s2>
struct merge< seq< begin_s1, s1... >, seq< begin_s2, s2... >, typename std::enable_if< (begin_s1 >= begin_s2) >::type > {
  typedef typename prepend< begin_s2, typename merge< seq< begin_s1, s1... >, seq<  s2... > >::type >::type type;
};
template<long long begin_s1, long long... s1>
struct merge< seq< begin_s1, s1... >, seq<>, void > {
  typedef seq< begin_s1, s1... > type;
};
template<long long... s2>
struct merge< seq<>, seq<s2...>, void > {
  typedef seq< s2... > type;
};

template<long long cnt, long long first, long long... rest>
struct Hamming<cnt, seq<first, rest...>, typename std::enable_if< cnt != 0 >::type>:
  Hamming<cnt-1, typename merge< seq<first*2, first*3, first*5>, seq<rest...> >::type >
{};

int main() {
  std::cout << Hamming<1500, seq<1>>::value << "\n";
};

Answer 4

Check this.

#include <iostream>
using namespace std;

int IsPrime(int var);
int CheckifPrimeGreaterThaFive(int Num);
int GetFactors(int Num)
{
    int i =0,j=0;
    for (i =2,j=0; i <= Num; i++)
    {
        if (Num%i == 0)
        {
           if (1 == CheckifPrimeGreaterThaFive(i))
           {
                 return 1;
              }
        }
    }
    return 0;
}

int CheckifPrimeGreaterThaFive(int Num)
{
   if ((Num != 2 && Num != 3 && Num != 5) && IsPrime(Num))
   {

           return 1;
   }

    return 0;
}

int IsPrime(int var)
{
    for (int i = 2; i <= var/2; i++)
    {
        if (var % i == 0)
           return 0;
    }
    return 1;
}


int main() {
    int n=98;
    int i, FactorsCount=0;

    for(i=2; i<n; i++)
    {
        if (0 == GetFactors(i))
        {  
           cout<<" "<<i;
        }   
    }
    return 0;
}