Suppose the integers from 1 to 10,000,000,000 are ordered alphabetically as spelled out in American English, according to the rules below. Find the first odd number in this ordering.
(1) Numbers are spelled out formally, using neither "and" nor common shortcuts. For example, 2400 is two thousand four hundred, not twenty-four hundred.
(2) To alphabetize, ignore any spaces or hyphens. For example, sixteen comes before six thousand.
This problem is one of the easier ones in Peter Winkler's excellent collection, Mathematical Puzzles: A Connoisseur's Collection. It is an excellent problem to give to students working together in small groups. Usually students will have to make many attempts along the way to finding the solution, giving everyone a chance to participate. Note the specification of American English. Many people don't realize that there is a difference between American English and British English in some number names. For example, "billion" has different meanings in the two forms of English.
It might make an interesting exercise to write an algorithm for converting an integer (say in the range specified in this problem) to the spelled out form.