home *** CD-ROM | disk | FTP | other *** search
/ Archive Magazine 1996 / ARCHIVE_96.iso / discs / mag_discs / volume_8 / issue_08 / puzzles / !EgFrac / !Help < prev    next >
Text File  |  1995-03-04  |  3KB  |  55 lines
  1. EgFrac - Egyptian Fractions
  2. ⌐ John Banks February 1995
  3.  
  4. See Colin Singleton's Puzzle Corner in Archive Magazine, March 1995
  5.  
  6. This application expresses any fraction of unity (1) or less as a series of reciprocals, that is fractions with a numerator of 1.
  7.  
  8.     For example: 59/80 = 1/4 + 1/5 + 1/8 + 1/10 + 1/16
  9.  
  10. Double clicking on the application icon installs it on the icon bar in the usual way. Clicking select on the iconbar icon opens the main application window. Use this to choose
  11.     
  12.    - the numerator of the fraction (a in a/b) 
  13.    - the denominator (b)
  14.    - the maximum denominator permitted in the partition reciprocals
  15.    - the greatest number of terms to be allowed
  16.  
  17. These values can be adjusted with the small blue adjuster icons. They will not allow you to enter a fraction more than 1, such as 3/2. You can however type in such a fraction. The program may well find partitions, but not necessarily and not all of them as it will for "legal" fractions.
  18.  
  19. The "Clear" icon will insert default values for these quantities, namely a fraction of 1/2, 4 terms allowed with a maximum denominator of 1/100.
  20.  
  21. "Search" will initiate the search. The results are sent to a task window under the control of whatever application on your machine owns the text filetype (&FFF). This is normally Edit, which will be installed on your iconbar if not already there. For high values of maximum denominator and (especially) of search depth you may as well leave the machine on whilst you go shopping, or to the pub or to bed, but "reasonable" searches are very fast. Soon after the start the results window opens and you can see them building up. You end with a text window belonging to Edit (or whatever), NOT to EgFrac. You may do what you will with this.
  22.  
  23. While the search is in progress, the pointer becomes the hourglass, so long as it is over our own (not the Edit) window.
  24.  
  25. You can abort the search process at any time 
  26.  
  27.    - by clicking the icon now labelled STOP; or 
  28.    - by hitting the ESCAPE key (provided EgFrac's window owns the machine's 
  29.      input focus - title bar is cream when this is so); or
  30.    - by closing the EgFrac window. 
  31.  
  32. Within the application directory is a simple basic program EgFrac. This will run a bit faster if lengthy searches are required as it suffers no desktop processing overheads. Use CTRL-B outside the desktop to direct its output to your printer.
  33.  
  34. ========================
  35. The algorithm
  36. ========================
  37.  
  38. If a/b = 1/c + 1/d + ... (n terms), then the start integer c is constrained. 1/c is certainly LESS than a/b, and 1/nc is certainly MORE than it. So minimum (h) and maximum (k) possible first terms are established.
  39.  
  40. The algorithm is a simple recursive structure:
  41.       
  42.   FIND (num, den, trial, depth)
  43.     REPEAT
  44.       IF 1/depth = num/den THEN
  45.         success, output series of stored values ending with trial
  46.         ELSE
  47.         IF depth<maxdepth THEN
  48.           store trial
  49.           FIND(num*trial-den,trial*den,trial+1,depth+1)
  50.         ENDIF
  51.       ENDIF
  52.       trial+=1
  53.     UNTIL trial>max_permitted OR trial>max_possible
  54.   END
  55.