April 2013 - mathfun@mailman.xmission.com

[math-fun] Sums of digits of powers of 2
by James Propp 20 Apr '13

20 Apr '13

Let E(n) and V(n) be the expected value and variance, respectively, of the sum of n independent draws from {0,1,2,...,9}; we can easily write E(n) and V(n) in closed form, and thereby extend to E(x) and V(x) where x is any positive real number. Let S(n) be the sum of the digits of 2^n, and let c = log_10 2, so that 2^n has about cn digits. What if anything is known (empirically or rigorously) about the distribution and autocorrelations of the sequence D_n whose nth term is (S(n)-E(cn))/sqrt(V(cn))? If that's obscure, just think of it as the sum of the digits of 2^n, adjusted to make it look like a Gaussian of mean 0 and variance 1. (The "D" is for discrepancy.) Jim Propp

5 6

[math-fun] "Ponder This"
by Lee Sallows 20 Apr '13

20 Apr '13

I'm usually a Silent Watcher on this forum, but with ELEVEN + TWO = TWELVE + ONE quoted, I cannot resist plugging my own creation in Spanish: UNO + CATORCE = CUATRO + ONCE and DOS + TRECE = TRES + DOCE That is, 1 + 14 = 4 + 11 and 2 + 13 = 3 + 12 Lee

1 0

Re: [math-fun] A grid with MAX
by Steve Witham 20 Apr '13

20 Apr '13

If you fill in a path backwards, the score is the same. (This is easy to see for symmetrical paths like the max of the 4x4, but it's true generally.) If you break a path into two parts, and write down all the numbers the first part going forward and for the second part backward, you can then compute the score for the combined path by summing the products of across-the-border neighbors (without needing to remember where the paths go). For instance, here's the 4x4 winner split down the middle: 1 1 | 1 1 2 4 | 4 2 6 18 | 18 6 6 30 | 30 6 You might write the total as: (1 + 4) * 1 + (1 + 4 + 18) * 4 + (4 + 18 + 30) * 18 + (18 + 30) * 30 = 2473 and pre-calculate the parenthesized expressions for a given left-half-path. This by itself doesn't reduce the capital-O order of the search. But in the example above, (30 + 18)**2 = 2304, which accounts for about 98% of the total. Seems true usually. I think it hints at ways to rate half-paths independently and cut the search with branch-and-bound. (And then there's recursive subdivision.) Exploiting this looks wrinklier than I want to attempt. --Steve p.s. i guess generally a partial path is a matrix, the initial and final conditions are vectors (sometimes with only a single one), and the connections across a border form a matrix of ones and zeroes. i would love it if bras and kets were appropriate.

1 0

Re: [math-fun] Tan[Sin[x]]-Sin[Tan[x]] puzzles
by Henry Baker 19 Apr '13

19 Apr '13

Wow! That's an amazing picture! Is there any way to estimate the height/depth of the pits? Are they analogous to Gibbs's ears on square waves? If so, perhaps they have a finite size. http://en.wikipedia.org/wiki/Gibbs_phenomenon At 06:20 PM 4/18/2013, Bill Gosper wrote: >Whoa, those pits in the leaves <http://gosper.org/.flattop2.png> go deep. > >Roots? > >--rwg > >(I omitted the /2 in the exponent, since I wasn't fudging for â2âÏ.) > >(Trying to save selection as pdf crashes 9.0.1 for PlotPoints->666. And the plotting artifacts are worse.) > >On Wed, Apr 10, 2013 at 1:58 AM, Bill Gosper <billgosper(a)gmail.com> wrote: >> On Wed, Apr 10, 2013 at 1:09 AM, Bill Gosper <billgosper(a)gmail.com> wrote: >> >>> Here <http://gosper.org/flattop.png>'s a more traditional plot near z=0. >>> --rwg >>> >> Oops, and here's A. Goucher's missing antecedent: >> >> When you said `ultraflat', I thought you were referring to the property of all derivatives being zero at that point. >> Obviously, complex-differentiable functions (such as yours) cannot have this property (except for constant functions); >> >> however, there are infinitely differentiable examples over the reals such as f(x) = exp(-1/x^2). A function with this >> property is considered here: http://cp4space.wordpress.com/2013/02/28/radical-tauism/ >> > > Sincerely, >> > > Adam P. Goucher

1 0

Re: [math-fun] A grid with MAX
by Phil Carmody 18 Apr '13

18 Apr '13

For those doing this by hand - have fun, but be gentle. http://87.119.183.129/perl/gridsplode.pl Bugs can't be dealt with for at least 48 hours, so if it doesn't work, don't use it. Phil

5 7

[math-fun] The probability distribution arising from a decreasing function
by Warren D Smith 18 Apr '13

18 Apr '13

Let F(n) be any real-valued function of integer n>0 which decreases to limit value 0 and with F(1)=1. Let E>0 be fixed. R = limit (sum +-F(n)) / (sum F(n)^E)^(1/E) be a real-valued random variable (all +- signs independent fair coin tosses). The sums are n=1..N and the limit is N-->infinity. In this way, any such function F and number E>0 is associated with a probability distribution on the real line. What can we say about these distributions? 1. Normality. If F(n)=n^(-k), for fixed k>0, then R is a normal distribution if and only if k<=1/2 and E is large enough so that R is defined. [Proof: Lindeberg-Feller central limit theorem.] If k>1/2 then we can take E=infinity if we want to jettison the scaling factor, but anyhow we get a smooth but not normal density with finite variance (the variance is expressible using zeta function). 2. Uniform. If F(n)=2^(-n) then we get the uniform density in a certain real interval (and zero density outside). 3. Funny fractals. If F(n)=3^(-n) or indeed A^(-n) for any A>2, then we get a distribution supported on a Cantor set. 4. But if 1<A<2 then we get a smooth but not normal density with finite variance (the variance is expressible in close form). Are there, e.g, fast ways to evaluate these (new?) density functions?

1 0

[math-fun] how many records? Asymptotic normality and review
by Warren D Smith 18 Apr '13

18 Apr '13

>>Since the events that the i'th entry is a record are independent, doesn't > this follow from a central limit like theorem? The number of records is a > sum of independent binomial random variables, Bin(1,1/i). >Cris Moore --actually (after correction) this idea does work. The kth random variable (1 if new record, 0 if not) out of N has mean=1/k and variance=1/k-1/k^2. This instantly proves that mean=harmonic(N) and var=H(N,1)-H(N,2), the simplest such proof. Further, although the Lyapunov CLT I was using does not work in this scenario to prove normality, the Lindeberg-Feller CLT after addititive corrections the make the mean=0, *does* work. (Also described by John D. Cook: http://www.johndcook.com/central_limit_theorems.html) And that is the simplest proof of normality too (given these CLTs available) although somewhat deceptive since my old Lyapunov-based proof (which apparently was what Renyi had used too) makes the slow convergence clear, while this does not.

1 0

[math-fun] how many records? Asymptotic normality and review
by Warren D Smith 17 Apr '13

17 Apr '13

I claim that the number R of record-high entries in a left-right-scan of a random-ordered list of N distinct numbers, is ASYMPTOTICALLY (for N large) NORMALLY DISTRIBUTED. In this post I will sketch a proof. To first recall the preceding progress, I found a disgusting proof (too horrible to describe) that expect(R) = harmonic(N,1) variance(R) = harmonic(N,1) - harmonic(N,2) where harmonic(n,k) = 1 + 1/2^k + 1/3^k + ... + 1/n^k. It turns out these are not new (even though NIST Stirling number fact compendium is ignorant of all this...) and were known to Alfred Renyi in the early 1960s, as described in Ned Glick: Breaking records and breaking boards, Amer. Mathematical Monthly 85 (Jan. 1978) 2-26, on page 14. Renyi also recognized the connection to Stirling numbers. http://www.isse.ucar.edu/extremevalues/nedglick.pdf Then Cris Moore found a nice proof method, which shows 1: E[R] = H(N,1) 2: E[R(R-1)] = H(N,1)^2 - H(N,2) 3: E[R(R-1)(R-2)] = H(N,1)^3 - 3 H(N,1) H(N,2) + 2 H(N,3) 4: E[R(R-1)(R-2)(R-3)] = H(N,1)^4 - 6 H(N,1)^2 H(N,2) + 3 H(N,2)^2 + 8 H(N,1) H(N,3) - 6 H(N,4). where H(n,k)=harmonic(n,k).... and in principle Moore's techniques allow one to work out any "falling factorial moment", these being just the first 4 cases. Unfortunately it gets more and more mysterious fast what the Moorish formulae are as the order increases. However, it should be pretty obvious how to generalize the above 4 statements to any order provided we just say "for some unspecified coefficients". I.e. in claim 4, the coefficients 1,-6,3,8,-6 are mysterious, but Moore's method makes it clear that suitable integer coefficients always exist at any order, and at present the best way I know to find them at orders>4 is simply to regard them as undetermined and solve for them (using exact Gaussian elimination) to exactly fit data, which in turn is computed exactly for (enough) small N by brute force. OK, now to prove the asymptotic normality claim (the normal has the mean and variance formulas above). The idea is to partition the N numbers chronologically into "eras" where each successive era increases the total cardinality so far (including both it and all previous eras) by a factor of e. The count of records within each era is INDEPENDENT of the number in every other era. Furthermore, the exact mean and variance of the count (for each era) is exactly known. The counts within the eras are almost-identically-distibuted random variables. Specifically, asymptotically for high eras, the means are asymptotic to 1 and the variances also to 1. If "almost identically" were "identically" we would now be done because of the central limit theorem for sums of i.i.d. random variables with variance=1. We need a form of the central limit theorem valid for not-quite-identically distributed random variables. Upon reading this web page http://www.johndcook.com/central_limit_theorems.html by John D.Cook surveying such central limit theorems, his formulation of "Lyapunov's CLT" (although NOT wikipedia's lamer formulation of Lyapunov's CLT) seems to do the job, in view of the bounds on 4th moments arising from Moorism. To make a precise claim, (R-ln(N))/sqrt(ln(N)) is an asymptotically (when N-->infinity) normally distributed random variable with mean=0 and variance=1. Note that this asymptotic normality claim converges a lot slower than it usually does since it depends on ln(N) being large, vs usually N being large suffices. Now once we know this, it is trivial to write down asymptotic formulae for every (mean-centered) power-moment etc (since those all are exactly known for normal curve, computing them is just Euler's gamma function integral in disguise). And this also gives us a great deal of understanding of the asymptotic behavior of the Stirling numbers of the first kind (which again NIST compendium is ignorant of). But (annoyingly) the asymptotic normality claim also is not new and is stated by Glick on page 15 and again attributed to Renyi 1962. So, not much newness here. Moore's path to understanding is nicer than Glick's, I'll say that. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

Re: [math-fun] how many records?
by Warren D Smith 17 Apr '13

17 Apr '13

> From: Cris Moore <moore(a)santafe.edu> > Subject: Re: [math-fun] how many records? > The great thing about this problem is that if X_i is the event that the i'th > entry sets a record, these events are independent! To see this, note that > X_i occurs if the i'th entry is bigger than the previous i-1 entries, and > this has probability 1/i no matter what order the previous i-1 entries > occurred in. --True, but the expectation = harmonic(n) formula works without need of independence. I think Moore's point is this independence comes in handy when working on higher moments than the 1st. > To compute the moments, consider the generating function > > G(z) = \sum_{t=0}^n z^t Pr[there are t records]. > > Then > > G(z) = z (1+(z-1)/2) (1+(z-1)/3) (1+(z-1)/4) ... (1+(z-1)/n) . --this is the stirling number (first kind, unsigned) generating function, essentially. > Then for any k, the "k'th falling moment" E[t(t-1)(t-2)...(t-k+1)] is the > k'th derivative of G(z) at z=1. This is the sum over all distinct, ordered > k-tuples (i_1, ... i_k) of the product 1/(i_1 ... i_k). --k-tuples of what? The i_1,..., i_k need to be selected from {1,2,3...,n} without replacement, I think is what he meant. > I'll use Warren's notation H(n,k) = sum_{i=1}^n 1/i^k. For k=1, we get E[t] > = H(n,1). For k=2, we have > > E[t(t-1)] = H(n,1)^2 - H(n,2) > > since H(n,1)^2 is the sum over all ordered pairs (i_1,i_2), including > i_1=i_2, but we only want the distinct ones. --right. Now you are cooking with gas. > To get the variance, we write > > E[t^2]-E[t]^2 > = E[t(t-1)] + E[t] - E[t]^2 > = H(n,1) - H(n,2) . > > Let's do one more. The third falling moment is > > E[t(t-1)(t-2)] = H(n,1)^3 - 3 H(n,1) H(n,2) + 2 H(n,3) > > where we start with all 3-tuples, remove the ones where one i equals the > other two, --he meant "remove the ones with two i's equal" >and add back in (twice) the ones where they're all the same. > Cris --A generalization of Cris Moore's 3 formulas 1: E[t] = H(n,1) 2: E[t(t-1)] = H(n,1)^2 - H(n,2)3: E[t(t-1)(t-2)] = H(n,1)^3 - 3 H(n,1) H(n,2) + 2 H(n,3) 3: E[t(t-1)(t-2)] = H(n,1)^3 - 3 H(n,1) H(n,2) + 2 H(n,3) is j+1: E[t*(t-1)*(t-2)*...*(t-j)] = H(n,1)^(j+1) + s(j+1,j)*H(n,1)^(j-1)*H(n,2) + s(j+1,j-1)*H(n,3) where s(N,R) are the signed stirling numbers of first kind, note s(N,N)=1, s(N,0)=0, and we proclaim s(N,AnythingNegative)=0. That works for j=0,1,2 but is not the right generalization for larger j. Indeed the next one is 4: E[t(t-1)(t-2)(t-3)] = H(n,1)^4 - 6 H(n,1)^2 H(n,2) + 3 H(n,2)^2 + 8 H(n,1) H(n,3) - 6 H(n,4). I think the right generalization should involve multinomial coefficients with upstairs index j+1 and a sum over all partitions of j+1 (which go in the downstairs indices)... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Summing Pascal's triangle a la Euler
by James Propp 17 Apr '13

17 Apr '13

Euler was born on this date in 1707, and I'd like to propose in his honor a problem to be interpreted and solved in his spirit: find the sum of all the entries in Pascal's triangle. To those of you who object that the sum diverges, I'll point out that Euler was the guy who calculated 0!-1!+2!-3!+.... So don't give me any of that "But-the-sum-diverges!" stuff. To those of you who say "Well, the sum of the nth row (counting the top row as the n=0 row) is 2^n, so the sum of all the entries is the sum of the geometric series 1+2+4+8+..., which in Euler's formalistic mathematics is 1/(1-2) = -1; end of story," I'll say "That's good, except for the last three words," and then point out that Euler was the guy who calculated 0!-1!+2!-3!+... not just one way but half a dozen ways (see http://www.maa.org/editorial/euler/How%20Euler%20Did%20It%2032%20divergent%…) and got the same answer every time. So while the geometric series calculation is fine, we want to see other ways to arrive at the answer -1. Here's another way to get -1: Decompose Pascal's triangle into tilted rows as indicated below (where the elements of distinct tilted rows get assigned different letters): a c b e d c g f e d i h g f e etc. Then we get a = 1, b = 1, c = 2, d = 3, e = 5, f = 8, etc.: the familiar way to write Fibonacci numbers as sums of binomial coefficients. Now 1+1+2+3+5+... is the x=1 evaluation of the power series 1+x+2x^2+3x^3+5x^4+... = 1/(1-x-x^2), and plugging in x=1 gives 1/(1-1-1) = -1. If you use other tilted rows, you get other rational functions playing the role of 1/(1-x-x^2), such as 1/(1-x-x^3) and 1/(1-x^2-x^3), but for every such rational function that I've tried, plugging in x=1 gives -1. Does every decomposition into tilted rows give -1? (This is really a question about one-parameter specializations of the two-variable generating function associated with the rational function 1/(1-x-y), and is probably not that hard, but I haven't done it; maybe one of you will.) Here's a start of a different way to calculate the sum that I don't know how to push through (and this is my real reason for posting): Looking down the middle of the array, we get the sum 1+2+6+20+..., which is the x=1 evaluation of the power series 1/sqrt(1-4x), which "is" 1/sqrt(-3). On either side we get the sum 1+3+10+35+..., with combined sum 2+6+20+..., which is 1/sqrt(-3) - 1. On either side of that we get ... Can anyone finish this calculation? All the columns I've examined look "sqrt(1-4x)-ish", but I don't see the unifying trick for getting all of them. And then there are the diagonals 1+1+1+1+..., 1+2+3+4+..., 1+3+6+10+..., etc. Euler knew about zeta function regularization and used it to evaluate 1+2+3+4+... as -1/12, and perhaps the trick extends to 1+3+6+10+... etc. That still leaves 1+1+1+1+..., which even Euler steered clear of, but perhaps there's a principled way of absorbing those infinitely many 1's into other sums. Jim Propp

3 3