2100010006 (idea)

This program takes 15 cpu seconds on my system to do 10⁴ tests. The time taken is constant for all numbers. For 10¹⁰ tests, it would take 10⁶ * 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: nⁿ
   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: (nⁿ)/(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.