usage = "
The Division String Problem: (David M. Sanger)
  Find a maximal integer  a_1 a_2 ... a_t, consisting of t decimal digits
  a_1 , a_2 , ... , a_t (also with t maximal), such that  a_1 a_2 ... a_i
  is divisible by i, for i=1,2,3,...,t , or show that there is no upper bound
  for the collection of these integers.
 
Equidistribution Heuristic:
  Let D(n) be division strings of length n except the all zero string.
  Assuming that a(n,i) = { x in D(n-1) with x mod n = i } are nearly
  equal for all i with 0<=i<n. Then we expect d(n) strings and get
    d(n) = 10/n d(n-1)  that is  d(n) = 10^n / n!
  That is the total number of strings is exp(10) = 22026.4
  There is a special string of all zero digits. This one is valid for all n.
  The equidistribution assumption is not good for this one. Therefore
  calculate its nonzero follow up strings. There are floor(9/n) ones.
  Then we have the recurence for the non-zero strings
    d'(n) = 10/n d'(n-1) + floor(9/n)  and  d'(0) = 0.
  Their total sum is 22146.54 which is a close to the actual number 22809.


References:

- Martin Gardner;
  The Magic Numbers of Dr. Matrix
  Prometheus Books (1985)
  Chapter 21: Chautauqua

- Stewart Metchette;
  Progressively Divisible Numbers,
  Journal of Recreational Mathematics 15:2 (1982-83) 119-122

- ???;
  What's In a Number?,
  The Mathematical Gazette 67 (Dec. 1983) 281-282

"
puts usage

list = [""]
v = Array.new(31,0)

while it = list.shift
  len = it.length
  v[len] = v[len] + 1
  for d in '0'..'9'
    its = it + d
    if (its.to_i % (len+1) == 0) 
      # puts its
      list << its if len < 30
    end
  end
end

# number of solutions
base = 10
ev = Array.new(31,0.0)
for n in 1..30
  small_n = (base-1)/n
  ev[n] = base*ev[n-1] / n + small_n
end

# print table with number of solutions
sumv = sumev = 0
puts "  n d'(n)  d''(n) "
puts "------------------"
for n in 0..30
  printf "%3d %5d %8.2f\n",  n, v[n]-1, ev[n]
  sumv  = sumv  + v[n]-1
  sumev = sumev + ev[n]
end
puts "------------------"
printf "sum %5d %8.2f\n", sumv, sumev
puts " D'(n)  : division strings of length n except the all zero string"
puts " d'(n)  : number of division strings of length n"
puts " d''(n) : expected number of division strings of length n"