Oban Numbers
October 1, 2010
We need a function that converts numbers to words. Scheme doesn’t provide one, so we write our own:
(define (num->words n)
(letrec ((ones '("" "one" "two" "three" "four" "five" "six"
"seven" "eight" "nine" "ten" "eleven" "twelve"
"thirteen" "fourteen" "fifteen" "sixteen"
"seventeen" "eighteen" "nineteen"))
(tens '("" "" "twenty" "thirty" "forty" "fifty"
"sixty" "seventy" "eighty" "ninety"))
(groups '("" "thousand" "million" "billion" "trillion"
"quadrillion" "quintillion" "sextillion"
"septillion" "octillion" "nonillion" "decillion"
"undecillion" "duodecillion" "tredecillion"
"quattuordecillion" "quindecillion" "sexdecillion"
"septendecillion" "octodecillion" "novemdecillion"
"vigintillion"))
(nnn->words (lambda (n) ; three-digit numbers
(cond ((<= 100 n)
(string-append
(list-ref ones (quotient n 100))
" hundred"
(if (positive? (modulo n 100)) " " "")
(nnn->words (modulo n 100))))
((<= 20 n)
(string-append
(list-ref tens (quotient n 10))
(if (zero? (modulo n 10)) ""
(string-append "-" (list-ref ones (modulo n 10))))))
(else (list-ref ones n))))))
(cond ((negative? n) (string-append "negative " (num->words (- n))))
((<= #e1e66 n) (error 'num->words "out of range"))
((zero? n) "zero")
((< n 1000) (nnn->words n))
(else (let loop ((n n) (groups groups))
(let ((prev (quotient n 1000))
(group (modulo n 1000)))
(string-append
(if (zero? prev) ""
(loop prev (cdr groups)))
(if (zero? group) ""
(string-append
(if (positive? prev) " " "")
(nnn->words group)
(if (string=? "" (car groups)) ""
(string-append " " (car groups))))))))))))
With that, it’s easy. There are 454 oban numbers between zero and one thousand. There can be no other oban numbers, since any larger numbers include either the word “thousand” or the suffix “illion” in their spelling (Sloane’s A008521):
(for-each
(lambda (n) (display n) (newline))
(list-of n (n range 1000) (not (string-index #\o (num->words n)))))
We used list comprehensions and string-index from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/pN3VLfJP.
[…] Praxis – Oban Numbers By Remco Niemeijer In today’s Programming Praxis exercise, our task is to print a list of all Oban numbers (numbers that […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/10/01/programming-praxis-oban-numbers/ for a version with comments):
Whoops. Accidentally duplicated the tens definition. Here’s the correct version:
— We don’t really need to spell them out, do we?
obanNumbers = filter (mkOban . show) [1..]
mkOban :: String -> Bool
mkOban [] = True
mkOban [‘1’,_] = True
mkOban (‘1’:_) = False
mkOban (‘2’:_) = False
mkOban (‘4’:_) = False
mkOban (x:xs) = mkOban xs
Sam, I don’t think your version would print 11 or 12, which are oban numbers. I’m not sure, because I don’t read Haskell, though.
Here’s my Python version. It came out very similar to Remco’s version.
def int2str(num):
to_20 = [”, ‘one’, ‘two’, ‘three’, ‘four’, ‘five’, ‘six’, ‘seven’, ‘eight’,
‘nine’, ‘ten’, ‘eleven’, ‘twelve’, ‘thirteen’, ‘fourteen’,
‘fifteen’, ‘sixteen’, ‘seventeen’, ‘eighteen’, ‘nineteen’]
tens = [”, ”, ‘twenty’, ‘thirty’, ‘forty’, ‘fifty’, ‘sixty’, ‘seventy’,
‘eighty’, ‘ninety’]
if num < 20:
return to_20[num]
if num < 100:
return tens[num // 10] + ' ' + to_20[num % 10]
else:
return to_20[num // 100] + ' hundred ' + int2str(num % 100)
def oban():
return [i for i in range(1000) if int2str(i).find('o') == -1]
print oban()
Similarly, mine in F#