--============================================================================= --| --| PROCEDURE NAME: pdi (main procedure) --| --| PURPOSE: To find PDIs and PPDIs --| --| PROGRAMMER: Lionel Deimel DATE WRITTEN: 5/24/90 --| DATE OF LAST REVISION: 8/8/90 VERSION: 2.0 --| --| INPUT: (From default file) commands and requests to accept commands from --| user. --| --| (From file "pdi.ckp") checkpoint information. File contains at most --| one checkpoint record. --| --| OUTPUT: (To default file) prompts, status information, and PDIs found. --| --| (To file "pdi.ckp") information written by program to all restart --| from a checkpoint. --| --| ASSUMPTIONS/LIMITATIONS: The program has certain built-in limitations --| that can be altered by changing constants in the code: --| --| 1. Numbers longer than 60 digits cannot be handled. --| Therefore, searches can be performed for at most --| length-60 PDIs. --| --| 2. The maximum radix that can be accommodated is 90. --| --| Searches for long-length PDIs may cause two kinds of problems: --| --| 1. No provision is made for output lines exceeding the line --| length normally handled by the output device. --| --| 2. Available storage may be insufficient for performing some --| searches. The amount needed is highly system-dependent, --| and the storage allocated for the search task may need --| to be adjusted for particular systems or particular --| searches. --| --| ALGORITHM/STRATEGY: Let the radix of the PDIs being sought be r. (See --| background notes below.) The search proceeds by selecting the number --| of digit r-1 in the number to be tested, then the number of digit --| r-2, etc. A combination of digits is counted as tested whenever --| the distribution of all digits r-1, r-2, ... , 0 is determined. --| Each time procedure select_digits is called, the program --| selects the distribution of another digit. The program selects --| the maximum number of occurrences of a digit before a distribution --| involving fewer occurrences is tried. As the number of instances of --| each digit is determined, the sum of these digits raised to the --| search-order power is computed in smin (the minimum summation value --| of the distribution being computed). Should smin become a number --| whose length is greater than the length of the PDIs being sought, --| the program backtracks, thereby removing large digits in favor of --| smaller ones. A one-dimensional array, select_vector, keeps track of --| how many instances of each digit have been selected in the current --| distribution. The search algorithm finds PDIs in roughly reverse --| numerical order. --| ERROR CHECKS/RESPONSES: Most errors likely to occur are caught by the --| program and result in error messages written to the output file. --| Some of the these messages are rather nonspecific, however, and --| may require the user to make reasonable inferences. It is intended --| that invalid input from all sources (including missing and unreadable --| files) be recognized as erroneous and that appropriate user error --| messages be displayed. --| --| COPYRIGHT NOTICE: --| --| Copyright (c) 1990 by Carnegie Mellon University, Pittsburgh, Pa. --| --| Distribution: Approved for public release; distribution is unlimited. --| --| Produced by the Software Engineering Institute (SEI). The SEI is a --| federally funded research and development center operated by Carnegie --| Mellon University and sponsored by the U.S. Department of Defense under --| contract F19628-90-C-0003. --| --| Permission to make copies or derivative works of this software is --| granted, without fee, provided that the copies, derivative works, and --| supporting documentation are not made or distributed for direct --| commercial advantage, and that all copies, derivative works, and --| supporting documentation contain this copyright notice and state that --| copying is by permission of Carnegie Mellon University. --| --| --| NOTES: --| --| 1. Background --| --| This program finds perfect digital invariants (PDIs) and --| pluperfect digital invariants (PPDIs). A PDI is an integer, the --| sum of whose digits, each raised to the same integral power, equals --| the number itself. For example, --| --| 5 5 5 5 --| 4150 = 4 + 1 + 5 + 0 = 1024 + 1 + 3125 + 0. --| --| We call 4150 an order-5 (for the exponent), length-4 (for the number of --| digits) PDI. Being a PDI is a property of the number and its base --| (radix). It is easy to verify, for example, that 4150, interpreted as --| an octal (base-8) number, is not an order-5 PDI. On the other hand, --| the octal number 4423 is an order-5 PDI because --| --| 5 5 5 5 --| 4423 = 4 + 4 + 2 + 3 = 2000 + 2000 + 40 + 363, --| --| where all the arithmetic shown is in octal. Because the radix of the --| number is significant, we should speak of 4150 as an order-5, --| length-4, base-10 PDI and of 4423 as an order-5, length-4, base-8 PDI. --| (Abbreviations are possible; we might say 4150 is an order-5 PDI, --| understanding that the base is 10 and assuming the length is apparent.) --| --| A PDI whose order is the same as its length is known as a pluperfect --| digital invariant, or PPDI. The decimal number 8208, for example, is --| an order-4 PPDI, since --| --| 4 4 4 4 --| 8208 = 8 + 2 + 0 + 8 = 4096 + 16 + 0 + 4096. --| PDIs and PPDIs have been tabulated, but questions remain about their --| properties and distribution. (It is not known if there are PPDIs of --| orders other than 1 in all bases, although there are non-trivial PPDIs --| in nearly all bases.) These are not burning questions of mathematics, --| but they have received a degree of attention, particularly from --| the recreational mathematics community. This program performs --| exhaustive searches for PDIs and PPDIs. --| --| --| 2. References --| --| Martin Gardner, THE INCREDIBLE DR. MATRIX, pp. 205-209. New York: --| Charles Scribner's Sons, 1976. --| --| Lionel Deimel & Michael Jones, "Finding Pluperfect Digital --| Invariants: Techniques, Results and Observations." JOURNAL OF --| RECREATIONAL MATHEMATICS 14:2, pp. 87-107, 1981-1982. --| --| --| 3. Program Operation Overview --| --| The program interacts with the user through the standard input file --| (presumed to be the keyboard). Output is sent to the standard output --| file (presumed to be a CRT). If the user needs to save program output, --| some mechanism is likely available through the operating system. --| (Most operating systems have a way of capturing all terminal output --| in a file.) The user interactively indicates whether search parameters --| (which tell the program what searches to perform) are to be taken from --| the file named "input.dat" or whether a previously begun search is to be --| restarted from a checkpoint. In the latter case, checkpoint information --| is read from file "pdi.ckp." Because searches can be long-running, --| the program records a checkpoint in "pdi.ckp" each hour. Should --| processing be interrupted for any reason, the program can be restarted --| from its state as of the last time a checkpoint was written. --| --| File "input.dat" should contain any number of triples of natural --| numbers, each triple specifying a search the program is to carry out. --| Numbers may be separated by spaces or line breaks; "normal" input --| should have a triple on each line of the file, although this format --| is not required. In any case, any characters on the line after the --| third number of a triple are ignored, and the first number of the next --| triple is sought on the next line. The numbers of the triple --| represent, respectively, the radix, order, and length of the PDIs being --| sought. The second and third numbers of a triple should be equal, --| of course, if the search is for PPDIs. --| --| If the program is started from a checkpoint, the contents of --| "input.dat," if any, are ignored; if the interrupted search is --| completed, the program terminates. --| During a search, the following is written to the screen: --| --| 1. When the search begins, the date, time, and search --| parameters. --| --| 2. When a PDI is found, the number, elapsed time since the --| beginning of the search, and the number of combinations --| tested. The time shown is clock time, not processor time. --| --| 3. When a checkpoint record is written, the date, time, --| elapsed time, number of combinations tested, and search --| state information: the values of smin, digit_to_place --| (the next digit whose number of instances is to be --| determined by select_digits), and select_vector. --| --| 4. When the search ends, the elapsed time and number of --| combinations tested. --| --| While the program is running, the user may interact with it by typing --| . (Actually, the program reads any line entered, but ignores --| the actual contents of the line.) After a brief delay--for the sake --| of efficiency, the program checks the keyboard infrequently--the user --| is prompted with: --| --| Enter "r" to resume search, --| "s" for status check of search, --| "c" to change checkpoint interval, --| "k" to change keyboard polling frequency, or --| "q" to quit: --| --| The user should enter the appropriate letter and . These --| commands, respectively, cause the program to resume its search, --| display the state of the search, change the frequency --| with which checkpoints are taken (from once each hour), change the --| frequency with which the keyboard is checked (the default is after --| each 3000 calls to procedure select_digits), and terminate the program. --| The state information includes all the information printed when a --| checkpoint is taken, plus the search parameters, checkpoint interval, --| and keyboard polling frequency. --| --| The user should recognize that program efficiency and flexibility are --| affected by changing the checkpoint interval and polling frequency. --| If checkpoints are recorded too often, the search process is slowed --| down, although less computing time is wasted should the program have --| to be restarted from a checkpoint. If the number of calls to --| select_digits before the keyboard is checked is made too low, the --| program becomes very responsive to keyboard interrupts, but at a high --| price, measured in terms of search efficiency. --| --| --| 4. Procedure Overview --| --| Procedure pdi prompts the user to determine the source of input. --| Entry calls are made to task search to begin searches. Illegal responses --| by the user cause the prompt to be redisplayed. After the --| appropriate call is made to begin searching, an entry call to --| synchronize is made to initiate monitoring of the keyboard while --| searches proceed. --| --============================================================================= WITH numbers; WITH text_io; PROCEDURE pdi IS -- Maximum length of input line line_length : CONSTANT := 80; -- Position of last character on input line last : natural; -- Flag indicating (if true) that a prompt for a user command must be output repeat : Boolean := true; --Input line entered by user response : string(1 .. line_length); BEGIN -- pdi -- Determine input option from user WHILE repeat LOOP -- Assume no need to reprompt repeat := false; -- Prompt user and read response text_io.new_line; text_io.put_line ("Enter ""n"" for normal input from file ""input.dat"""); text_io.put_line (" or ""r"" to restart from file ""checkpoint"": "); text_io.get_line (item => response, last => last); -- Interpret user response IF (last = 1) THEN IF (response(1) = 'n') THEN -- Take search parameters from "input.dat" numbers.search.process_normal_input.start; ELSIF (response(1) = 'r') THEN -- Begin search from checkpoint file "pdi.ckp" numbers.search.do_search.enter_start_search_from_checkpoint; ELSE -- Invalid user input (unrecognized character); must reprompt repeat := true; text_io.new_line; END IF; ELSE -- Invalid user input (>1 character entered); must reprompt repeat := true; text_io.new_line; END IF; END LOOP; --Begin monitoring keyboard for user request to enter commands numbers.search.synchronize.start_monitor; END pdi;