Programming Praxis

10 Responses to “Minimax Pandigital Factor”

1. Paul said

   June 13, 2014 at 10:06 AM

   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

   June 13, 2014 at 3:02 PM

   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

   June 13, 2014 at 3:38 PM

   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

   June 13, 2014 at 4:51 PM

   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

   June 13, 2014 at 5:05 PM

   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

   June 13, 2014 at 6:50 PM

   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

   June 13, 2014 at 7:05 PM

   @mcmillhj: Thank you, most kind.
8. JP said

   June 17, 2014 at 6:02 AM

   (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

   June 17, 2014 at 7:33 AM

   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. Karl Bielefeldt said

    June 20, 2014 at 8:46 PM

    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
    

Leave a Reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out /  Change )

You are commenting using your Twitter account. ( Log Out /  Change )

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

Notify me of new comments via email.

Notify me of new posts via email.

Δ