Advanced Search
All Posts :
The IBM Research August 2005 Ponder This challenge is out. The attached 11 line Maple procedure solves it in just under 2.5 seconds. Don't look at my solution if you want to do this yourself. When I attempted to attach the file an error was generated indicating that the extension was invalid. This was a text file named ponderthis.mpl. Are only worksheets attachable? I converted the text file to a Maple worksheet and attached that. I also added a comment about anonymous procedures and a problem that could arise if unknown were assigned. I wonder whether it should be a protected symbol. I've updated the worksheet to include Thomas Richard's mention of a slightly different version. Experimenting with it over various bases suggests that with that version, the maximal solution has one less figure ("digit") than the base. Can you prove/disprove that conjecture? That might be worthy of a "Ponder This" challenge (this one was on the easy side). On second thought, maybe not. It's trivial to prove that no solution can have a number of digits equal to its base. Its also easy to prove that every base has a solution with base-1 "digits". Consider the original problem, but generalized to base b ("digits" correspond to those appropriate to the base). That is, for k as large as possible, produce a k-"digit" integer m such that for n=1..k the integer given by the first (left-most) digits of m is divisible by n. Now, attempt to compute the expected number of digits. It is easy to show that for any base b, there exists solutions with b digits. Let's estimate the expected number of digits in excess of that. Given a solution with b+k digits, the probability of there being a b+k+1 digit is b/(b+k+1). The probability of there being exactly b+k digits is then (1) Pk = b^k*b!/(b+k)!*(1-b/(b+k+1)). The expected number of excess digits is (2) ExcessDigits = sum(Pk*k,k=1..infinity). Using Maple to evaluate this we get a moderately complicated expression in terms of the GAMMA function. A reasonable approximation to it is (3) ExcessDigits ~ 5/4*sqrt(b)-3/5. Alas, this expression is not close to the computed values. The probabilistic approach does not work.
convert infinity integer procedure

Please Wait...