## Minimax Pandigital Factor

### June 13, 2014

The Standard Prelude makes it easy to compute the pandigital numbers that include all the digits from 1 to 9: `(map undigits (permutations (range 1 10)))`. That gives 9! = 362880 pandigital numbers. Then, instead of fully factoring each one, we partially factor up to some desired smoothness bound:

```(define (darksteve limit)   (sort lt?     (map (lambda (xs) (cons (apply * xs) xs))       (filter (lambda (x) x)         (map (lambda (x) (smooth limit x))           (map undigits             (permutations               (range 1 10))))))))```

The `smooth` function uses a 2,3,5-wheel to find the factors of n that are less than a bound b:

```(define (smooth b n) ; factors if b-smooth, else #f   (let loop ((n n) (f 2) (fs (list))              (wheel (cons 1 (cons 2 (cons 2 (cycle 4 2 4 2 4 6 2 6))))))     (if (< b f) #f       (if (= n 1) fs         (if (zero? (modulo n f))             (loop (/ n f) f (cons f fs) wheel)             (loop n (+ f (car wheel)) fs (cdr wheel)))))))```

The answer to Darksteve’s problem is 7; there are two pandigital numbers, 619573248 = 2^12 * 3^2 * 7^5 and 948721536 = 2^7 * 3^2 * 7^7, with maximum factor 7. Here is the list of 20-smooth pandigital numbers:

```> (darksteve 20) ((619573248 7 7 7 7 7 3 3 2 2 2 2 2 2 2 2 2 2 2 2)  (948721536 7 7 7 7 7 7 7 3 3 2 2 2 2 2 2 2)  (214396875 11 11 7 5 5 5 5 5 3 3 3 3)  (372594816 11 11 11 3 3 3 3 3 3 3 2 2 2 2 2 2 2)  (423579618 11 11 7 7 7 7 3 3 3 3 3 3 2)  (536481792 11 7 7 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2)  (697321548 11 11 11 11 7 7 3 3 3 3 3 2 2)  (745189632 11 11 11 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2)  (847159236 11 11 7 7 7 7 3 3 3 3 3 3 2 2)  (129783654 13 11 7 7 7 7 7 3 3 3 2)  (213497856 13 11 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2)  (256134879 13 13 11 7 3 3 3 3 3 3 3 3 3)  (418693275 13 13 13 11 11 7 5 5 3 3)  (139478625 17 17 13 11 5 5 5 3 3 3)  (142957386 17 13 11 11 11 3 3 3 3 3 2)  (156397824 17 11 11 11 3 3 3 2 2 2 2 2 2 2 2)  (159274836 17 17 7 3 3 3 3 3 3 3 3 3 2 2)  (185342976 17 13 13 7 3 3 2 2 2 2 2 2 2 2 2 2)  (256937184 17 17 7 7 7 3 3 3 3 2 2 2 2 2)  (312795648 17 11 11 11 3 3 3 2 2 2 2 2 2 2 2 2)  (318549672 17 17 7 3 3 3 3 3 3 3 3 3 2 2 2)  (319467825 17 17 17 17 17 5 5 3 3)  (426391875 17 13 7 7 7 5 5 5 5 3 3)  (462193875 17 13 13 13 11 5 5 5 3 3)  (589324176 17 17 17 17 7 7 3 3 2 2 2 2)  (124783659 19 13 11 7 3 3 3 3 3 3 3 3)  (164923857 19 7 7 3 3 3 3 3 3 3 3 3 3 3)  (165297834 19 17 13 3 3 3 3 3 3 3 3 3 2)  (167845392 19 13 13 11 11 3 3 3 2 2 2 2)  (183649725 19 19 19 17 7 5 5 3 3)  (213465798 19 19 19 19 13 7 3 3 2)  (231469875 19 17 13 7 7 5 5 5 3 3)  (243918675 19 19 13 11 7 5 5 3 3 3)  (249567318 19 13 11 7 3 3 3 3 3 3 3 3 2)  (271964385 19 17 11 7 5 3 3 3 3 3 3 3)  (283961574 19 17 17 17 13 13 3 3 2)  (286493571 19 19 19 17 13 7 3 3 3)  (389174625 19 17 17 7 5 5 5 3 3 3 3)  (459317628 19 19 17 11 7 3 3 3 3 3 2 2)  (461892375 19 7 7 7 7 5 5 5 3 3 3 3)  (567923148 19 17 17 17 13 13 3 3 2 2)  (598321647 19 17 11 11 7 3 3 3 3 3 3 3)  (763251489 19 13 13 11 7 7 7 7 3 3))```

You can run the program at http://programmingpraxis.codepad.org/vGy44zaT, which gives the output in a slightly different form.

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 [0];
}
print “Smallest largest factor is \$small->[0] of number \$small->[1]\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
```