This program takes 15 cpu seconds on my system to do 10
4 tests.
The time taken is constant for all numbers. For 10
10 tests,
it would take 10
6 * 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.
- For a base n, the number of digits (or bits, or octits) is
equal to the base.
- The range of numbers is 0 .. n-1
- Sum(digits) = n
- 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)
- 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.
- Not Applicable.
- No existing valid string. 4 possible numbers: 00, 01, 10,
11. None of them express the number.
- 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.
- 256 possible numbers.