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.

About these ads

Pages: 1 2

6 Responses to “Oban Numbers”

  1. […] 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 […]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/10/01/programming-praxis-oban-numbers/ for a version with comments):

    obans :: [Int]
    obans = filter (notElem 'o' . spell) [1..999] where
        spell n | n <  20 = ones !! n
                | n < 100 = tens !! div n 10 ++ spell (mod n 10)
                | True    = spell (div n 100) ++ "hundred" ++ spell (mod n 100)
        ones = "" : words "one two three four five six seven eight \
                          \nine ten eleven twelve thirteen fourteen \
                          \fifteen sixteen seventeen eighteen nineteen"
        tens = "" : "" : words "twenty thirty forty fifty sixty \
                               \seventy eighty ninety"
        tens = "" : "" : words "twenty thirty forty fifty sixty \
                               \seventy eighty ninety"
    
    main :: IO ()
    main = mapM_ print obans
    
  3. Remco Niemeijer said

    Whoops. Accidentally duplicated the tens definition. Here’s the correct version:

    obans :: [Int]
    obans = filter (notElem 'o' . spell) [1..999] where
        spell n | n <  20 = ones !! n
                | n < 100 = tens !! div n 10 ++ spell (mod n 10)
                | True    = spell (div n 100) ++ "hundred" ++ spell (mod n 100)
        ones = "" : words "one two three four five six seven eight \
                          \nine ten eleven twelve thirteen fourteen \
                          \fifteen sixteen seventeen eighteen nineteen"
        tens = "" : "" : words "twenty thirty forty fifty sixty \
                               \seventy eighty ninety"
    
    main :: IO ()
    main = mapM_ print obans
    
  4. Sam said

    – 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

  5. Iain said

    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()

  6. Khanh said

    Similarly, mine in F#

    let rec isOban(n : int) =
        let digits = [""; "one"; "two"; "three"; "four"; "five"; 
                      "six"; "seven"; "eight"; "nine"; "ten"; "eleven";
                      "twelve";"thriteenth"; "fourteenth"; "fifteenth"; "sixteenth";
                      "seventeenth"; "eighteenth"; "nineteenth"]
        let tens   = [""; ""; "twenty"; "thirty"; "fourty"; "fifty"; "sixty";"seventy"; "eighty";"ninety"]
        
        if n < 20 then
            not (digits.[n].Contains("o"))
        elif n < 100 then        
            not(tens.[n/10].Contains("o")) && (isOban(n % 10))
        elif n < 1000 then 
            not(digits.[n / 100].Contains("o")) && (isOban(n % 100))
        else false
    
    
    let l = List.filter isOban [1..1000] |> List.length
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: