The Nine Billion Names of God with Raku - Part 1: Introduction

[ Index | Introduction | Base | Recursion | Loops | Summary | RakuConf ]

In the short story The Nine Billion Names of God from 1953, science fiction author Arthur C. Clarke had Tibetan monks hire a couple of Americans to compute the nine billion names of god for them. The task would have taken the monks 15,000 years to do by hand, according to Clarke, so they wanted to have a go at contemporary modern technolgy to speed it up. The premises are: A custom alphabet Maximium name length: 9 characters No more than three identical letters in succession Nine billion names (give or take) altogether

Note that Rosetta Code has solutions to this task - but they have rewriten the task quite a bit - actually so much so that I do not recognize it at all. This variation (their word) is probably on purpose.

Clarke has not divulged the actual alphabet, for reasons that should be fairly obvious if you have read the short story. Do read it, by following the link above, if you have not done so already...

We are not really interested in the words themselves, nor the letters in the alphabet, just the number of letters in the alphabet required to get to the nine billion words. Clarke failed to disclose this as well. Well, he may not actually have had any means of figuring it out. (Not that it actually matters in the short story.)

It is easy to compute this, as long as we disregard the succession premise.

Alphabet size 1: 9 words (0% of target)
Alphabet size 2: 1022 words (0% of target)
Alphabet size 3: 29523 words (0.0003% of target)
Alphabet size 4: 349524 words (0.0038% of target)
Alphabet size 5: 2441405 words (0.0271% of target)
Alphabet size 6: 12093234 words (0.1343% of target)
Alphabet size 7: 47079207 words (0.5231% of target)
Alphabet size 8: 153391688 words (1.7043% of target)
Alphabet size 9: 435848049 words (4.8427% of target)
Alphabet size 10: 1111111110 words (12.3456% of target)
Alphabet size 11: 2593742459 words (28.8193% of target)
Alphabet size 12: 5628851292 words (62.5427% of target)
Alphabet size 13: 11488207653 words (127.6467% of target)
Alphabet size 14: 22250358074 words (247.2262% of target)

We need an alphabet with 13 or 14 letters, depending on how much spillage the succession premise will cause. Feel free to have a guess.

The program used to generate the values:

#! /usr/bin/env raku

my $target = 9_000_000_000; # Nine billion

for 1 .. Inf -> $alphabet-size                    # [1]
{
  my $count = 0;

  for 1 .. 9 -> $word-length                      # [2]
  {
    $count += $alphabet-size ** $word-length;     # [2a]
  }

  my $pct = (1000000 * $count/$target).Int / 10000;
  say "Alphabet size $alphabet-size: $count words ($pct% of target)";
  last if $pct > 200;                             # [3]
}

[1] For each alphabet size, (and note the exit strategy in [3].)

[2] Count all the 1 character words, 2 character words, ... and nine character words and add them all together.

[3] Stop after reaching 200% percent or more.

We'll have a look at the Base approach (using the base function) in the next part.

[ Index | Introduction | Base | Recursion | Loops | Summary | RakuConf ]