A ten digit number in which the 1st digit indicates the number of 1's in the number, the 2nd indicates the number of 2's in the number and so on... till the 10th indicates the number of zeros in the number.

I think there should be other such numbers. Node them here if you find them!

This program takes 15 cpu seconds on my system to do 104 tests. The time taken is constant for all numbers. For 1010 tests, it would take 106 * 15 seconds, or approximatly 250,000 minutes, or about half a year (~525600 minutes).

#!/usr/bin/perl -w

use strict;

my $i;  # the test number
my $is; # the 10 digit string version
my @i;  # the array

my $j;  # array iterator
my @j;  # the array built
my $js; # the string of the built array

# little speedup, don't have to keep doing runtime RE's 
my @RE = ( qr/^0$/, qr/^1$/, qr/^2$/, qr/^3$/, qr/^4$/, qr/^5$/,
                    qr/^6$/, qr/^7$/, qr/^8$/, qr/^9$/, qr/^0$/);

# start it off
for ($i = 1; $i < 10000000000; $i++)
{   
    $is = sprintf("%0.10d", $i);
    @i  = split(//,$is);
    for($j = 1; $j <= 10; $j++)
      { $j[$j-1] = grep(/$RE[$j]/,@i); }
    $js = join('',@j);
    if($is eq $js) { print "$is\n"; }
    if(not ($i % 1000)) { print STDERR "calc... $is\n"; }
}

Just unrolled the j loop, which cut the time in half... though not quite as elegant, it certainly is worth 90 days of cpu time.

#!/usr/bin/perl -w

use strict;

my $i;  # the test number
my $is; # the 10 digit string version
my @i;  # the array

my $j;  # array iterator
my @j;  # the array built
my $js; # the string of the built array

# start it off
for ($i = 1; $i < 10000000000; $i++)
{
    $is = sprintf("%0.10d", $i);
    @i  = split(//,$is);
    $j[0] = grep /1/,@i;
    $j[1] = grep /2/,@i;
    $j[2] = grep /3/,@i;
    $j[3] = grep /4/,@i;
    $j[4] = grep /5/,@i;
    $j[5] = grep /6/,@i;
    $j[6] = grep /7/,@i;
    $j[7] = grep /8/,@i;
    $j[8] = grep /9/,@i;
    $j[9] = grep /0/,@i;
    $js = join('',@j);
    if($is eq $js) { print "$is\n"; }
    if(not ($i % 1000)) { print STDERR "calc... $is\n"; }
}


More research...

The search space can restricted to 1/9th of its current space. The sum of the digits must be 10. Why? Because its the number of times each digit shows up in a 10 digit string. Therefore, the only possible valid numbers are 1 + n*9.

n*9 has the property that the sum of the digits is 9. Search time down to 10 days.

Although I can't read russian, I do believe that this is the only such number of its type. Source: http://www.comptek.ru:8100/company/digits/index.html


The question of other bases has come up.
  1. For a base n, the number of digits (or bits, or octits) is equal to the base.
  2. The range of numbers is 0 .. n-1
  3. Sum(digits) = n
  4. Raw search space: nn
    This goes up very fast.
    For n=10, the size is 10,000,000,000 (10 billion).
    For n=16, the size is 18,446,744,073,709,551,616 (~1.85 million times larger than the n=10 space)
  5. Optimized search space: (nn)/(n-1). This is because of (B) above. This is only intuitively known for n=10 because of the property of multiples of 9. This leads to m_turner's postulate.

The following table is for base n numbers of length n to see if they are any self descriptive numbers in that base.

  1. Not Applicable.
  2. No existing valid string. 4 possible numbers: 00, 01, 10, 11. None of them express the number.
  3. No existing valid string. 27 possible numbers, of which (E) above reduces to : 111, 012, 021, 102, 201, 120, 210. None of these express themselves.
  4. 256 possible numbers.

I did some work on this, and...
Disclaimer: this isn't a formal proof, and some things may be left out (like saying we're using integers), but it should be clear what is happening.

First thing, it helps to realize that this isn't really a number, its a list of digits.

Second thing, I changed the order around to make things easier - instead of the order:
      number of 1s, number of 2s, etc., number of 9s, number of 0s,
I used:
      number of 9s, number of 8s, etc., number of 0s,
which means
      2100010006
      1234567890 (position)
becomes
      0001000126
      9876543210 (position).
So, for base b, let n equal b - 1 (for convenience). Then, the digits are
      dn , dn-1 , dn-2 , ... , d1 , d0
This means that di, where i is an integer between 0 and n, inclusive, is the count of the number of is in the full number. For example, in decimal and using 0001000126, the digits are d9 to d0 , and d0 = 6, d1 = 2, d3 = 1, etc.

From that, it is possible to determine some rules.
As m_turner stated, the sum of the digits equals the base. This means
      dn + dn-1 + ... + d1 + d0 = b = n + 1
Note that for all digits, i must occur di times (that is why this is so special in the first place). This yields two things.
The first is:
      dn(n) + dn-1(n-1) + ... + d1(1) + d1(0) = n + 1
which reduces to
      dn(n) + dn-1(n-1) + ... + d1(1) = n + 1 ,
and the second is that di i must be less than b = n + 1, for all i :
      di < trunc( (n + 1) / i ) ,
where trunc is the round-down function (so, for example, trunc(2), trunc(2.4), trunc(2.5), and trunc(2.9) are all equal to 2). Using this second fact, n occurs dn times, so
      dn < trunc( (n + 1) / n ) = a value between 1 and 2, for bases 3 and higher,
which reduces to
      dn < 1 ,
which means
      dn = 0
which reduces the search space from nn to nn - 1.
Note: since that equals 0, then there must be at least one 0:
      d0 ≥ 1, or d0 is greater than or equal to 1 .

That is all I've determined so far, you may want to try finding the range other di values can be, using the trunc inequality.

There are several optimisations that can be performed on the brute force algorithm on the most obvious search space, for finding strings like this.

The solution to the problem contains 10 digits, and each digit contains a number from 0 to 9. This means the most obvious search space is the set of all strings 0000000000 to 9999999999, or 10,000,000,000 search items. This space can be drastically reduced with some logic applied to the problem in advance.

First, as has been pointed out by m_turner, the sum of all the digits must be 10 (in Eindhoven notation, using N-Wing's symbols, (+ : 0 ≤ i < 10 : di) = 10). So, if values are chosen for digits d9 to d1, there is only one possible valid value for d0 = 10 - (+ : 0 < i < 10 : di). This reduces the search space by a factor of 10. (If the computed value for d0 is negative, then the chosen values for d9 to d1 are invalid. Indeed, if the computed value is 0, then you don't have a valid string either.)

Second, as has been pointed out by N-Wing, the sum of all the digits di multiplied by their position in the string i must be 10, i.e. (+ : 0 ≤ i < 10 : (i * di)) = 10. Since 0 * x = x for all x, this expression is equivalent to (+ : 0 < i < 10 : (i * di)) = 10. d1 can be isolated from the equation, d1 = 10 - (+ : 1 < i < 10 : (i * di)). This reduces the search space by another factor of 10. (Again, if the computed value for d1 is negative, then the previously chosen values for the string cannot make a valid solution.)

Applying the same formula in the above paragraph in a different way, we have that for each i, (i * di) ≤ 10. This leads to the third optimisation (also suggested by N-Wing): instead of checking every digit di with values 0 to 9, check di with values 0 to floor(10 / i). d9 cannot be 2 or greater, because then (9 * d9) > 10 so (+ : 1 < i < 10 : (i * di)) > 10. Similarly, d8, d7, and d6 cannot be 2 or greater. d5 and d4 cannot be 3 or higher, d3 cannot be 4 or higher, and d2 cannot be 6 or higher. This reduces the search space to 2 * 2 * 2 * 2 * 3 * 3 * 4 * 6, or 27 * 33 = 128 * 27 = 3456.

This final optimisation can be pursued even more aggressively, in that, for example, at most one of d9, d8, d7, and d6 can be 1 (because if d7 and d6 were both one, 7 * d7 + 6 * d6 = 7 * 1 + 6 * 1 = 7 + 6 = 13 > 10). This reduces the search space to 40.

The following is a Lua program for showing all these types of strings in any specified base.

-- To run, type:
-- lua -f Problem.lua B
-- where Problem.lua is the name of this file
-- and B is the base


Problem = {}

Problem.Show = function()
  write ("Solution:")
  local i = Problem.B
  while (i > 0) do
    i = (i - 1)
    write (" " .. Problem.A[i])
  end
  write ("\n")
end

Problem.Check = function()
  local Test, i, success = {}, Problem.B, 0
  while (i > 0) do
    i = (i - 1)
    Test[i] = 0
  end
  i = Problem.B
  while (i > 0) do
    i = (i - 1)
    local x = Problem.A[i]
    Test[x] = (Test[x] + 1)
  end
  i = Problem.B
  while ((i > 0) and (success ~= nil)) do
    i = (i - 1)
    if (Test[i] ~= Problem.A[i]) then
      success = nil
    end
  end
  Problem.Checked = (Problem.Checked + 1)
  return (success)
end

Problem.Solve1 = function(n, Total0, Total1)
  if (n < 2) then
    Problem.A[1] = (Problem.B - Total1)
    if (Problem.A[1] >= 0) then
      Total0 = (Total0 + Problem.A[1])
      Problem.A[0] = (Problem.B - Total0)
      if (Problem.A[0] > 0) then
        if (Problem.Check() ~= nil) then
          Problem.Show()
        end
      end
    end
  else
    Problem.A[n] = 0
    repeat
      Problem.Solve1((n - 1), Total0, Total1)
      Problem.A[n] = (Problem.A[n] + 1)
      Total0 = (Total0 + 1)
      Total1 = (Total1 + n)
    until ((Total0 >= N) or (Total1 > N))
  end
end

Problem.Solve = function(b)
  Problem.A = {}
  Problem.B = b
  Problem.Checked = 0
  Problem.Solve1((b - 1), 0, 0)
end


B = tonumber(arg[1])
if ((arg.n ~= 1) or (type(B) ~= "number") or (B <= 0)) then
  write ("I need a base, B (and nothing more)\n")
else
  Problem.Solve(B)
  write ("Size of search space : " .. Problem.Checked .. "\n")
end

One final tweak would be to implement N-Wing's final point; fix db - 1 (Problem.A[b - 1]) to 0.

This challenge is similar to the following number puzzle, which I found on math.stackexchange, here:


Given that all the underscores receive one-digit numbers, can you fill this page out so it is true?
+----------------------------------------------+
| The number 0 appears _ time(s) on this page. |
| The number 1 appears _ time(s) on this page. |
| The number 2 appears _ time(s) on this page. |
| The number 3 appears _ time(s) on this page. |
| The number 4 appears _ time(s) on this page. |
| The number 5 appears _ time(s) on this page. |
| The number 6 appears _ time(s) on this page. |
| The number 7 appears _ time(s) on this page. |
| The number 8 appears _ time(s) on this page. |
| The number 9 appears _ time(s) on this page. |
+----------------------------------------------+


It's an interesting twist to the number tricks above, mostly because every number appears at least once.

There are a number of interesting explanations on how to get the solution at the question page, but the most intuitive—indeed, the one by which I solved it myself—is detailed below.

(You may wish to pause here in case you want to try it yourself!)

As all the numbers to fill in are restricted to being one digit positive integers, 0 cannot appear more than once, and all but one of the high numbers (5 to 9 definitely, debatably also 3 and 4) will also appear once, where the odd one out can only appear twice.

2, therefore, will be appear at least twice, once for the "The number 2 appears" part and once in the underscore of the large number. But filling in 2 with a 2 will mean that you have actually 3 2s.

This can be resolved by giving 3 a 2 and 2 a 3; so long as no other numbers besides 2, 3, and the large one have 2s or 3s, we're safe.

As the number of 1s will therefore be one for zero, and one for every number greater than 3 (except one), we get 1(0) + 1(sentence) + 6(>3) - 1(the non-1) = 7 1s. Thus the 7 appears twice and the 1 appears seven times.

The solution is then:
+----------------------------------------------+
| The number 0 appears 1 time(s) on this page. |
| The number 1 appears 7 time(s) on this page. |
| The number 2 appears 3 time(s) on this page. |
| The number 3 appears 2 time(s) on this page. |
| The number 4 appears 1 time(s) on this page. |
| The number 5 appears 1 time(s) on this page. |
| The number 6 appears 1 time(s) on this page. |
| The number 7 appears 2 time(s) on this page. |
| The number 8 appears 1 time(s) on this page. |
| The number 9 appears 1 time(s) on this page. |
+----------------------------------------------+

Self-referential puzzles like these are always fun to hand to more casual puzzle-solvers, since they typically have plenty of false starts and get blindsided by the one minute factor they forget about and they end up kicking themselves at the end when they figure it out. Moments of epiphanic realization like those are truly beautiful.

Log in or register to write something here or to contact authors.