Search for all "self-describing" integers; integers
of a specified length, N, with the property that, when digit positions are
labeled 0 to N-1, the digit in each position is equal to the number of times
that digit occurs in the number.
Background & Techniques
There are a number of ways to define "self-describing" numbers or
sequences. This program searches for those meeting the above
conditions. For example 1210 is a four digit self describing
number because position "0" has value 1 and there is one 0 in the number;
position "1" has value 2 because there are two 1' s in the number, position "2"
has value 1 and there is one 2, and position "3" has value 0 and there are
Searching for the maximum length, 10 digits, may take several hours, but you
should be able to recognize a pattern in the shorter results and "guess" the
10 digit answer! (Hint: Start by guessing the number of zeros and filling in
the rest of the digits from there.)
I wrote the original version of a program to solve this program several
years ago, but when a young student asked me about it the other day, I
couldn't find the program so I coded it again. yesterday When I saw
the results, I recalled why I had not posted the original version. The
coding was interesting, but the results are kind of boring. There are
only 7 of them and a pattern is clear in the last few. It would be
interesting to answer a couple of other questions though (see Further
Explorations section below.)
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program
Notes for Programmer's
There are about 70 lines of user written code here so we'll call it
Intermediate level, but most of those lines perform "housekeeping".
The 25 lines that consume most of the search time work like this:
- Initialize with the starting number then loop until the number
exceeds the maximum value for the length specified:
- Convert number to a string so that we can check
- Zero out a array of 10 integers to hold counts of the 10
possible digit values, 0 through 9.
- Examine the string and count the digit occurrences using
the digits as an index into the counts array.
- Compare the counts left to right with the to the
digit values left to right. If they all match, then we have a
solution to display.
- Increment the number to be tested.
There are probably many rules that could be applied to reduce the "search
space" and let the program find solutions faster. So far, the program
uses these two:
- Solutions cannot have leading zeros. A zero in the 1st
position would imply that there is at least one zero in the number so
the leftmost digit must be 1 or greater. This means that we can
start the N digit search with 10N-1 (e.g. 4 digit search can
start at 1000).
- The effective base of an N digit solution is N. That is, it
cannot contain any digit values larger than N-1. (The 4 digits of a 4
digit solution represent counts of values 0, 1, 2, and 3, so no
need to count and check any integer containing a digit greater than 3).
Running/Exploring the Program
Suggestions for Further Explorations
||Out of 10
billion possibilities, why are there only 7 numbers that meet the
definition? Or did I miss some?
additional rules that could shortcut the "brute force" approach so
that fewer numbers would require checking?
||The inner loop
of the program could no doubt be speeded up, but I was too lazy to
add the timing stuff right now.
Original Date: August 19, 2007
February 18, 2016