Problem Solving: Exhaustive Search Simulation

Learn to write programs that require brute-force solutions using nested loops.

We'll cover the following

In this lesson, we will practice the nested loops by solving a few problems. Let’s look at the first problem which is about Pythagorean Triples.

Pythagorean Triples

A Pythagorean triple is a set of three positive integers that satisfy the equation, a2+b2=c2a^2 + b^2 = c^2.

Problem statement

Print all Pythagorean triples a, b, c less than 1000. a2+b2=c2a^2 + b^2 = c^2.

In this problem, with the help of loops, we’ll determine the integers (less than 1000) that satisfy the conditions of being Pythagorean triples.

If we think about the logic of solving this problem, it’s pretty straightforward.

For each number (say a), we need to check another number (say b) which, when their squares are added, are equal to the square of the third number (say c).

So we can simply write a for loop for variable a that runs from 0 to 999 (as the question states that all three numbers should be less than 1000). Then inside this loop, we can write another for loop for variable b that runs from 0 to 999. Inside it, we can create another for loop for variable c.

The for loops basically provide us with all the possible combinations of values of a, b, and c, which we can compare to check when the equation is satisfied. We can write an if condition inside our third loop, which compares whether the sum of squares of variables a and b is equal to the square of c.

We then simply print the values of a, b, and c.

Click Run to execute the code below. The program prints all the possible combinations of two numbers that satisfy the equation.

Press + to interact
#include <iostream>
using namespace std;
int main()
{
    int a,b,c;
    for(a=1;a<1000;a++)
    {
        for(b=1;b<1000;b++)
        {
            for(c=1;c<1000;c++)
            {
                if(a*a + b*b == c*c)
                    cout << a << "^2" << " + " << b << "^2" << " = " << c << "^2" << endl;
            }
        }
    }
    return 0;
}

Now we have a question for you. can the above code be optimized in terms of efficiency? Think for a while.

There is indeed a way to optimize our code. We can skip the third inner for loop and instead just check if the result of a2+b2a^2 + b^2 is a perfect square by taking its integer square root r. If it is, then the squared result (r*r) should be equal to a2+b2a^2 + b^2. For example, in the case of a=3, b=4, the value of a2+b2=25a^2+b^2=25, therefore the integer square root will return r=5 and r*r=25, which is equal to a2+b2a^2+b^2. Therefore 3,4 and 5 are Pythagorean triplets. Similarly, if a=3, b=5, then a2+b2=34a^2+b^2=34 and its integer square root r=5 and r*r=25 is not equal to 34. Hence, a Pythagorean triplet is not possible for a=3and b=5.

Press + to interact
#include <iostream>
#include<cmath>
using namespace std;
int integerSquareRoot(int n);
int main()
{
    int a,b,c;
    int result;
    for(a=1;a<1000;a++)
    {
        for(b=1;b<1000;b++)
        {
            int c_sqr = a*a + b*b;
            
            result = integerSquareRoot(c_sqr);
            if (result*result == c_sqr)
            {
                c = result;
                cout << a << "^2" << " + " << b << "^2" 
                     << " = " << c << "^2" << endl;
            }
        }
    }
    return 0;
}
int integerSquareRoot(int n)
{
    int s;
    for(s=0; s*s  <= n;s++)
    {       
     //loop will end when s is one greater than integer square root of n.
    }
    return s-1;   
}

Palindromic numbers

We already know by now that a palindrome is read the same way both backward and forward. Let’s now solve a problem related to it.

Problem statement

The largest palindrome obtained from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

Exercise: Palindromic numbers

Since we already know how to use nested loops, we want you to try and write the solution to this program in the editor below.

You can write the code for 2-digit numbers first and then modify it for 3-digit numbers. For your convenience, we’ve already added the isPalindrome() function that checks whether the number is a palindrome or not.

Press + to interact
#include <iostream>
using namespace std;
//this function returns the reverse of number
int reverse(int num);    
//this function tell the number is palindrome or not
bool isPalindrome(int num);  
 
int main()
{
    // Add code here.
    
}
int reverse(int num)    //reverse function
{
    int rem, m=0;
    while(num!=0)
    {
        rem=num%10;
        m=(m*10)+rem;
        num=num/10;
    }
    return m;
}
bool isPalindrome(int num)    //palindrome function
{
    if(num==reverse(num)) // calling reverse function in condition
    {
        return true;
    }
    return false;
}

To see the solution, click the “Show Solution” button below.

Our code should return 906609 as the largest 3-digit palindrome after multiplying 913 and 993.

Food for thought: Would we get a more efficient code if we reverse both loops and display whichever is the first palindrome pair?

It will not, You can modify the above code and see why it doesn’t give the largest palindrome.

Prime number generator

The expression: n2+n+41n^2 + n + 41 was claimed to be a prime number generator by some math experts.

Problem statement

Disprove the above claim by writing a program that finds the first counterexample on a specific value of n which does not generate a prime number in the above expression.

The equation n2+n+41n^2 + n + 41, as a prime number generator, is one of the finest examples in mathematics. Usually, mathematicians present this problem to students to make them realize that if some claim is true for some values of the initial space (n here), it does not mean it will be true for all values of n. That is why proving it is an essential part, and showing it, for example, when you need to show it for all the universal quantifier cases, is not enough. However, to disprove it is quite simple; show one example where it fails.

Let’s see how we can solve the problem

Idea

Understand the following steps:

  1. Loop through each possibility of n starting from the beginning of the claim for n.
  2. Evaluate the above expression n2+n+41n^2 + n + 41 and store it in answer.
  3. answer should be checked for primality.
  4. If answer is prime, check for the next n.
  5. If answer is not prime, we have found the counterexample.

Exercise: Prime number generator

Try and write the solution to this program in the editor below.

For your convenience, we’ve already added the isPrime() function that checks whether or not a number is a prime number.

Press + to interact
#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(int n);
int main()
{
 // Add code here, by following the below steps
 // 1. You should loop through each possibility of n
 // 2. evaluate on n the above expression n^2 + n + 41 in Answer
 // 3. Answer should be checked for primality 
 // 4. if Answer is prime, check for the next n
 // 5. if Answer is NOT prime, we have found the counter example.
   return 0;
}
bool isPrime(int n)
{
   if (n == 1)
      return false;
   if (n!=2 && n%2==0)
      return false;
   int Limit = sqrt(n);
   for (int d = 3; d <= Limit; d+=2)
   {    
      if (n % d == 0)
         {
            return false;
         }    
   }
   return true;
}

There can be different solutions to this problem. Click the “Show Solution” button to look at one of the potential solutions.

Our code should return 1681 as the first non-prime number (the first counter-example) when n = 40.

Hacker challenge: Circular prime

A number is called a circular prime when all the possible numbers formed from rotations of its digits also make up prime numbers. For example, 197 is a circular prime because all rotations of its digits (197, 971, and 719) are also prime numbers.

Problem statement

There are thirteen circular prime numbers below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97. Which and how many circular primes are there below some number k?

Exercise: Circular prime

Try and write the solution to this program in the editor below.

For your convenience, we’ve already added the functions isPrime() that checks whether the number is a prime number or not and noOfDigits() that counts the number of digits.

Press + to interact
#include <iostream>
//the pow() function is defined in the cmath header file
#include <cmath>
using namespace std;  
bool isPrime(int n);
int noOfDigits(int n);
bool circularPrime(int number);
int main()
{
  int k;
  cout << "Circular primes below the number: " << endl;
  cin >> k;
  // Add code here.  
  return 0;
}
bool isPrime(int n)
{
   if (n == 1)
      return false;
   if (n!=2 && n%2==0)
      return false;
   int Limit = sqrt(n);
   for (int d = 2; d <= Limit; d++)
   {    
      if (n % d == 0)
         {
            return false;
         }    
   }
   return true;
}
int noOfDigits(int n)
{
      int count = 0;
      while (n) 
      {
          count++;   // counting digits
          n /= 10;
      } 
      return count;
}

Enter the input below

Circular primes below 1000 are 25. You can run your program and see what they are. They should include 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97 as the first thirteen circular primes.

There can be different solutions to this problem. Click the “Show Solution” button below to look at one of the potential solutions.