Lottery Ball Problem A woman works at a lottery ball factory.  She's instructed to open up a lottery ball creation kit composed of 1 red rubber ball and n strips of digits from 0 through 9.  

She's instructed to do the following:


Starting with 1, write the current number on the ball using the digits available on the n strips.  
Put unused digits into a bowl where they can be used later for when she runs out of available digits in step 1.  
Open up another lottery ball creation kit and continue to step 1 for the next number.


The question is, at what number will she arrive at before she runs out of digits to write the number?  Edited: Given n where n is the number of digit strips from 0 through 9 provided in each lottery ball creation kit, write a program that can solve this (not trivially) in the least amount of time.  

Edit:  Additional notes - 6 and 9 are different numbers.  Assume there are no limits to the number of digits that can be pasted on the ball.  

Hint:  If she counted in base 2 rather than base 10, how would that change the result and would that be easier to calculate?  What could you derive from solutions in base 2?
edit 2: fixed

General solution for n > 1:

-- lottery2.hs

import System
import Control.Monad
import Data.Maybe

main = mapM_ print . map (solve . read) =&lt;&lt; getArgs

rdigits 0 = []
rdigits n = (n `mod` 10) : rdigits (n `div` 10)

digits = reverse . rdigits

undigits = foldl ((+) . (10*)) 0

c1 = c . digits

c [] = 0
c [0] = 0
c [_] = 1
c (0:xs) = c xs
c (1:xs) = d xs + c xs + undigits xs
c (x:xs) = c xs + x * (d xs - 1) + 10 ^ length xs

d xs = ds !! length xs

ds = map d' [0..]
  where d' n = c1 (10 ^ n - 1) + 1

maxVal n =
  fst . head . filter (uncurry $ (&lt;) . (*n))
  . map (liftM2 (,) undigits c . (1:) . flip replicate 9) $ [0..]

search f p q a b = s f (uncurry p) q (a, f a) (b, f b)
  where 
    s f p q a b
      | not (p a) = Nothing
      | fst a + 1 == fst b = guard (not $ p b) &gt;&gt; return (fst a)
      | a &gt;= b = Nothing
      | q a b = maybe (s f p q k b) Just (s f p q a k)
      | otherwise = Nothing
        where k = ((fst a + fst b) `div` 2, f (fst k))

solve n = fromJust $ search c1 ((&gt;=) . (*n)) q 1 m
  where 
    m = maxVal n
    q (a, fa) (b, fb) = (a * n) - fa &lt;= fb - fa


There seems to be a pattern here:


$ ghc -O --make lottery2.hs
Linking lottery2 ...
$ time ./lottery 1 2 3 4 5 6
199990
1999919999999980
19999199999999919999999970
199991999999999199999999919999999960
1999919999999991999999999199999999919999999950
19999199999999919999999991999999999199999999919999999940

real    0m3.580s
user    0m3.508s
sys     0m0.020s
$ time ./lottery 7 8 9 10 11 12
199991999999999199999999919999999991999999999199999999919999999930
1999919999999991999999999199999999919999999991999999999199999999919999999920
19999199999999919999999991999999999199999999919999999991999999999199999999919999999918
199991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999917
1999919999999991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999916
19999199999999919999999991999999999199999999919999999991999999999199999999919999999991999999999199999999919999999915

real    1m10.855s
user    1m3.868s
sys     0m0.324s