## Minimax Pandigital Factor

### June 13, 2014

Over at /r/math, Darksteve writes of “A problem I came up with, and haven’t been able to solve for many years:”

I would like to present a mathematical problem that I came up with some years ago, and haven’t yet found a solution for:

If you take all the numbers that contain the digits 1 to 9 exactly once, and you write down the prime factorization of all those numbers, which one has the smallest biggest prime factor?

To illustrate what I mean, the number 879456123 contains the prime factors 3 7 13 and 491; making 491 this numbers biggest prime factor.

The number 213456789 contains 3 7 13 and 197 as factors, making 197 the biggest prime factor. Out of all the numbers I’ve tried, 213456789 has the smallest biggest prime factor.

Many other number have much bigger biggest prime factors, like 576492813 which contains 3 13 19 and 13649.

But I have not found a way to actually solve this problem, as I am lacking the programming skills, or the algebraic knowledge required. I would therefore greatly appreciate anyone capable of solving this.

Your task is to solve Darksteve’s problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 10 Responses to “Minimax Pandigital Factor”

1. Paul said

In Python. I used the factorization method in the PP Primes Essay.

```from itertools import permutations
from ma.primee import td_factors

def solve():
cand, maxfac = None, 10000
for p in permutations("123456789"):
d = int("".join(p))
try:
facs = td_factors(d, limit=maxfac - 1)
except OverflowError:
continue
m = max(facs)
if m < maxfac:
cand, maxfac = (d, m)
return cand, maxfac

print "Solution", solve() # -> Solution (619573248, 7)
```
2. matthew said

Build up list of numbers with std::next_permutation, then pull out factors from the bottom until some are reduced to 1:

```#include <algorithm>
#include <vector>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;

int main()
{
vector<int> n;
vector<int> m;
char s[] = "123456789";
do {
int k = atoi(s);
n.push_back(k);
m.push_back(k);
} while (next_permutation(s,s+strlen(s)));
int N = n.size();
// All numbers are divisible by 9, so none is power of 2
for (int i = 0; i < N; i++) {
while(n[i]%2 == 0) {
n[i] /= 2;
}
}
bool found = false;
for (int p = 3; !found; p += 2) {
for (int i = 0; i < N; i++) {
while (n[i]%p == 0) {
n[i] /= p;
if (n[i] == 1) {
printf("%d %d\n", m[i], p);
found = true;
}
}
}
}
}
```
3. danaj said

Perl using modules:

use Algorithm::Combinatorics qw/permutations/;
use Math::Prime::Util qw/factor/;

my \$small = [1e12, 0];
my \$it = permutations([qw/1 2 3 4 5 6 7 8 9/]);
while (my \$p = \$it->next) {
my \$n = join(“”,@\$p);
my \$bf = (factor(\$n))[-1]; # take largest factor
\$small = [\$bf, \$n] if \$bf ;
}
print “Smallest largest factor is \$small-> of number \$small->\n”;

4. mcmillhj said

To clarify, since I am not sure I understand the problem completely. The problem is trying to identify pandigital numbers who largest factor is smaller than some limit L?

5. programmingpraxis said

The task is to calculate the largest factor of each pandigital number, and find the smallest of those. Thus, the number 483761925 = 3^2 * 5^2 * 523 * 4111 is pandigital and its largest factor is 4111. But 4111 is not the smallest largest factor, because the largest factor of 483761952 = 2^5 * 3^2 * 41 * 53 * 773 is smaller. In fact, the smallest largest factor is 7, which appears in two different pandigital numbers: 619573248 = 2^12 * 3^2 * 7^5 and 948721536 = 2^7 * 3^2 * 7^7.

6. mcmillhj said

Ah, now I understand. I really enjoyed your solution @matthew. Here is a different Perl solution (doesn’t display ties):

```#!/usr/bin/perl

use strict;
use warnings;

use feature qw(say);

use Algorithm::Permute;
use Math::Prime::Util qw(factor);

my \$p_iterator = Algorithm::Permute->new( [1..9] );
my \$maxfactor  = 2**32;
my \$pandigital = undef;
PERM:
while ( my \$perm = join('', \$p_iterator->next) ) {
my \$local_max = (factor(\$perm))[-1];
next PERM
if \$local_max >= \$maxfactor;

\$pandigital = \$perm;
\$maxfactor  = \$local_max;
}

say "\$pandigital, \$maxfactor";
```
7. matthew said

@mcmillhj: Thank you, most kind.

8. JP said
```(require math/number-theory)

(for/fold ([pandigital #f] [smallest-largest-factor +inf.0])
([digits (in-permutations '(0 1 2 3 4 5 6 7 8 9))]
#:unless (zero? (car digits)))
(define n (string->number (apply string-append (map number->string digits))))
(define largest-factor (apply max (map car (factorize n))))
(cond
[(< largest-factor smallest-largest-factor)
(values n biggest)]
[else
(values pandigital smallest-largest-factor)]))
```
9. Paul said

Another Python solution.

```from itertools import permutations, chain
from collections import defaultdict

def solve(maxfac):
"""for each number try divide by all factors 2,3,5,7,.. until value becomes
1 and record last factor used
input maxfac: highest factor to try
"""
factor_numbers = defaultdict(list)
for pd in permutations("123456789"):
number = remainder = int("".join(pd))
for factor in chain((2,), xrange(3, maxfac + 1, 2)):
while remainder % factor == 0:
remainder //= factor
if remainder == 1:
factor_numbers[factor].append(number)
break
return factor_numbers

sol = solve(15)
for k in sorted(sol.keys()):
print k, sol[k]

"""
7 [619573248, 948721536]
11 [214396875, 372594816, 423579618, 536481792, 697321548, 745189632, 847159236]
13 [129783654, 213497856, 256134879, 418693275]
"""
```
10. Actually solved this one straight in the Scala REPL, with pandigitals and prime factors functions I already have in my standard “puzzles” library. Kind of brute forced, but it only took around 3 seconds to run.

```scala> import Puzzles.pandigitals
import Puzzles.pandigitals

scala> import Puzzles.Prime.factors
import Puzzles.Prime.factors

scala> import Puzzles.time
import Puzzles.time

scala> time{pandigitals().map(factors(_).max).min}
time: 2922.930171ms
res0: Int = 7

scala> time{pandigitals().filter(factors(_).max == 7).foreach(println)}
948721536
619573248
time: 2783.357329ms
```