Project Euler/170

Problem Statement

Link: https://projecteuler.net/problem=170

Take the number 6 and multiply it by each of 1273 and 9854:

6 × 1273 = 7638

6 × 9854 = 59124

By concatenating these products we get the 1 to 9 pandigital 763859124. We will call 763859124 the "concatenated product of 6 and (1273,9854)". Notice too, that the concatenation of the input numbers, 612739854, is also 1 to 9 pandigital.

The same can be done for 0 to 9 pandigital numbers.

What is the largest 0 to 9 pandigital 10-digit concatenated product of an integer with two or more other integers, such that the concatenation of the input numbers is also a 0 to 9 pandigital 10-digit number?

Solution: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round7_170-180/Problem170.py

Explanation

This problem asks for the largest 0-to-9 pandigital number that can be expressed as a concatenated product: an integer multiplier a applied to two (or more) other integers b, c, … such that concatenating a × b and a × c yields a 0-to-9 pandigital, and concatenating the inputs a, b, c, … also yields a 0-to-9 pandigital.

Approach

A brute-force search over all 0-to-9 pandigital numbers (10! = 3,628,800 permutations) is feasible. For each pandigital, split it into two parts (left and right). For each common divisor of the two parts, check whether the concatenation of the divisor and the two quotients forms a 10-digit pandigital.

Key observations:

• The concatenated product only needs to be split into two parts (left = factor × one, right = factor × two).
• The factor must divide both parts: 1 < factor ≤ gcd(left, right).
• All valid factors are multiples of 3.

The search proceeds from the largest pandigital (9876543210) downward using std::prev_permutation, stopping at the first valid result.