Self Describing Numbers

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

Problem Description

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 zero 3's.

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 individual digits
    •   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

bullet Out of 10 billion possibilities, why are there only 7 numbers that meet the definition?  Or did I miss some?
bullet Are there additional rules that could shortcut the "brute force" approach so that fewer numbers would require checking?
bullet 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

Modified: February 18, 2016

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.