9267/18534 =  ½ .  This equation is somewhat special.  It cancels exactly to one-half, but that’s not the only thing.  Look a little closer.  All the digits from 1 to 9 inclusive are used in the fraction on the left once and once only.  Such a collection of digits is known as a 9-digit Pandigital, regardless of their order.
 
The challenge here is to find all other fractions of this type – that is, they use all the digits 1 to 9 inclusive once and once only, and they can be cancelled exactly to one-half. 

The hard way to do this is to rush in, generate all possible 9-digit pandigitals, then, for each permutation, take all combinations of 4 digits from 9.  Each one of these combinations must then be tested to see whether it cancels to equal ½.

Let’s see … my calculator tells me there are 362, 880 permutations of 9 from 9, and 126 combinations of 4 from 9.  126 x 362,880 = 45,722,880.  That’s a lot of calculations!  Guess I won’t rush in after all.

The easy way is to think about the range to cover first.  What’s the smallest possible numerator?  It can’t be 3 digits, since even the largest, 987, when divided by the smallest, 123456, equals only about 0.08 – a lot less than 0.5.  It can’t be 5 digits, since that would make the numerator bigger than the denominator, and the fraction would be greater than 0.5.  Thus, we know the numerator will be 4 digits in size.

Just trying a few arrangements quickly points to a suitable lowest number.  6345/12789 = 0.496, just safely below the magical 0.5.  As this number gets larger, the fraction will get smaller, sweeping through the target, so it’s a good place to start.  The largest possible numerator will be 9876.  Therefore, the sweep range will be 6345 to 9876, 3,531 numbers in all. 

Every one of those numbers can easily be tested.  If it’s going to give the correct answer, the denominator will be double its value.  If the numerator and denominator between them form a Pandigital, we have a correct answer.  So there are only 3,087 test to be made here, instead of the 45 million encountered in the “rush in” method.  The computer will do that in a few seconds instead of days!

Using this approach, the following Ibasic program will do all the work for you.

' Puzzlet #003.
' Using all the digits 1 to 9 inclusive
' once and once only, form fractions whose
' value is exactly 0.5
' Example:  6729/13458 = 0.5
' By Dave Ellis.

' Declarations
declare NoZeroes(check$: string)
declare AllDigitsDifferent(check$: string)
def num, den: int
def check$: string

' Screen SetUp
color 11, 0: cls
openconsole
print "Searching ...": print
color 14, 0: cls

' Main Routine
for num = 6345 to 9876
    den = 2 * num
    check$ = ltrim$( str$(num))+ltrim$( str$(den))
    if NoZeroes(check$)
        if AllDigitsDifferent(check$)
            print num,"/ ",den," = 0.5"
        endif
    endif
next num

' Finished
color 11, 0: cls
print: print "No more!"
print: print "Press any key ... ",
do: until inkey$ <> ""
closeconsole
end

' +++ Functions and Subroutines +++

sub NoZeroes(check$)
' if check$ contains the character zero
' at least once, returns returns 0,
' otherwise returns -1.
def flag, i, L: int
L = len(check$)
i = 1
flag = -1
do
    if mid$(check$,i,1) = "0"
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > L
endif
return flag

sub AllDigitsDifferent(check$)
' if every character in check$ is unique,
' returns -1, otherwise returns 0.
def flag, i, j, L: int
def i$, j$: string
L = len(check$)
flag = -1
i = 1
do
    i$ = mid$(check$, i, 1)
    j = i + 1
    do
        j$ = mid$ (check$, j, 1)
        if i$ = j$
            flag = 0
        endif
        j = j + 1
    until j > L | flag = 0
    i = i + 1
until i > L -1 | flag = 0
endif
return flag

PROGRAM NOTES

The program works very simply when viewed from a top-down point of view. The main routine doubles the denominator  and then concatenates it with the numerator.  If there are no zeroes in the resultant string, and all the digits are unique, it must be a valid answer, so print it!

The function NoZeroes() begins by setting flag to TRUE (-1).  Iterator i then runs through the characters of the argument, check$.  If one of them is found to be a zero, flag's state is changed to FALSE (0) and the DO loop exited.

If no zeroes are encountered, the DO loop is exited when iterator i 's value exceeds the length of check$.

Whatever value is now in flag is returned to the main subroutine as an indication of whether check$ contains zeroes or not.

The function AllDigitsDifferent() begins by setting flag to TRUE (-1). Iterators i and j are used in nested DO loops to examine every possible combination of pairs of characters from the argument, check$. 

If any one of these pairs contains identical characters, flag is set to FALSE (0) and the DO loops exited.  

If no pairs are contain identical characters, both DO loops exit when their iterators have exceeded the length of check$.

Whatever value is now in flag is returned to the main subroutine as an indication of whether check$ contains unique digits or not.

When you run this code, it produces the screen shown inset. As you can see, there are 12 valid solutions altogether.  These are really anagrams of two basic solutions, one beginning with 6792 and the other beginning with 7293.

---

MAIN MENU

DOWNLOAD CODE

ARCHIVES

---

Site design/maintenance: Dave Ellis

E-mail me!

Last Updated: January 23rd, 2010.

---