6
\$\begingroup\$

I have written a program to print Brown numbers from Brocard's problem. I want to improve the code.

Brocard's problem is a problem in mathematics that asks to find integer values of n and m for which

n ! + 1 = m^2 

where n! is the factorial.

Pairs of the numbers (n, m) that solve Brocard's problem are called Brown numbers. There are only three known pairs of Brown numbers:

(4,5), (5,11), and (7,71).
#include <iostream>

unsigned int factorial(unsigned int num)
{
  unsigned int result = 1;
  for(unsigned int i = 1; i <= num; i++)
  {
    result = result*i;
  }
  return result;
}

void print_brown_numbers(int limit)
{
  for(unsigned int i = 2; i <= limit; i++)
  {
    for(unsigned int j = 1; j < i; j++)
    {
      if((i * i) == (factorial(j) + 1))
      {
        std::cout << i << " " << j << " are brown numbers\n";
      }
    }
  }
}

int main()
{
  unsigned int max_limit;
  std::cout << "Enter the maximum limit for you want to test \n";
  std::cin >> max_limit;
  print_brown_numbers(max_limit);
}
\$\endgroup\$
2
  • \$\begingroup\$ Swap the for cycles, don't use at all the factorial function, find a smarter way to iterate through squares. \$\endgroup\$ – N74 Jan 23 '18 at 22:20
  • 2
    \$\begingroup\$ I probably ought to point out that if there exist an n larger than 7, it's known it must be greater than 10¹², and int is unlikely to be adequate to represent n!. \$\endgroup\$ – Toby Speight Jan 24 '18 at 9:40
4
\$\begingroup\$

This is a pretty good brute-force way to find these numbers. It will obviously be slow because of it's brute-force, but it's easy to read and understand, which is always a plus! Here are some ways you could improve it.

Don't Try All Combinations

Once you've calculated a factorial, it's pretty easy to add 1 to it and determine if it's a perfect square. I would write a function called is_perfect_square() that looks like this:

bool is_perfect_square(const int x)
{
    double square = static_cast<double>(x);
    double root = sqrt(square);
    return root == std::round(root);
}

Now you can simply do this:

void print_brown_numbers(int limit)
{
    for (unsigned int i = 2; i <= limit; ++i)
    {
        unsigned int fact = factorial(i);
        if (is_perfect_square (fact + 1))
        {
            std::cout << sqrt(fact + 1) << " " << i << " are brown numbers\n";
        }
    }
}

Note that in my version, the limit is the limit of the factorial, not the square, so it works slightly differently.

Error Handling

Most compilers will use 32-bits for an int or an unsigned int these days. Factorials can get very large very quickly. 12! is the largest factorial a 32-bit int or unsigned int can hold. You should check your inputs to make sure you won't get an overflow and let the user enter a different one if it would.

Types

You're mixing signed and unsigned types. While there's nothing wrong with your math, you're leaving 1 bit (so half the range - 2 billion values) on the table for the square. It will never be negative, so you should just make it unsigned to begin with. (Or make the factorial signed. Either way is fine given the maximum values.)

\$\endgroup\$
2
  • \$\begingroup\$ Good advice. Additionally, the factorial doesn't need to be calculated from scratch on each iteration - (n+1)! is a single multiplication when you already have n!. \$\endgroup\$ – Toby Speight Jan 24 '18 at 9:33
  • \$\begingroup\$ Excellent point! And for 32-bit values, you can just make a table of 13 values, too. \$\endgroup\$ – user1118321 Jan 24 '18 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.