Dear Monks
Anybody up for some golf?
I have been asked to find a number that is a permutation of
123456789 and has the following properties.
The complete number should be divisable by 9
The number built of the first 8 digits should be dividable by 8
The number built of the first 7 digits should be divisable by 7
and so forth until you just have one digit that is divisable by one
(the last part is pretty easy ;-)
I wrote a perl script to find the number(s) it is 157 characters long (no strict):
sub t{($n,@c)=@_;my@w;foreach$c(@c){for$u(1..9)
{next if$c=~/$u/;$y=$c.$u;if($y%$n==0){push(@w,$y)}}}return@w}
my@c=(1..9);for$i(2..9){@c=&t($i,@c)}print"@c\n"

[download]
Here is a bit more readable version of the same program (runs under strict):
use warnings;
use strict;

sub iter {
 my ($n, @old_cand) = @_;
 my @new_cand;
 foreach my $cand (@old_cand) {
  for my $num (1..9) {
   next if $cand =~ /$num/;
   my $new_c=$cand.$num;
   if ($new_c % $n == 0) {push ( @new_cand, $new_c)}
  }
 }
 return @new_cand;
}

my @c=(1..9);
for my $i (2..9) {
 @c=&iter($i, @c);
}
print "@c\n";

[download]
Comments?
si_lence

Replies are listed 'Best First'.
Re: Golf the numbers!
by cLive ;-) (Prior) on Oct 29, 2004 at 23:26 UTC

    The complete number should be divisible by 9

    No need to test this part. All combinations of the digits 1-9 are divisible by nine, since their total is divisible by 9.

    Actually, let's see if we can solve this by hand (except for the /7 bit because I'm lazy on that front) as an aside, using standard regexp notation and known rules...

    Since even numbers must be divisible by 2, and five must be in the middle (5 and 0 are only valid numbers for position 5), we start with:

    [1379][2468][1379][2468]5[2468][1379][2468][1379]

    [download]

    First 4 digits must be divisible by 4, so 3rd and 4th digits must be divisible by 4, ie one of 12,16,32,36,72,76,92 or 96, making it:

    [1379][2468][1379][26]5[2468][1379][2468][1379]

    [download]

    Each block of 3 digits must be divisible by 3 (implied since first 3 divisible by 3,6 by 6 and 9 by 9, and sum of digits of frst 3,6 and 9 must also be divisible by 3.This leads us to:

    [1379][2468][1379](258|654)[1379][2468][1379]

    [download]

    So we have two cases:

    [1379][46][1379](258)[1379][46][1379]
[1379][28][1379](654)[1379][28][1379]

    [download]

    Examining the first case now, the first 3 digits can be:

    147, 369, 741 and 963

    [download]

    So, what can the 6th to 8th digits be if it has to start with an 8? Well, that means the 7th and 8th digits are divisible by 8:

    816 and 896

    [download]

    But 816 can't work because it clashes with all possibilities for the first 3 digits, so we can only try 896, leaving us with, by elimination:

    (147|741)(25896)3

ie 147258963 and 741258963

    [download]
    And we haven't touched division by 7 yet*. A quick bit of mental division (1472589/7 and 7412589/7) tells us that neither of these fit the bill, so on to the second case:

    [1379][28][1379](654)[1379][28][1379]

    [download]

    Again, first 3 digits can be:

    123,129,321,327,723,729,921,927,183,189,381,387,783,789,981,987

    [download]

    400 is divisible by 8, so consider 6th-8th numbers where 7th and 8th are divisible by 8:

    432 and 472

    [download]

    Both these contain 2, so we can narrow first three down to:

    183,189,381,387,783,789,981,987

    [download]

    Leaving us with these possible candidates:

    189654327  1896543/7 = 270934.714
789654321  7896543/7 = 1128077.57
981654327  9816543/7 = 1402363.29
987654321  9876543/7 = 1410934.71
183654729  1836547/7 = 262363.857
189654723  1896547/7 = 270935.286
381654729  3816547/7 = 545221      <-- we have a winner
981654723  9816547/7 = 1402363.86

    [download]

    Well, that was a good waste of a couple of hours. Time to load up the laptop so I can catch up on work tonight :)

    Damn you si_lence for sucking me in!

    cLive ;-)

    * there is a rule for division by seven, but it's no use here. Chop off last digit, double it and remove total from remaining digits. If this number is divisible by seven, then so is original (repeat as necessary). Whether this is any quicker than just dividing by seven the long way or not is debatable in my eyes though - either way, it's no use until we know the last seven digits anyway...

[reply]
[d/l]
[select]

      Nice++.

      These are these methods I was taught by dear ol' "Spud" Murphy (otherwise known as Dr.T.N Murphy--we never did find out what the T.N. stood for:). I remember him ruing the day when he had to tell us that we could use calculators in our exams provided that they didn't have memories.

      I borrowed my brother-in-law's Sinclair Scientific (which he wore on his belt to meetings like people did with mobile phones in the late '80s:). I took it into the exam and placed it on the desk in front of me, but then used log tables because I had never got to grips with the reverse polish notation!

      Spud was right about calculators.

      Examine what is said, not who speaks.
      "Efficiency is intelligent laziness." -David Dunham
      "Think for yourself!" - Abigail
      "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
[reply]

      there is a rule for division by seven, but it's no use here ...

      Alternatively, convert to base 8 and add the digits. :)

      More useful can be to take advantage of the fact that 1001 is 7 * 11 * 13 - you can check for divisibility of all three of those in one step by adding/subtracting alternating groups of 3 digits (counting from the right).

      Eg:

        testing 123456789
  split into groups: 789, 456, 123
  add/subtract alternately: 789 - 456 + 123 = 456
  factorise what's left: 456 = 2^3 * 3 * 19
  so 123456789 is not divisible by 7 or 11 or 13

      [download]

      If the resulting number is difficult to factorise in your head, you can always add/subtract multiples of one of those primes until you get to something that obviously is/isn't a multiple of that prime:

        456 = 400 + 56 (so it isn't divisible by 7)
  456 = 390 + 66 (so it isn't divisible by 11 or 13)

      [download]

      Hugo

[reply]
[d/l]
[select]
      If you're going to do this much work, you can do it entirely by hand.

      Let's see. The fifth number has to be divisible by 5, so that digit is 0 or 5, but we don't have a 0 so that is 5. Digits in position 2, 4, 6, and 8 must be even, so that uses up 4 even digits - we only have 4 so all must be used there. Therefore the odd digits must be odd.

      Oh, but we can go further still, so far we know that at position 4 we have (odd)(even)(odd)(even) and we need it divisible by 4, that will only happen if the 4'th digit is divisible by 2 but not 4. A similar thing happens at position 8. We only have 2 such digits, 2 and 6. Therefore 2 and 6 appear at positions 4 and 8. And 4 and 8 appear at positions 2 and 6.

      We are now in a position to do exhaustive search. The pattern is that we want a permutation where the digits happen to fall into the sequence

      1. 1, 3, 7, 9
      2. 4, 8
      3. 1, 3, 7, 9
      4. 2, 6
      5. 5
      6. 4, 8
      7. 1, 3, 7, 9
      8. 2, 6
      9. 1, 3, 7, 9
      With this pattern we need to check that the first 3 digits are divisible by 3. The second 3 digits are divisible by 3. The first 7 are divisible by 7. And the 7'th and 8'th are divisible by 8. Here is the exhaustive search: 
      143 x
14725836 x
1472589 x
147658 x
149 x
183254 x
1836547 x
1836549 x
187 x
189254 x
1896547 x
1896549 x
341 x
347 x
349 x
381254 x
381654729 <--- Yes!
3816549 x
387254 x
3876541 x
3876549 x
389 x
7412583 x
7412589 x
741658 x
743 x
749 x
781 x
783254 x
7836541 x
78365492 x
789254 x
7896541 x
7896543 x
941 x
943 x
947 x
981254 x
9816543 x
9816547 x
983 x
987254 x
9876541 x
9876543 x

      [download]
      And there you have it, only one answer.

      Incidentally that there would be about one answer should not surprise. After all we have 9! permutations. But odds are that all of them get through the first check, half the second, a third the third, a quarter the fourth, etc. So we'd expect about 1/9! of the permutations to get through. Which (hmmm...) works out an estimate of 1 right answer...

[reply]
[d/l]
      I started writing a mathematical response here, but I've created a new thread in Meditations.
      _____________________________________________________
      Jeff japhy Pinyan, P.L., P.M., P.O.D, X.S.: Perl, regex, and perl hacker
      How can we ever be the sold short or the cheated, we who for every service have long ago been overpaid? ~~ Meister Eckhart
[reply]
Re: Golf the numbers!
by tilly (Archbishop) on Oct 29, 2004 at 17:59 UTC
    Given the output the shortest solution is probably the following 17 char one: 
    print"381654729
"

    [download]
    Unless you want to cheat with: 
    die"381654729
"

    [download]
    But for "real" solutions, try this 78 character one: 
    sub t{@_||print"$n
";for(1..@_){$n.=shift;$n%(9-@_)||&t;push@_,chop$n}}t(1..9)

    [download]
[reply]
[d/l]
[select]
      That "real" solution can be compressed to 76 characters at the cost of readability: 
      sub t{@_||print"$,
";$,.=shift,$,%(9-@_)||&t,push@_,chop$,for 1..@_}t(1..9)

      [download]
      Update: I was blind. 72. 
      sub t{@_||print"$,
";$,.=shift,$,%(9-@_)||&t,push@_,chop$,for@_}t(1..9)

      [download]
[reply]
[d/l]
[select]
        you can save one char by removeing the brackets from the subroutine call
        sub t{@_||print"$,
";$,.=shift,$,%(9-@_)||&t,push@_,chop$,for@_}t 1..9

        [download]
[reply]
[d/l]
      <impressed>

      I'll be really impressed at the golfed version of Algorithm::Loops.

      </impressed>

      Being right, does not endow the right to be rude; politeness costs nothing.
      Being unknowing, is not the same as being stupid.
      Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
      Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

[reply]
Re: Golf the numbers!
by TedPride (Priest) on Oct 30, 2004 at 04:00 UTC
    Here's mine just to prove I can, but it's much sloppier than most of the examples given here. I'll have to analyze your code and see if I can make mine more efficient.

    sub permute {
    return if $_[0] && $_[0] / length($_[0]) != int ($_[0] / length($_
+[0]));
    if (!length($_[1])) { print $_[0]." "; return; }
    for (0..length($_[1])-1) {
         permute($_[0].substr($_[1],$_,1), substr($_[1],0,$_).substr($
+_[1],$_+1));
    }
}

    [download]
    Incidently, I tried some larger numbers and found that the following are all the matches up through 19 digits: 
    1 : 1
12 : 12 
123 : 123 321 
123456 : 123654 321654 
12345678 : 38165472 
123456789 : 381654729 
1234567890 : 3816547290

    [download]
    Then you hit 20 and start getting piles of matches. My algorithm isn't efficient enough yet to go beyond 21 or so.

    EDIT:
    si_lence gets ~27 iterations per second
    Ted_Pride gets ~100 iterations per second
    tilly gets ~154 iterations per second

[reply]
[d/l]
[select]
Re: Golf the numbers!
by sleepingsquirrel (Chaplain) on Oct 29, 2004 at 18:00 UTC
    15 bytes... 
    print 381654729

    [download]

    -- All code is 100% tested and functional unless otherwise noted.
[reply]
[d/l]
      The output differs from the original one.
[reply]

Back to Meditations