November 2018 - mathfun@mailman.xmission.com

[math-fun] Computer Science alternative to "Pi Day" ?
by Henry Baker 06 Nov '18

06 Nov '18

I love Pi; I love 2Pi twice as much! (sqrt(2pi) -- don't ask) However, Pi is too math & physics oriented, and doesn't say anything specifically about computer science. So what would be the single number that most computer science people would recognize and acknowledge as being representative of computer science? Some possibilities, just to warm people up: ln(2) ~ .693 (Computer science people only want logs to base 2!) phi ~ 1.618 (One of Knuth's favorite numbers) gamma (Euler's constant) ~ .57722 (related to digital approx to log function) (should this be digital approx to log2 function?!?) Gibb's constant ~ 1.8519 (Inevitable overshoot for digital/square waves) Sierpinski triangle dimension ~ 1.58496 (Visual representation of why recursive algorithms can be efficient!) Any other suggestions?

10 11

Re: [math-fun] Computer Science alternative to "Pi Day" ?
by Henry Baker 06 Nov '18

06 Nov '18

After a lot of searching for this topic, the most popular number Google could come up with was "404". :-) April 4th is a good candidate. At 05:01 PM 11/5/2018, Henry Baker wrote: >I love the concept of a date conversion fault! A computer scientist spends far more time dealing with faults than with actual data.

1 0

Re: [math-fun] Computer Science alternative to "Pi Day" ?
by Henry Baker 06 Nov '18

06 Nov '18

Oops! Andrew Trevorrow <andrew(a)trevorrow.com> got 0xdeadbeef first! At 05:01 PM 11/5/2018, Henry Baker wrote: >A digital salute for this entry! > >I love the concept of a date conversion fault! A computer scientist spends far more time dealing with faults than with actual data. > >Perhaps some hex number -- e.g., 0xdeadbeef (often used to find stuff in hex dumps) > >0xdeadbeef = -559,038,737 >----------- >The problem with something like the least positive IEEE float is that it won't last very long (we hope). > >At 03:23 PM 11/5/2018, Kerry Mitchell wrote: >>On Mon, Nov 5, 2018 at 4:20 PM Brent Meeker <meekerdb(a)verizon.net> wrote: >>> I memorized 2.302581 early on, ln(10), to convert to base e. >>> >>> Brent >> >>This is a natural choice. Following Pi Day tradition, ln(10) ~ 2.30 can be >>memorialized annually on February 30. :-) >> >>Kerry

1 0

Re: [math-fun] Computer Science alternative to "Pi Day" ?
by Henry Baker 06 Nov '18

06 Nov '18

A digital salute for this entry! I love the concept of a date conversion fault! A computer scientist spends far more time dealing with faults than with actual data. Perhaps some hex number -- e.g., 0xdeadbeef (often used to find stuff in hex dumps) 0xdeadbeef = -559,038,737 ----------- The problem with something like the least positive IEEE float is that it won't last very long (we hope). At 03:23 PM 11/5/2018, Kerry Mitchell wrote: >On Mon, Nov 5, 2018 at 4:20 PM Brent Meeker <meekerdb(a)verizon.net> wrote: >> I memorized 2.302581 early on, ln(10), to convert to base e. >> >> Brent > >This is a natural choice. Following Pi Day tradition, ln(10) ~ 2.30 can be >memorialized annually on February 30. :-) > >Kerry

1 0

[math-fun] calculus question from watching veteran's day movies
by Henry Baker 05 Nov '18

05 Nov '18

I was watching an old WWII movie, which showed the rifled insides of a cannon barrel. A similar view (of a smaller gun) is found at the beginning of one (or more!) of the James Bond movies. This rifling all seems to be of a *fixed* pitch -- i.e., a helix of constant twist angle. But if you think about it, a bullet starts at velocity zero and angular momentum zero, so *ideally*, this rifling should start out relatively shallow, with slightly more twist angle as the bullet travels further down the barrel. On the other hand, the bullet is also travelling *faster* at the end of the barrel, than at the breech of the barrel, so the twist could actually be less at the end, since it may already have achieved the correct angular momentum. So what's the ideal rifling -- by "ideal" here I will choose that rifling that maximizes the energy transferred to the bullet, while still achieving a given angular momentum ? We have to transfer a certain amount of energy from linear motion to rotating motion, and I presume that there is a certain cost associated with this transfer. Obviously, the ratio of the moment of inertia to the mass of the bullet should enter into the calculation at some point. In order to maximize the power transfer, there needs to be a kind of *impedance match* of the bullet to the rifling pitch. https://en.wikipedia.org/wiki/Rifling "In some cases, rifling will have twist rates that increase down the length of the barrel, called a *gain twist* or *progressive twist*".

2 4

Re: [math-fun] Finding a polynomial from an integer sequence
by Steve Witham 05 Nov '18

05 Nov '18

I really liked Keith Lynch's set of related problems: > Subject: > [math-fun] Finding a polynomial from an integer sequence > From: > "Keith F. Lynch" <kfl(a)KeithLynch.net> > Date: > 10/27/18, 3:56 PM > > To: > math-fun(a)mailman.xmission.com > > > I was wondering how many strings there are of length n, with no > instances of 4 consecutive identical letters, in a b-letter alphabet. If you generalize to prohibiting *r* consecutive identical letters, this can be calculated in O(n * r) time, i.e. quickly. Here's the pattern of the algorithm I used: For n = 1, r = 4, there are b strings like "c". For n = 2, r = 4, there are b * (b - 1) strings like cd. # (b - 1) ways to pick a different letter. b * 1 strings like cc # one way to pick the same letter. total: b^2 For n = 3, r = 4, b^2 * (b - 1) strings like cde or cce -- e not repeated (b * (b - 1)) * 1 strings like cdd -- d repeated twice b * 1 * 1 strings like ccc -- c repeated three times total: b^3 For n = 4, r = 4, there's a possibility of a repeat-of-four so we get b^3 * (b - 1) strings like cdef, ccdf, cddf, or cccf (b^2 * (b - 1)) * 1 strings like cdeeor ccee (b * (b - 1)) * 1 * 1 strings like cddd zero strings like cccc -- that's not allowed. total: b^4 - b "And so forth" up to strings of length n. For each level you need to remember: [how many end in (just one copy of) a new digit, how many end in two copies of the same digit, how many end in three copies of the same digit] I confirmed your results for the total numbers of allowed strings. I confirmed your sequences of numbers keeping n and r constant and varying b. I confirmed the polynomials you got from those sequences. > So, can anyone think of a better way to come up with polynomials from > those sequences, or from sequences in general? Thanks. My favorite way to remember how to fit a polynomial to a sequence of N numbers (or any set of N (x, y) points without repeats of x) is this: 0) If there's only one point, the polynomial is a constant. Else, 1) Fit polynomial L(x) to points 1 .. N-1 2) Fit polynomial R(x) to points 2 .. N 3) Linearly interpolate between L and R: P(x) = ((N - x) * L(x) + (x - 1) * R(x)) / N The rationale is that L and R each cover one end point, and they both go through all the points in between. So interpolating between them (correctly) gives a curve that hits all the points. The algorithm is a nasty recursive O(2^N) if you don't optimize by saving some results, but O(N^3) if you do. > Another issue is that there's no guarantee that the polynomial is even > correct. All I really know is that it will reproduce the terms I > counted. Of course the more identical differences I get, the more > confident I am. For instance for b=9, I counted the first 25 terms, > so I actually got 16 copies of 362880. Yes. What I did is calculate the polynomial with n + 1 numbers in the sequence, then with 2n + 2 numbers, and checked that it was the same polynomial. It always was. > neither of them constitutes a proof that the polynomial is correct. Or that*any* polynomial is correct-- who says that, except for the first few values of n where it's obvious, the sequence is a polynomial series at all? I looked at my algorithm and asked, "Is there a reason to expect that's a polynomial in b?" Hmm, b is always just a number that goes into the calculations, but it never changes the pattern of the calculations. No loop ranges or IF statements depend on b. Also, there's nothing but multiplying and adding going on. So, instead of b being a specific number, can I set up an analogous process where all the intermediate values and results are replaced by polynomials (as they are in the examples I work through above)? I was calculating with a Python function, n_strings(n, r, b). Looking at that code, how would I calculate the polynomial in b for a given n and r? Hm, well, I also had a Python class for polynomials. So I set b = a polynomial object, B(b) = 1 * b + 0. Then I plugged that B into my Python function. And it returns the correct polynomial for the answer! The first time I tried it! With no change to the function itself! It's always a kick when code you wrote, instead of digging in its heels resisting change, is out in front anticipating where you're going next. Here are some results of n_strings(n, 4, B) for various n. The polynomial coefficients are shown in the opposite of the usual order, from b^0 through b^n): n = 1 : UniPoly([0, 1]) , order 1 n = 2 : UniPoly([0, 0, 1]) , order 2 n = 3 : UniPoly([0, 0, 0, 1]) , order 3 n = 4 : UniPoly([0, -1, 0, 0, 1]) , order 4 (These up to here duplicate the examples I worked through above.) n = 5 : UniPoly([0, 1, -2, 0, 0, 1]) , order 5 n = 6 : UniPoly([0, 0, 2, -3, 0, 0, 1]) , order 6 n = 7 : UniPoly([0, 0, 0, 3, -4, 0, 0, 1]) , order 7 n = 8 : UniPoly([0, -1, 1, 0, 4, -5, 0, 0, 1]) , order 8 n = 9 : UniPoly([0, 1, -4, 3, 0, 5, -6, 0, 0, 1]) , order 9 n = 10 : UniPoly([0, 0, 3, -9, 6, 0, 6, -7, 0, 0, 1]) , order 10 n = 11 : UniPoly([0, 0, 0, 6, -16, 10, 0, 7, -8, 0, 0, 1]) , order 11 ... Related to n_strings() is a function n_strings_segregated() that returns the r - 1 results for whether the last letter is repeated 1, 2 ... r - 1 times. That also returns polynomials if b is a polynomial. Their sum is the polynomial for the total number of strings, but it might be interesting to look at the patterns of their coefficients, for instance: n_strings(6, 4, B): UniPoly([0, -1, 3, -2, 0, -1, 1]) UniPoly([0, 1, -1, 0, -1, 1]) UniPoly([0, 0, 0, -1, 1]) total: UniPoly([0, 0, 2, -3, 0, 0, 1]) n_strings(16, 4, B): UniPoly([0, 0, 0, -10, 50, -90, 70, -48, 92, -100, 36, -11, 23, -12, 0, -1, 1]) UniPoly([0, 0, -4, 22, -42, 34, -31, 70, -77, 28, -10, 21, -11, 0, -1, 1]) UniPoly([0, -1, 7, -15, 13, -19, 51, -57, 21, -9, 19, -10, 0, -1, 1]) total: UniPoly([0, -1, 3, -3, 21, -75, 90, -35, 36, -81, 45, 0, 12, -13, 0, 0, 1]) --Steve

1 0

Re: [math-fun] Finding a polynomial from an integer sequence
by Keith F. Lynch 04 Nov '18

04 Nov '18

Thanks to everyone who responded to my query, especially Tomas Rokicki, who described a matrix method for the specific problem I was interested in, and Rich Schroeppel, who described a way that will work for any sequence, including one with terms missing. Of course any finite subsequence of an infinite sequence will match an unlimited number of polynomials, and there doesn't seem to be any way of telling which, if any, is correct. If the order of a polynomial is much less than the number of terms, that's evidence, but not proof, that that polynomial is correct. I'm tempted to test every sequence in OEIS to see if it appears to be polynomial, and if not, to see if it can be made polynomial by altering, removing, or interpolating one element. If it can be, it might be that I've found an error in the sequence, or at least an oddity that could do with some exploration. Has anyone done this already? Thanks.

2 1

[math-fun] p1100-MWSS-gun.lua
by Bill Gosper 01 Nov '18

01 Nov '18

I urge anyone who has not tried this to randomly delete one of the 1142 gliders and watch things shut completely down. Nice exercise: Use Golly to determine that 1142 glider count. (Ask for hints!) —Bill Perhaps in the info the .lua could encourage these experiments. It might also mention that this was only the 3rd(?) "glider" gun, following a 10(?) yr drought. (The technology supports periods 900+200n, but n=0 gives a dull multiple of 30.) And I would like to hear about the CAD technology, which seems dramatically more concise than my ZetaLisp CAD system.

1 1

Re: [math-fun] Matrix roots of polynomials
by Dan Asimov 01 Nov '18

01 Nov '18

Oh, well. I knew there was some reason I didn't become an algebraist. (I wanted to look at one-sided polynomials because I thought they might be easier to deal with than general polynomials. The same problem — non-commutativity — seems to be what prevents there being a good theory of analytic functions with quaternion or octonion coefficients.) —Dan Andy Latto wrote: ----- I think this doesn't work because of non-commutativity. You can't factor X^2 + 2DX + D^2 as (X + D)^2 ( a necessary step in deriving the quadratic formula), because the latter expands to X^2 + DX + XD + D^2, which is different. Which raised the question of why the polynomials with the coefficients before the variables are the interesting ones. Shouldn't you be looking at the more general quadratic X^2 + AX + XB + C = 0? I wrote: > It occurs to me that as long as the matrices are over a ring M > (assumed to have a multiplicative identity) in which the following > hold: > > ----- > a) 2 has a multiplicative inverse ...* > > —and— > > b) every element of Ring has a square root in Ring ... > ----- > > ... then a quadratic equation of form > > X^2 + b X + c > > for b, c in Ring and the unknown X to be found within Ring as well ... > > ... has a solution (OK, two) given by the usual formula: > > ----- > X = -b/2 ± √((b/2)^2 - c). -----

2 1

Re: [math-fun] Matrix roots of polynomials
by Dan Asimov 01 Nov '18

01 Nov '18

Thanks for the paper suggestions, Victor! It occurs to me that as long as the matrices are over a ring M (assumed to have a multiplicative identity) in which the following hold: ----- a) 2 has a multiplicative inverse ...* —and— b) every element of Ring has a square root in Ring ... ----- ... then a quadratic equation of form X^2 + b X + c for b, c in Ring and the unknown X to be found within Ring as well ... ... has a solution (OK, two) given by the usual formula: ----- X = -b/2 ± √((b/2)^2 - c). ----- I'm guessing the cubic and quartic formulae for C work, too, for rings, that have some additional restrictions regarding characteristic, at least. (Cubics should definitely *not* be characteristic = 3 or we may have trouble dividing by 27.) But commutativity may be a problem for degrees 3 and 4. —Dan ————— * Here 2 denotes 1 + 1, in case you were wondering. I wrote: ----- ... Consider a collection M of matrices over a ring, like M = M(n, Z) or M = M(n, Q) or M = M(n, R) or M = M(n, C), meaning the ring of n x n square matrices over the integers, the rationals, the reals, or the complexes. For any one of these, call it M and consider polynomials of form P(X) = X^k + A_(k-1) X^(k-1) + ... + A_1 X + A_0 where the A_j belong to the matrix ring M. Then what is known a) about the existence of solutions X in M to the equation P(X) = 0 (where 0 denotes the 0 matrix in M) ??? b) about closed formulas for the roots of P(X) in M ??? (like the quadratic, cubic, and quartic formulae). Of course, there can't be any general quintic formula* for matrices, since that would contradict Abel's theorem on its unsolvability over C. -----

6 5