More on N-persistence, (recreational computing) (column) Michael W. Ecker.
In this column last time, we looked at a number that I pulled out of thin air and which had the property of being 16-persistent: That is, the number times any one of 1, 2, 3, ..., 15, 16 always produced an answer that contained at least one of each digit. Where did I get this number from? Does it have any special significance, or is it just something contrived, found by trial-and-error and lacking in richness?
It would be unreasonable to expect me to foist a contrivance on you, right? So, you can believe that there is some significance to such numbers. Even if you have seen many math recreations, I doubt that you will find this concept in any text. That is because I myself created the concept of n-persistent number a couple of years ago. Moreover, I showed the interesting connection of this concept to one which has been around a while longer. And that is the topic of this month's investigation.
Not to keep you in the dark any longer, the number 5882352941176470 comes from the repetend--or smallest repeating block--in the division of 1 by 17, as 1/17 = .0588235294117647 0588235294117647 0588235294117647...ad infinitum, where the repetend has a length of 16--meaning the digits repeat precisely every 16 digits. (First 16-persistence and now a length of 16; interesting, eh?) The only difference is that I put the leading zero at the tail of our integer, since we don't count leading zeros in whole numbers, as in 34, not 034. (If you prefer, you can note that 10/17 would produce our 16-persistent number with the zero intact.) Note that I'm not saying that this is the only way to produce any n-persistence. I do maintain, however, that it is certainly the most elegant.
So now I have replaced one mystery with a bigger one. What does this have to do with producing n-persistent numbers in general, and why does this work? It would be a lot easier if I could work with smaller numbers just to illustrate the point. Momentarily ignore the question of n-persistence and consider the repetend corresponding to 1/7. Division produces 1/7 = .142857 142857 142857 ...ad infinitum. A more familiar example to readers would be 1/3 = .3 3 3...ad infinitum, or even 1/5 = .2 0 0 0...etc., where I have added the zeros for emphasis.
Realize that no repetend in the division of 1 by p can contain more than p-1 digits in the repetend. In the case of 7, we are saying that the repetend could not have had more than six digits; in the case of 5, at most four digits. Why is this? Simple. When you divide 1 by p, once the digits start repeating, there are only p possible remainders in the actual division, namely 0, 1, 2,...up to p-1. If the remainder is ever 0, as soon happens with the division of 1 by 5, then the division terminates and we get a terminating decimal, or we can say the repetend is 0. Otherwise, we only get p-1 remainders.
Within p-1 steps, any remainder must repeat, which then makes the digits of the decimal quotient repeat within a block of at most p-1 digits. In the limited space available here it is difficult to explain this. I explained this phenomenon--along with some other neat properties--in a lengthier discovery and expository article "The Alluring Lore of Cyclic Numbers" several years ago in the College Mathematics Journal. Readers who don't wish to hunt this down in a math library can send me a self-addressed, stamped envelope and a dollar (to cover photocopy costs), and I'll send a reprint.
Well, it turns out that whenever the prime number p has the property that 1/p has a repetend with the largest possible length, namely p-1, the resulting repetend always has an interesting property. That property is that if you take any of 1, 2, ..., p-1, and multiply by the repetend, you get the same digits in the answer but in a different order.
Consider for example the number 142857, the repetend of 1/7. We have the following: 1X142857 = 142857, 2X142857 = 285714, 3X142857 = 428571, 4X142857 = 571428, 5X142857, = 714258, 6X142857 = 857142, and lastly, 7X142857 = 999999. There is a delightful trick associated with this, but alas, we have no space this month. These last multiplications should also remind you of last month's program in which our special number was 16-persistent, but not 17-persistent, since we got a whole lot of nines when we multiplied by 17. Here, 7 plays the role of 17. As for the nines, it has to do with the mathematical fact that .9 9 9 9...ad infinitum as exactly equal to 1--but that in itself is another story.
Whenever the reciprocal (1/p) of a prime p has a repetend with a full-period, we call that prime a full-period prime. The first p-1 multiples of that repetend always are cyclic permutations of one another (barring any missing leading zeros). For that reason, such primes are also called cyclic primes. To apply this, then, to n-persistence, all you need to do is find a cyclic prime p which is greater than n and 10, take 1/p, and the resulting repetend will be a number which is cyclic. It turns out that there is an almost uniform distribution of digits in the repetend, assuring that each digit appears at least once. Since the repetend is p-1-persistent, and p-1 is at least n, it is, a fortiori, n-persistent as well.
A program to find such repetends can be demanding, so I will solicit your improvements in a moment. The program here simply simulates the division of any numerator by any denominator. It is up to you to restrict yourself to using prime denominators p; the numerator need not be 1. The program prints out the first p-1 digits of the quotient. These may be manually examined for smaller repeating blocks. If you find a smaller repeating block, then the number p is not a full-period or cyclic prime. If none is found, you have one.
As a final note, I must confess to one gap: As of 1985, it is conjectured, but still not proven, that the number of cyclic primes is infinite. We all know that the number of primes (cyclic or not) is infinite, and there is strong evidence that the same is true of full-period ones, but there is no proof yet. When that is done, we will know that for every n, there exists an n-persistent number which we can generate in this manner. If it makes you feel any better though, other proofs exist which do not rely on cyclic primes. However, these lack the elegance--and fun--of this exploration.
This column is open to reader suggestions, questions of a relevant nature, improvements, comments, etc. If you would like an acknowledgment or reply, be sure to enclose a self-addressed, stamped envelope. Write me at 129 Carol Dr., clarks Summit, PA 18411.
Until next month, happy recreational computing.