Initial Search Program

The first program that I wrote to search for PPDIs was written in C++, and made use of the critical observation made earlier to only search as few numbers as possible. It was very limited in scope, taking as command line arguments the base, the number of digits to check, and the beginning and ending powers to try. Since I had to deal with extremely large numbers, I used the GNU Multiprecision Library ([5]) to store and perform arithmetic on them, rather than writing my own.

This program had three main design features that are worth noting. To store the numbers that were checked, I wrote a class called FrequencyList, which stored an array of integers, representing the number of each digit exists in the current number to check. When checking a number, It is necessary to add up the $t^{th}$ powers of each digit and then determine if the numbers of each digit in the result are the same as the numbers of each digit that were exponentiated and added. Therefore, I wrote two other functions for this class - ``Digitize'', which converts a number from its value into its base-$B$ digits, and an overloaded = operator which would compare two FrequencyLists to determine if the numbers of each digit were equal.

In order to generate the set of all combinations of the digits, I wrote a recursive function that acts on the FrequencyList object. Although I realized it would execute slower than actually writing out loops, I felt that it was justified in that my program would be flexible enough to handle any base without modification. Generally, the algorithm of this function was:

1212


If Current Index $< 0$, or there are no digits left to distribute


return;


Set the current index so that it contains all remaining digits

{Check to see if the number produced is a PDI}


For each index $i$ in the list, total $+=$ List[$i$]*$i^{t}$


If the total has the same quantity of each digit as the list


The value of the total must be a PDI, so print out its base B representation


Zero out all digits to the left of the current index


While there are digits left to distribute at the current index


Decrement the value at the current index by one


Repeat the process on the next lowest index with the current number ofremaining digits to distribute 

The last feature of note was that in order to avoid the large amount of exponentiation in the inner loop, I instead pre-computed the value of each digit raised to the $t^{th}$ power and stored it in a table. I possibly could have saved even more time by precomputing the values of $1 \ldots n$ times each digit to the $t^{th}$ power, but that could have become memory intensive for large values of n.

Using this program, I calculated all PDIs and PPDIs up to order 30. As would be expected, the time it took to calculate each order increased; order 30 took approximately 12 hours to calculate. Since my results agreed with those published in other tables, I did not use my program to calculate higher orders but instead worked on creating a more flexible and better-optimized meta-program.