Check which numbers satisfy the condition [A*B*C = A! + B! + C!]

Question

#include <iostream>
#include <cmath>
using namespace std;
int s = 1; //Serial No.

Should I use recursion for the factorials function?

int Factorial(int n)
{
    int k=1;
    for(int i=1;i<=n;++i)
    {
        k=k*i;
    }
    return k;
}

How I can go about doing this in a single for loop instead of the 3 while loops?

int main()
{
    int a = 1;
    int b = 1;
    int c = 1;
    int Fact1;
    int Fact2;
    int Fact3;
    while (a < 11)
    {
        Fact1 = Factorial(a);
        while (b < 11)
        {
            Fact2 = Factorial(b);
            while (c < 11)
            {
                Fact3 = Factorial(c);
                cout << s << " : ";
                int LHS = Fact1 + Fact2 + Fact3;
                if (LHS == a * b * c)
                {
                    cout << "Pass:" <<"    "<< a << " & " << b << " & " << c << endl;
                }
                else
                {
                    cout << "Fail" /*<<"   "<< Fact1 <<"   "<< Fact2 <<"   "<<Fact3*/<<endl;
                }
                    c++;
                    s++;
            }
            c = 1;
            b++;
        }
        b = 1;
        a++;
    }
    return 0;
}

Also I would love some variable naming tips.

Answer 1

Hello and welcome to Code Review.

Surprisingly, a, b, and c are probably the best variable names you can come up with. They are conventionally given as canonical examples of bad names, but when the task is to implement a mathematical function using the same variable names as in the spec is more important.

As to the single loop question, the short answer is "not easily". You are trying to check all combinations of three independently varying things. That means you naturally want three loops, and anything else would lose out on readability.

---

Aside from your questions, I have a few observations about this code that might be worth fixing.

• When you have a loop that is counting up to something, it is convention to prefer a for loop to a while loop.
• Factorial is what is known as a "pure function" which means that its output only depends on its input. Such functions within loops are often good candidates for caching so that you don't have to waste time calculating the same output a hundred and eleven times for each input number.
• Both + and * are commutative, which means that if a, b, and c pass then b, a, and c also pass. You should check whether you need to display all reorderings of the same sets of numbers.
• It is unclear where 11 has come from. It seems like a magic number, which would benefit from being moved to a named constant and having a comment explaining why that value is used.

Answer 2

Avoid using namespace std. It doesn't even save any typing in this program.

serialNumber doesn't need to be global.

Consider using unsigned types for numbers when negatives can't be present.

Whilst there's nothing wrong with the factorial function (and I certainly wouldn't recommend making it recursive), we can skip the i==1 iteration:

constexpr unsigned int factorial(unsigned int n)
{
    unsigned int k = 1;
    for (unsigned int i = 2u;  i <= n;  ++i) {
        k *= i;
    }
    return k;
}

Note that we need to be very careful with our inputs to avoid overflow here. With a 16-bit int, we can compute factorials only up to 8!, and with 32-bit int, a maximum of 12!. Consider throwing a std::range_error when the output is too large to represent:

#include <limits>
#include <stdexcept>

constexpr unsigned int factorial(unsigned int n)
{
    unsigned int k = 1;
    for (unsigned int i = 2u;  i <= n;  ++i) {
        if (k >= std::numeric_limits<decltype(k)>::max() / n) {
            throw std::range_error("factorial");
        }
        k *= i;
    }
    return k;
}

Reduce scope of variables, and keep the names of related variables obviously connected; i.e. instead of using numbers for the factorials, include a, b or c in their names (e.g. fa, fb, fc).

We can reduce the search space by limiting the loops so that we don't repeat tests so much (given that both operations are commutative):

for (unsigned a = 1;  a < 11;  ++a)
{
    auto const fa = factorial(a);
    for (unsigned b = 1;  b <= a;  ++b)
    {
        auto const fb = factorial(b);
        for (unsigned c = 1;  c <= b;  ++c)
        {
            auto const fc = factorial(c);

Notice how the inner loops reach but don't exceed the current value of the containing loop.

Prefer '\n' to std::endl when there's no need to flush the output immediately (in fact, when a newline and flush are both needed, I prefer to write << '\n' << std::flush to be absolutely clear what we want).

---

Modified code

#include <iostream>
#include <limits>
#include <stdexcept>

constexpr unsigned int factorial(unsigned int n)
{
    unsigned int k = 1;
    for (unsigned int i = 2u;  i <= n;  ++i) {
        if (k >= std::numeric_limits<decltype(k)>::max() / n) {
            throw std::range_error("factorial");
        }
        k *= i;
    }
    return k;
}

int main()
{
    for (unsigned a = 1;  a < 11;  ++a) {
        auto const fa = factorial(a);
        for (unsigned b = 1;  b <= a;  ++b) {
            auto const fb = factorial(b);
            for (unsigned c = 1;  c <= b;  ++c) {
                auto const fc = factorial(c);
                if (fa + fb + fc == a * b * c) {
                    std::cout << "Pass:" << "    "
                              << a << " & " << b << " & " << c
                              << '\n';
                }
            }
        }
    }
}

---

Exercise

What would you change to extend this to search for N numbers whose product equals the sum of their factorials, when N is given at run time?

Answer 3

A couple of remarks in addition to Josiah's answer:

• While I agree that the variable names a, b and c are fine when implementing mathy functions that can be concisely described with these identifiers, this doesn't apply to the counter s. I am not totally sure what it does, but

  int s = 1; //Serial No.
  

  makes me think that

  int serialNumber = 1;
  

  would be a better approach.

• Try to be consistent in your naming, you have some names that start with an upper case and some that start with a lower case. Instead, pick one scheme and stick to it.

• Keep the scope of your variables as small as possible.

  int Fact1;
  int Fact2;
  int Fact3;
  

  They can all be moved into the loop body and be initialized upon their declaration. This doesn't make the exist unitialized, which is desireable.

• When you don't intend to modify a variable, const-qualify it:

  const int LHS = Fact1 + Fact2 + Fact3;
  

• If you intend to enlarge the 11 constant at some point, note that factorials might get quite large. Maybe check (if the limit is known at compile time via a static_assert) that Fact1, Fact2 and Fact3 as well as the sum of it can't overflow?

• I don't see any use of functions that come from

  #include <cmath>
  

  so you might want to remove this line.

Answer 4

Don't forget testability

As no other answer has mentioned this - I feel it's worth pointing out by itself.

In your current example, you are writing the results directly to stdout as soon as they are found. This works well for toy examples, and as it gives you the output you desire - it's often an easy habit to get into.

However, doing it this way requires a human to verify and test the output each time a change is made.

Instead of writing results directly to stdout; try to separate the business logic from the output itself. That is, write the logic in a function which returns the results. In this specific case, you may want to return a list/vector of structs, representing each result as calculated:

   struct Result {  
       bool success;  
       int input_a;  
       int input_b;  
       int input_c;  
       int calculated_abc;  
       int calculated_fa_fb_fc_total;     
    };

Once separate, you'll have a function that can be run by "other code" (such as in a test framework), allowing you to write automated tests that check this code is always correct for a given set of inputs.

Answer 5

The code as presented suffers from an algorithmic problem known as The Algorithm of Shlemiel the Painter. For example, after calculating 5! = 120 and going on to calculate 6!, the Factorial function has to determine 1×2×3×4×5×6, even though it has just been calculated what the product of the first five terms is. Not particularly important in this particular case because the numbers involved are so small, but it’s still something to be kept in mind. To address this concern, storing the last value of the factorial is helpful as then a single multiplication operation suffices to find out the new value.

Additionally, because the expression is symmetric, it’s only necessary to look for solutions where a ≥ b ≥ c. All other solutions will be permutations of what was found.

With that in mind, the code can be simplified just to this:

#include <iostream>

int main()
{
    int const MAX = 11;
    for(int a = 0, af = 1; a < MAX; af *= ++a)
    {
        for(int b = 0, bf = 1; b <= a; bf *= ++b)
        {
            for(int c = 0, cf = 1; c <= b; cf *= ++c)
            {
                if(af + bf + cf == a * b * c)
                {
                    std::cout << "a: " << a << std::endl;
                    std::cout << "b: " << b << std::endl;
                    std::cout << "c: " << c << std::endl;
                    std::cout << std::endl;
                }
            }
        }
    }

A more advanced technique would be to factor out the generation of the factorial sequence. Alas, without C++20 coroutines it’s clumsy. The main function becomes very pretty and clear:

int main()
{
    int const MAX = 11;
    for(auto [a, af] : factorials_upto{MAX})
    {
        for(auto [b, bf] : factorials_upto{a + 1})
        {
            for(auto [c, cf] : factorials_upto{b + 1})
            {
                if(af + bf + cf == a * b * c)
                {
                    std::cout << "a: " << a << std::endl;
                    std::cout << "b: " << b << std::endl;
                    std::cout << "c: " << c << std::endl;
                    std::cout << std::endl;
                }
            }
        }
    }
}

but the code enabling that is less so:

#include <tuple>

class factorial_iterator
{
public:
    factorial_iterator(int value): m_value{value}, m_product{1}
    {
    }

    std::tuple<int, int> operator *() const
    {
        return { m_value, m_product };
    }

    factorial_iterator& operator ++()
    {
        m_product *= ++m_value;

        return *this;
    }

    bool operator !=(factorial_iterator const& other) const
    {
        return m_value != other.m_value;
    }

private:
    int m_value;
    int m_product;
};

struct factorials_upto
{
    int m_end;

    friend factorial_iterator begin(factorials_upto const &)
    {
        return {0};
    }

    friend factorial_iterator end(factorials_upto const& fu)
    {
        return {fu.m_end};
    }
};