Shorts
The Nine Billion names of God
Email this post
⋅ 
Print this post
⋅ Post a comment
Arthur C. Clarke wrote a classic SF short story in the 1950s called The Nine Billion names of God, in which he discusses a computer designed and built for a Buddhist monastery to calculate the billions of possible names possible for God, using the entirety of the possible combinations of available characters.
"We use a special alphabet of our own" describes the lama. So how many characters are they using? Their limit on the length of the names is nine characters - so if we assume they plan to use words of any length up to nine characters, the number of possible names can be expressed as
Where A is the number of characters in their alphabet.
So, assuming 1 billion is 10^12:
-
When A=26, the number of possible names is 5.65 billion
-
When A=27, the number of possible names is 7.92 billion
-
When A=28, the number of possible names is 10.97 billion
Obviously none of these results can be rounded to the nearest billion, to give nine billion. Even if we assume Clarke means only names that are nine characters long (the number of which could be expressed as A^9), we are still left with no results which round to nine billion.
Obviously given that we lack the exact alphabet used, it is impossible to reproduce the exact process described - but what if we were to try the same in Python, using our own alphabet?
alphabet = tuple('abcdefghijklmnopqrstuvwxyz')
def names(length, prefix=''):
_for char in alphabet:
__print prefix + char
__if length - 1:
___names(length - 1, prefix + char)
To test this process, I used an alphabet consisting of 'a' and 'b', with a maximum word length of two characters. And it appeared to work:
a
aa
aaa
aab
ab
aba
abb
b
ba
baa
bab
bb
bba
bbb
I ran a full 26 word alphabet with a maximum word length of nine characters for ten minutes. It reached 'aaaaajjnk'.
At the end of Clarke's story, the machine finishes its task, and the stars are described as going out, one by one.
Anyone care to try?
Popularity: 8%
6 votes, average: 3.5 out of 5
Loading ...Discussion
5 comments for “The Nine Billion names of God”
Post a comment
Challenge accepted. Removed recursion and used Perl's internal counting mechanism.
use strict;
my $root = "a";
while($root le "zzzzzzzzz") {
print $root . "\n";
$root++;
}
I haven't read the story for quite a while, but I do seem to remember that one of the limitations was that a letter could not be repeated more than three times in a row, ie. zzzaaazzz was valid, but zzzaaaazz was not. This may have some effect on the total number of possibilities.
Darren.
9 Billion names, but not all the combinations were valid names. Hence A could well equal 28 or more.
i hate u
I just modified JT's code to strip out strings with letters repeated four times in a row (
print "$root\n" unless $root =~ /(.)\1{3}/), then ran some timings and determined it would take over 600 hours to finish. It's possible to work out the numbers using the inclusion-exclusion principle, but it's going to be a messy calculation. Still, nice to know that sometimes pencil and paper can be faster than computing :-)