<< Heh, here's a puzzle: take a pool of random positive, reduced rational numbers. Repeatedly Take out five of them at random, q, r, s, t, u. x = (p q + r s) / t Replace a random member of the pool with x in reduced form. How fast does the number of bits in the pool grow? >> Execution halts with "variable unassigned" or whatever --- trick question? WFL On 7/24/13, Steve Witham <sw@tiac.net> wrote:

...

From: Steve Witham <sw@tiac.net>

Visualize an array of the coefficients, with the iterations as rows. Say t is the row number, starting at zero.

The column for the constant term is all zero. the coefficient of x is all 1, constant down the column x^2, a linear progression x^3, a quadratic x^4, a cubic ...

From: Dan Asimov <dasimov@earthlink.net>

Thanks for the elaboration.

How do you do this step:

"I inferred polynomials of t from the columns, giving a polynomial in both x and t."

I noticed that the coefficients for x^2 were 0, 1/2e, 1/e, 3/2e, etc. just by eye, and "inferred" t/2e, then guessed and verified that the next column was following a quadratic, the next a cubic. Then I wrote code to do the Method of Divided Differences... maybe "infer" is to strong a word for that. Cribbed from http://en.wikipedia.org/wiki/Newton_form

So, each coefficient of a power of x in the result, is a polynomial in t, so it's all a polynomial of x and t.

Later I convinced myself that the pattern really must fall out of substituting polynomials of the form x + a_2 x^2 + a_3 x^3 ... into a polynomial of the same form.

Describing all this makes me wonder where I've gone ill-founded. The final polynomial for f^t(1/2) always has a single negative coefficient at the second-to-last term, for instance. And I'm wondering why my computer didn't run out of space for digits of the polynomial coefficients when f^14(1/2) should be like e^e^1000000. I guess the coefficients decrease forever, but super-slowly.

Heh, here's a puzzle: take a pool of random positive, reduced rational numbers. Repeatedly Take out five of them at random, q, r, s, t, u. x = (p q + r s) / t Replace a random member of the pool with x in reduced form. How fast does the number of bits in the pool grow?

--Steve

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun