Solutions
1. Sum of naturals divisible by 3 and 5
The solution to this problem is to iterate through all numbers from 3 (1 and 2 are not divisible by 3 so it does not make sense to test them) up to the limit entered by the user. Use the modulo operation to check that the rest of the division of a number by 3 and 5 is 0. However, the trick to being able to sum up to a larger limit is to use long long and not int or long for the sum, which would result in an overflow before summing up to 100,000:
int main()
{
unsigned int limit = 0;
std::cout << "Upper limit:";
std::cin >> limit;
unsigned long long sum = 0;
for (unsigned int i = 3; i < limit; ++i)
{
if (i % 3 == 0 || i % 5 == 0)
sum += i;
}
std::cout << "sum=" << sum << std::endl;
}
2. Greatest common divisor
The greatest common divisor (gcd in short) of two or more non-zero integers, also known as the greatest common factor (gcf), highest common factor (hcf), greatest common measure (gcm), or highest common divisor, is the greatest positive integer that divides all of them. There are several ways the gcd could be computed; an efficient method is Euclid's algorithm. For two integers, the algorithm is:
gcd(a,0) = a
gcd(a,b) = gcd(b, a mod b)
This can be very simply implemented in C++ using a recursive function:
unsigned int gcd(unsigned int const a, unsigned int const b)
{
return b == 0 ? a : gcd(b, a % b);
}
A non-recursive implementation of Euclid's algorithm should look like this:
unsigned int gcd(unsigned int a, unsigned int b)
{
while (b != 0) {
unsigned int r = a % b;
a = b;
b = r;
}
return a;
}
3. Least common multiple
The least common multiple (lcm) of two or more non-zero integers, also known as the lowest common multiple, or smallest common multiple, is the smallest positive integer that is divisible by all of them. A possible way to compute the least common multiple is by reducing the problem to computing the greatest common divisor. The following formula is used in this case:
lcm(a, b) = abs(a, b) / gcd(a, b)
A function to compute the least common multiple may look like this:
int lcm(int const a, int const b)
{
int h = gcd(a, b);
return h ? (a * (b / h)) : 0;
}
To compute the lcm for more than two integers, you could use the std::accumulate algorithm from the header <numeric>:
template<class InputIt>
int lcmr(InputIt first, InputIt last)
{
return std::accumulate(first, last, 1, lcm);
}
4. Largest prime smaller than given number
A prime number is a number that has only two divisors, 1 and the number itself. To find the largest prime smaller than a given number you should first write a function that determines if a number is prime and then call this function, starting from the given number, towards 1 until the first prime is encountered. There are various algorithms for determining if a number is prime. Common implementations for determining the primality appear as follows:
bool is_prime(int const num)
{
if (num <= 3) { return num > 1; }
else if (num % 2 == 0 || num % 3 == 0)
{
return false;
}
else
{
for (int i = 5; i * i <= num; i += 6)
{
if (num % i == 0 || num % (i + 2) == 0)
{
return false;
}
}
return true;
}
}
This function can be used as follows:
int main()
{
int limit = 0;
std::cout << "Upper limit:";
std::cin >> limit;
for (int i = limit; i > 1; i--)
{
if (is_prime(i))
{
std::cout << "Largest prime:" << i << std::endl;
return 0;
}
}
}
5. Sexy prime pairs
Sexy prime numbers are prime numbers that differ from each other by six (for example 5 and 11, or 13 and 19). There are also twin primes, which differ by two, and cousin primes, which differ by four.
In the previous challenge, we implemented a function that determines whether an integer is a prime number. We will reuse that function for this exercise. What you have to do is check that if a number n is prime, the number n+6 is also prime, and in this case print the pair to the console:
int main()
{
int limit = 0;
std::cout << "Upper limit:";
std::cin >> limit;
for (int n = 2; n <= limit; n++)
{
if (is_prime(n) && is_prime(n+6))
{
std::cout << n << "," << n+6 << std::endl;
}
}
}
You could take it as a further exercise to compute and displays the sexy prime triples, quadruplets, and quintuplets.
6. Abundant numbers
An abundant number, also known as an excessive number, is a number for which the sum of its proper divisors is greater than the number itself. The proper divisors of a number are the positive prime factors of the number, other than the number itself. The amount by which the sum of proper divisors exceeds the number itself is called abundance. For instance, the number 12 has the proper divisors 1, 2, 3, 4, and 6. Their sum is 16, which makes 12 an abundant number. Its abundance is 4 (that is, 16 - 12).
To determine the sum of proper divisors, we try all numbers from 2 to the square root of the number (all prime factors are less than or equal to this value). If the current number, let’s call it i, divides the number, then i and num/i are both divisors. However, if they are equal (for example, if i = 3, and n = 9, then i divides 9, but n/i = 3), we add only i because proper divisors must only be added once. Otherwise, we add both i and num/i and continue:
int sum_proper_divisors(int const number)
{
int result = 1;
for (int i = 2; i <= std::sqrt(number); i++)
{
if (number%i == 0)
{
result += (i == (number / i)) ? i : (i + number / i);
}
}
return result;
}
Printing abundant numbers is as simple as iterating up to the specified limit, computing the sum of proper divisors and comparing it to the number:
void print_abundant(int const limit)
{
for (int number = 10; number <= limit; ++number)
{
auto sum = sum_proper_divisors(number);
if (sum > number)
{
std::cout << number << ", abundance="
<< sum - number << std::endl;
}
}
}
int main()
{
int limit = 0;
std::cout << "Upper limit:";
std::cin >> limit;
print_abundant(limit);
}
7. Amicable numbers
Two numbers are said to be amicable if the sum of the proper divisors of one number is equal to that of the other number. The proper divisors of a number are the positive prime factors of the number other than the number itself. Amicable numbers should not be confused with friendly numbers. For instance, the number 220 has the proper divisors 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110, whose sum is 284. The proper divisors of 284 are 1, 2, 4, 71, and 142; their sum is 220. Therefore, the numbers 220 and 284 are said to be amicable.
The solution to this problem is to iterate through all the numbers up to the given limit. For each number, compute the sum of its proper divisors. Let’s call this sum1. Repeat the process and compute the sum of the proper divisors of sum1. If the result is equal to the original number, then the number and sum1 are amicable numbers:
void print_amicables(int const limit)
{
for (int number = 4; number < limit; ++number)
{
auto sum1 = sum_proper_divisors(number);
if (sum1 < limit)
{
auto sum2 = sum_proper_divisors(sum1);
if (sum2 == number && number != sum1)
{
std::cout << number << "," << sum1 << std::endl;
}
}
}
}
In the above sample, sum_proper_divisors() is the function seen in the solution to the abundant numbers problem.
8. Armstrong numbers
An Armstrong number (named so after Michael F. Armstrong), also called a narcissistic number, a pluperfect digital invariant, or a plus perfect number, is a number that is equal to the sum of its own digits when they are raised to the power of the number of digits. As an example, the smallest Armstrong number is 153, which is equal to 
.
To determine if a number with three digits is a narcissistic number, you must first determine its digits in order to sum their powers. However, this involves division and modulo operations, which are expensive. A much faster way to compute it is to rely on the fact that a number is a sum of digits multiplied by 10 at the power of their zero-based position. In other words, for numbers up to 1,000, we have a*10^2 + b*10^2 + c. Since you are only supposed to determine numbers with three digits, that means a would start from 1. This would be faster than other approaches because multiplications are faster to compute than divisions and modulo operations. An implementation of such a function would look like this:
void print_narcissistics()
{
for (int a = 1; a <= 9; a++)
{
for (int b = 0; b <= 9; b++)
{
for (int c = 0; c <= 9; c++)
{
auto abc = a * 100 + b * 10 + c;
auto arm = a * a * a + b * b * b + c * c * c;
if (abc == arm)
{
std::cout << arm << std::endl;
}
}
}
}
}
You could take it as a further exercise to write a function that determines the narcissistic numbers up to a limit, regardless their number of digits. Such a function would be slower because you first have to determine the sequence of digits of the number, store them in a container, and then sum together the digits raised to the appropriate power (the number of the digits).
9. Prime factors of a number
The prime factors of a positive integer are the prime numbers that divide that integer exactly. For instance, the prime factors of 8 are 2 x 2 x 2, and the prime factors of 42 are 2 x 3 x 7. To determine the prime factors you should use the following algorithm:
- While n is divisible by 2, 2 is a prime factor and must be added to the list, while n becomes the result of n/2. After completing this step, n is an odd number.
- Iterate from 3 to the square root of n. While the current number, let’s call it i, divides n, i is a prime factor and must be added to the list, while n becomes the result of n/i. When i no longer divides n, increment i by 2 (to get the next odd number).
- When n is a prime number greater than 2, the steps above will not result in n becoming 1. Therefore, if at the end of step 2 n is still greater than 2, then n is a prime factor.
std::vector<unsigned long long> prime_factors(unsigned long long n)
{
std::vector<unsigned long long> factors;
while (n % 2 == 0) {
factors.push_back(2);
n = n / 2;
}
for (unsigned long long i = 3; i <= std::sqrt(n); i += 2)
{
while (n%i == 0) {
factors.push_back(i);
n = n / i;
}
}
if (n > 2)
factors.push_back(n);
return factors;
}
int main()
{
unsigned long long number = 0;
std::cout << "number:";
std::cin >> number;
auto factors = prime_factors(number);
std::copy(std::begin(factors), std::end(factors),
std::ostream_iterator<unsigned long long>(std::cout, " "));
}
As a further exercise, determine the largest prime factor for the number 600,851,475,143.
10. Gray code
Gray code, also known as reflected binary code or simply reflected binary, is a form of binary encoding where two consecutive numbers differ by only one bit. To perform a binary reflected Gray code encoding, we need to use the following formula:
if b[i-1] = 1 then g[i] = not b[i]
else g[i] = b[i]
This is equivalent to the following:
g = b xor (b logically right shifted 1 time)
For decoding a binary reflected Gray code, the following formula should be used:
b[0] = g[0]
b[i] = g[i] xor b[i-1]
These can be written in C++ as follows, for 32-bit unsigned integers:
unsigned int gray_encode(unsigned int const num)
{
return num ^ (num >> 1);
}
unsigned int gray_decode(unsigned int gray)
{
for (unsigned int bit = 1U << 31; bit > 1; bit >>= 1)
{
if (gray & bit) gray ^= bit >> 1;
}
return gray;
}
To print the all 5-bit integers, their binary representation, the encoded Gray code representation, and the decoded value, we could use the following code:
std::string to_binary(unsigned int value, int const digits)
{
return std::bitset<32>(value).to_string().substr(32-digits, digits);
}
int main()
{
std::cout << "Number\tBinary\tGray\tDecoded\n";
std::cout << "------\t------\t----\t-------\n";
for (unsigned int n = 0; n < 32; ++n)
{
auto encg = gray_encode(n);
auto decg = gray_decode(encg);
std::cout
<< n << "\t" << to_binary(n, 5) << "\t"
<< to_binary(encg, 5) << "\t" << decg << "\n";
}
}
11. Converting numerical values to Roman
Roman numerals, as they are known today, use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, and M = 1000. The system uses additions and subtractions in composing the numerical symbols. The symbols from 1 to 10 are I, II, III, IV, V, VI, VII, VIII, IX, and X. Romans did not have a symbol for zero and used to write nulla to represent it. In this system, the largest symbols are on the left, and the least significant are on the right. As an example, the Roman numeral for 1994 is MCMXCIV. If you are not familiar with the rules for Roman numerals, you should read more on the web.
To determine the Roman numeral of a number, use the following algorithm:
- Check every Roman base symbol from the highest (M) to the lowest (I)
- If the current value is greater than the value of the symbol, then concatenate the symbol to the Roman numeral and subtract its value from the current one
- Repeat until the current value reaches zero
For example, consider 42: the first Roman base symbol smaller than 42 is XL, which is 40. We concatenate it to the numeral, resulting in XL, and subtract from the current number, resulting in 2. The first Roman base symbol smaller than 2 is I, which is 1. We add that to the numeral, resulting in XLI, and subtract 1 from the number, resulting in 1. We add one more I to the numeral, which becomes XLII, and subtract again 1 from the number, reaching 0 and therefore stopping:
std::string to_roman(unsigned int value)
{
std::vector<std::pair<unsigned int, char const*>> roman {
{ 1000, "M" },{ 900, "CM" }, { 500, "D" },{ 400, "CD" },
{ 100, "C" },{ 90, "XC" }, { 50, "L" },{ 40, "XL" },
{ 10, "X" },{ 9, "IX" }, { 5, "V" },{ 4, "IV" }, { 1, "I" }};
std::string result;
for (auto const & kvp : roman) {
while (value >= kvp.first) {
result += kvp.second;
value -= kvp.first;
}
}
return result;
}
This function can be used as follows:
int main()
{
for(int i = 1; i <= 100; ++i)
{
std::cout << i << "\t" << to_roman(i) << std::endl;
}
int number = 0;
std::cout << "number:";
std::cin >> number;
std::cout << to_roman(number) << std::endl;
}
12. Largest Collatz sequence
The Collatz conjecture, also known as the Ulam conjecture, Kakutani's problem, the Thwaites conjecture, Hasse's algorithm, or the Syracuse problem, is an unproven conjecture that states that a sequence defined as explained in the following always reaches 1. The series is defined as follows: start with any positive integer n and obtain each new term from the previous one: if the previous term is even, the next term is half the previous term, or else it is 3 times the previous term plus 1.
The problem you are to solve is to generate the Collatz sequence for all positive integers up to one million, determine which of them is the longest, and print its length and the starting number that produced it. Although we could apply brute force to generate the sequence for each number and count the number of terms until reaching 1, a faster solution would be to save the length of all the sequences that have already been generated. When the current term of a sequence that started from a value n becomes smaller than n, then it is a number whose sequence has already been determined, so we could simply fetch its cached length and add it to the current length to determine the length of the sequence started from n. This approach, however, introduces a limit to the Collatz sequences that could be computed, because at some point the cache will exceed the amount of memory the system can allocate:
std::pair<unsigned long long, long> longest_collatz(
unsigned long long const limit)
{
long length = 0;
unsigned long long number = 0;
std::vector<int> cache(limit + 1, 0);
for (unsigned long long i = 2; i <= limit; i++)
{
auto n = i;
long steps = 0;
while (n != 1 && n >= i)
{
if ((n % 2) == 0) n = n / 2;
else n = n * 3 + 1;
steps++;
}
cache[i] = steps + cache[n];
if (cache[i] > length)
{
length = cache[i];
number = i;
}
}
return std::make_pair(number, length);
}
13. Computing the value of Pi
A suitable solution for approximately determining the value of Pi is using a Monte Carlo simulation. This is a method that uses random samples of inputs to explore the behavior of complex processes or systems. The method is used in a large variety of applications and domains, including physics, engineering, computing, finance, business, and others.
To do this we will rely on the following idea: the area of a circle with diameter d is PI * d^2 / 4. The area of a square that has the length of its sides equal to d is d^2. If we divide the two we get PI/4. If we put the circle inside the square and generate random numbers uniformly distributed within the square, then the count of numbers in the circle should be directly proportional to the circle area, and the count of numbers inside the square should be directly proportional to the square’s area. That means that dividing the total number of hits in the square and circle should give PI/4. The more points generated, the more accurate the result shall be.
For generating pseudo-random numbers we will use a Mersenne twister and a uniform statistical distribution:
template <typename E = std::mt19937,
typename D = std::uniform_real_distribution<>>
double compute_pi(E& engine, D& dist, int const samples = 1000000)
{
auto hit = 0;
for (auto i = 0; i < samples; i++)
{
auto x = dist(engine);
auto y = dist(engine);
if (y <= std::sqrt(1 - std::pow(x, 2))) hit += 1;
}
return 4.0 * hit / samples;
}
int main()
{
std::random_device rd;
auto seed_data = std::array<int, std::mt19937::state_size> {};
std::generate(std::begin(seed_data), std::end(seed_data),
std::ref(rd));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
auto eng = std::mt19937{ seq };
auto dist = std::uniform_real_distribution<>{ 0, 1 };
for (auto j = 0; j < 10; j++)
std::cout << compute_pi(eng, dist) << std::endl;
}
14. Validating ISBNs
The International Standard Book Number (ISBN) is a unique numeric identifier for books. Currently, a 13-digit format is used. However, for this problem, you are to validate the former format that used 10 digits. The last of the 10 digits is a checksum. This digit is chosen so that the sum of all the ten digits, each multiplied by its (integer) weight, descending from 10 to 1, is a multiple of 11.
The validate_isbn_10 function, shown as follows, takes an ISBN as a string, and returns true if the length of the string is 10, all ten elements are digits, and the sum of all digits multiplied by their weight (or position) is a multiple of 11:
bool validate_isbn_10(std::string_view isbn)
{
auto valid = false;
if (isbn.size() == 10 &&
std::count_if(std::begin(isbn), std::end(isbn), isdigit) == 10)
{
auto w = 10;
auto sum = std::accumulate(
std::begin(isbn), std::end(isbn), 0,
[&w](int const total, char const c) {
return total + w-- * (c - '0'); });
valid = !(sum % 11);
}
return valid;
}
