John, If you had to count to 9 billion, even US billions, you'd need an integer bigger than INTEGER4. Computers I used in the 60s used 24-bit words, and used 2 words for an INTEGER. They could hold 9 billion - even the UK 10^12 billion then in use. Two 24 bit words are effectively INTEGER6. In other words, the job was doable back then. INTEGER*8 is overkill for that job.
Incidentally, the program would probably print out the 9-character names on a 132 column line printer, say 12 or 13 on a line, once the algorithm had found that many names, so apart from keeping count, the storage requirements were tiny. Assuming that the Tibetan character set was implemented on the lineprinter., all the algorithm had to do was to permutate all combinations and reject those that didn't make sense - the story explains that in principle not in detail.
It couldn't have been done in Fortran in 1953, but only in assembly language, and so the absence of a CHARACTER type is of no consequence.
I'm not sure that the computers of 1953 (when the story was written) were up to the job - those of the mid to late 60s certainly were.
Eddie