September 2015 - mathfun@mailman.xmission.com

[math-fun] Draft of September essay
by James Propp 12 Sep '15

12 Sep '15

I'm writing a new Mathematical Enchantments essay titled "The One About .999..." and would love to get your feedback. I plan on publishing it in a week or so. Please leave your feedback here (and include your name in your comments so I'll know whom to acknowledge): https://mathenchant.wordpress.com/?p=142&shareadraft=55f327dde83a0 Or you can post comments to math-fun, or in private email to me, if you prefer. Thanks, Jim Propp P.S. I'm sure I've seen a slicker and easier-to-follow bogus analysis of 1 - 1/2 + 1/3 - 1/4 + ... than the one I give in the End Notes; my high school math teacher Mr. Brenner showed it to me forty years ago, but for some reason I'm unable to reconstruct it. I'm sure it's out there, in print if not on the web. Can anyone provide a lead?

5 8

[math-fun] Cantor set of measure 1?
by James Propp 12 Sep '15

12 Sep '15

Starting from S_0 = [0,1], iteratively define S_n (for n = 1, 2, 3, ...) as the set obtained from S_{n-1} by replacing each of the 2^n closed intervals [a,b] by the two closed intervals [a-1/3^n,(a+b)/2-1/3^n] and [(a+b)/2+1/3^n, b+1/3^n] (that is, we break the interval in half, duplicate the midpoint, shift the left half to the left by 1/3^n, and shift the right half to the right by 1/3^n). It seems to me that at each stage we get 2^n disjoint closed intervals of length 1/2^n separated from one another by 1/3^n, and that every point (including the duplicate points created along the way) moves a finite distance and therefore has a well-defined location "at time infinity". So we seem to get a well-defined set "at time infinity". Am I right? And do we obtain a set of measure 1 that's homeomorphic to the Cantor set? I've seen constructions of "fat Cantor sets" on the web, where one modifies the culling procedure, but I've never seen one that uses sliding and preserves the measure throughout the procedure. So I'm worried that I'm overlooking something. Jim Propp

6 18

[math-fun] Fast image matching
by Warren D Smith 11 Sep '15

11 Sep '15

Given two images, each consisting of N pixels. We want to find the way to rotate, scale, and translate image #1 so it best matches up with image #2. I believe I have invented algorithmic ways to do this in O(NlogN) time. I'm somewhat surprised nobody ever thought of them before. But maybe that is because somebody DID think of them before... QUESTION: did they? (It also might be because I'm wrong... I'll describe my methods later...)

2 1

Re: [math-fun] Fast image matching
by Henry Baker 11 Sep '15

11 Sep '15

This problem is called "image registration". rotation & scaling can be taken care of by the log polar (i.e., complex log) transform: http://www.researchgate.net/profile/Jorge_Dias4/publication/255591825_An_In… At 08:43 AM 9/11/2015, Warren D Smith wrote: >Given two images, each consisting of N pixels. >We want to find the way to rotate, scale, and translate image #1 so it >best matches up with image #2. > >I believe I have invented algorithmic ways to do this in O(NlogN) time. > >I'm somewhat surprised nobody ever thought of them before. >But maybe that is because somebody DID think of them before... >QUESTION: did they? > >(It also might be because I'm wrong... I'll describe my methods later...)

2 1

[math-fun] Kraehenbuehl's harmonization algorithm
by Warren D Smith 11 Sep '15

11 Sep '15

It seems Matt Earnshaw programmed it Listen to his example: https://soundcloud.com/mattearnshaw/kraehenbuehl-harmonies-test His algorithm in a LISP-like language: https://gist.github.com/mattearnshaw/ba3928a256d55341e288 I did not understand this algorithm. Be nice if somebody translated it into something understandable. (Which likely Knuth already did, but I do not have his book.) So I will now try...: Supposedly any N-note single-voice melody -- i.e. time-ordered sequence of N notes -- is converted in this way into any of 2^N + 2^(N-1) harmonized versions (in which each single note is converted into a 4-note chord) "all of which sound pretty good." A "standard major triad" chord is CEG with note-separations (using the 12-tone scale) 4 & 3. To "invert" it (I apologize for the asinine wording used by musicians) you move the lowest note (here C) up one octave (to a higher C), converting the note-separations to 3 & 5. Invert it again by moving lowest note (now E) up one octave to higher E, yielding note-separations 5 & 4. Finally invert it again by moving the lowest note (now G) up 1 octave to higher G, yielding note separations 4 & 3. Thus applying the "inversion" operation 3 times, invert^3, is the same as the frequency-doubling (i.e raising everything 1 octave, i.e. 12 steps) operation (I re-apologize for the asinine nature of musician word usage). In other words, note-separation ordered-pair (X,Y) is converted by inversion to (Y,12-X-Y), then to (12-X-Y,X) then to (X,Y). I suppose perhaps Kraehenbuehl might also allow harmonizing using all "minor triad" chords instead of all "major triads" but in the exact same way. The minor triad is ACE with note-separations 3 & 4. It inverts to 4 & 5, which in turn inverts to 5 & 3, which finally inverts back to 3 & 4. Apparently Kraehenbuehl's algorithm is this. Replace the first note in the melody, by one of the three "inversions" of a major (or we could allow minor?) triad chord, appropriately shifted to contain that note as its highest note. (Hence, if major, then 3 choices: note separations either 4&3, 3&5, or 5&4.) Now, for the subsequent N-1 notes in the melody, do the same, except on all these N-1 occasions only 2 among the 3 invert-versions, of the triad with that note topmost, are permitted -- because Kraehenbuhl demands the invert-versions must differ, i.e. the note-separation-ordered-pair for the Kth chord, cannot equal the note-separation-ordered-pair for the (K-1)th chord. So on each successive non-first note in the melody, there are 2 allowed choices. (You always stay all major or all minor since all chords agree with the first chord about majorness or minorness.) The total number of all-major harmonizations thus produced, is 3*2^(N-1), and each note in the original melody has been converted to a 3-note chord. Now Knuth as a further refinement, wants each note to be converted to a 4-note chord, not merely a 3-note chord (i.e. "4 part harmony"). To accomplish that, he adds 1 more bass note to each chord, which is 12 tones (i.e. 1 octave) below one of the 3 Kraehenbuehl notes we already have. Which one? Well, each of the Kraehenbuehl chords was either an invert^0, invert^1, or invert^2. Keep track of this exponent (modulo 3). The extra bass note is 1 octave below the topmost 3-note-chord note if 0, the middle one if 1, or the lowest one if 2. (Warning: I may have switched "1" and "2" here.) idenity operation (excvpet upo 1 octave).

1 0

[math-fun] Mathics (Mathematica-lite)
by Fred Lunnon 11 Sep '15

11 Sep '15

This project to provide a free lightweight distribution of Mathematica had fallen by the wayside, but an effort is now being made to revive it. The official site at http://www.mathics.org/ does at least respond now, although the online server appears incapable of actually running a program. But the developer maintains an independent online server at http://mathics.angusgriffith.com/ which can cope with running a short program. It does at least handle binomial coefficients correctly, which is better than Wolfram Alpha can manage; it barfed over RWG's latest titbit, but then so does WolfA. WFL

1 0

[math-fun] Bogus proofs using rearrangement of conditionally convergent series
by James Propp 10 Sep '15

10 Sep '15

Can anyone provide a favorite web-reference? For my upcoming Mathematical Enchantments column, I composed a proof that 1 - 1/2 + 1/3 - 1/4 + ... is both positive and zero, but it really doesn't fit into the (already over-long) article, so I'd like to outsource the job of showing "You can get nonsensical results by rearranging conditionally convergent series" to some website that already exists. Jim Propp

7 11

[math-fun] Beware the orange marlin.
by Bill Gosper 09 Sep '15

09 Sep '15

Just a couple of days ago I wrote in a draft "Here are some other K transformations that are immediate specializations of hypergeometric transformations: EllipticK[z]==EllipticK[1/2 - (1/4)*Sqrt[-((z - 2)^2/(z - 1))]]/(1 - z)^(1/4) " Two misfortunes: This isn't quite right, and I lost its faulty derivation to a Mma front-end crash. The rather fishy plot of the error difference, Plot3D[Abs[Subtract @@ % /. z -> u + I*v], {u, 3/4, 9/4}, {v, -1, 1}, AxesLabel -> Automatic, PlotRange -> All] is gosper.org/marlin.png . I don't recall a prior case of two "analytic" functions agreeing everywhere but on a line segment. (In this case all the discrepancies have arg π/4.) --rwg

1 1

[math-fun] OEIS and music
by Warren D Smith 09 Sep '15

09 Sep '15

WDS: My theory of "what music is" is described here in the too-long and too-short versions respectively: https://dl.dropboxusercontent.com/u/3507527/MusicTh.html https://dl.dropboxusercontent.com/u/3507527/MusicThShort.html NJAS: basically all the OEIS algorithm does to sonify a sequence is to reduce the terms mod 88 to a note on the grand piano keyboard. You then get to adjust how the midi file is played, but "read mod 88" is the basic step. This is very primitive and I wish we had something better. The only kind of rating we have for how the "music" sounds is that there is a keyword "hear" that has been added to some sequences that someone has thought are worth listening to. WDS: OK, typing "hear" into the OEIS search box retrieves the following 88 sequences (actually 87, but I added one NJAS mentioned was worth listening to: A261422). This is actually pretty interesting. I still think it would be better if there were a "music-quality rating system" because the present "if a single human likes it, then it qualifies" system is too vulnerable to deranged humans. But the "hear" keyword is not a bad start. A000045 Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. A000005 d(n) (also called tau(n) or sigma_0(n)), the number of divisors of n. A000010 Euler totient function phi(n): count numbers <= n and prime to n. A007318 Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0<=k<=n. A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n). A001223 Differences between consecutive primes. A003415 a(n) = n' = arithmetic derivative of n: a(0) = a(1) = 0, a(prime) = 1, a(mn) = m*a(n) + n*a(m). A000071 Fibonacci numbers - 1. A064413 EKG sequence: a(1) = 1; a(2) = 2; for n > 2, a(n) = smallest number not already used which shares a factor with a(n-1). A005132 Recaman's sequence: a(0) = 0; for n > 0, a(n) = a(n-1) - n if positive and not already in the sequence, otherwise a(n) = a(n-1) + n. A006995 Numbers whose binary expansion is palindromic. A006577 Number of halving and tripling steps to reach 1 in `3x+1' problem. A030101 a(n) is the number produced when n is converted to binary digits, the binary digits are reversed and then converted back into a number. A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n. A001317 Sierpinski's triangle (Pascal's triangle mod 2) converted to decimal. A001611 a(n) = Fibonacci(n) + 1. A056239 If n = product_{k >= 1} (p_k)^(c_k) where p_k is k-th prime and c_k >= 0 then a(n) = sum_{k >= 1} k*c_k. A048883 a(n) = 3^wt(n), where wt(n) = A000120(n). A003602 Kimberling's paraphrases: if n = (2k-1)*2^m then a(n) = k. A025480 a(2n) = n, a(2n+1) = a(n). A166133 After initial 1,2,4, a(n+1) is the smallest divisor of a(n)^2-1 that has not yet appeared in the sequence. A001610 a(n) = a(n-1) + a(n-2) + 1. A089911 Fibonacci(n) mod 12. A108618 A quaternion-generated sequence calculated using the rules given in the comment box with initial seed x = .5'i + .5'j + .5'k + .5e; version: "tes". A115368 Decimal expansion of first zero of the Bessel function J_0(z). A093873 Numerators in Kepler's tree of harmonic fractions. A004718 The Danish composer Per Noergaard's "infinity sequence", invented in an attempt to unify in a perfect way repetition and variation: a(2n) = -a(n), a(2n+1) = a(n) + 1, a(0)=0. A245701 Permutation of natural numbers: a(1) = 1, a(A014580(n)) = 2*a(n), a(A091242(n)) = 2*a(n)+1, where A014580(n) = binary code for n-th irreducible polynomial over GF(2), A091242(n) = binary code for n-th reducible polynomial over GF(2). A001612 a(n) = a(n-1) + a(n-2) - 1. A080099 Triangle T(n,k) = n AND k, 0<=k<=n, bitwise logical AND, read by rows. A129760 Bitwise AND of binary representation of n-1 and n. A240830 a(n)=1 for n <= s+k; thereafter a(n) = Sum(a(n-i-s-a(n-i-1)),i=0..k-1) where s=0, k=7. A249814 Permutation of natural numbers: a(1) = 1, a(n) = A249741(A001511(n), a(A003602(n))). A140263 Permutation of nonnegative integers obtained by interleaving A117967 and A117968. A239690 Base 4 sum of digits of prime(n). A240828 a(1)=a(2)=0, a(3)=2; thereafter a(n) = Sum( a(n-i-s-a(n-i-1)), i=0..k-1 ), where s=0, k=3. A241154 a(n)=1 for n <= s+k; thereafter a(n) = Sum(a(n-i-s-a(n-i-1)),i=0..k-1) where s=0, k=5. A086099 a(n) = OR(k AND (n-k): 0<=k<=n), AND and OR bitwise. A105870 Fibonacci sequence (mod 7). A142149 a(n) = XOR{k OR (n-k): 0<=k<=n}. A142151 a(n) = OR{k XOR (n-k): 0<=k<=n}. A240835 a(n)=1 for n <= s+k; thereafter a(n) = Sum(a(n-i-s-a(n-i-1)),i=0..k-1) where s=0, k=4. A248034 a(n+1) gives the number of occurrences of the last digit of a(n) so far, up to and including a(n), with a(0)=0. A258083 Smallest multiple of 3 not appearing earlier that ends with n. A186994 Number of maximal subsets of {1, 2, ..., n} containing n and having pairwise coprime elements. A227876 Write the decimal digits of n and take successive absolute differences; sequence is the sum of all digits at each level of the pyramid. A249346 The exponent of the highest power of 6 dividing the product of the elements on the n-th row of Pascal's triangle. A051933 Triangle T(n,m) = Nim-sum (or XOR) of n and m, read by rows, 0<=m<=n. A075877 Powering the decimal digits of n (left-associative). A126759 a(0) = 1; a(2n) = a(n); a(3n) = a(n); otherwise write n = 6i+j, where j = 1 or 5 and set a(n) = 2i+2 if j = 1, otherwise a(n) = 2i+3. A243493 Value of Matula-Goebel signature at the fixed points of A069787: a(n) = A127301(A243490(n)). A243658 a(0)=0; thereafter a(n) = noz(n+a(n-1)), where noz(n) = A004719(n). A256229 Powering the decimal digits of n (right-associative). A257213 Least d>0 such that floor(n/d) = floor(n/(d+1)). A258200 First differences of A258024. A125886 a(1) = 1, a(n) = smallest positive number b not among a(1)..a(n-1) such that the last digit of b = the first digit of a(n-1). A131813 a(n+1) = number of preceding terms that are contained in a(n) in binary; a(0)=0. A137655 Working in base 3, a(n+1) = number of preceding terms that are contained in a(n); a(0)=0. A140266 Inverse permutation to A140265. A169669 (first digit of n) * (last digit of n) in decimal representation. A227538 Smallest k such that a partition of n into distinct parts with perimeter k exists. A256489 First differences of A257509: a(n) = A257509(n+1) - A257509(n). A068636 a(n) = Min(n, R(n)), where R(n) (A004086) = digit reversal of n. A068637 a(n) = Max(n, R(n)), where R(n) (A004086) = digit reversal of n. A104325 Number of runs of equal bits in the Dual Zeckendorf (binary) representation of n. A117154 Floretion with FAMP code 1teszapsumseq[C*B] with C = - .5'j + .5'k - .5j' + .5k' - 'ii' - .5'ij' - .5'ik' - .5'ji' - .5'ki' and B = - .5'i + .5'j - .5i' + .5j' - 'kk' - .5'ik' - .5'jk' - .5'ki' - .5'kj'. A119953 Y = X = 'i + .25(ii + jj + kk + e); Z = 'i - i' + .5(jj + kk - jk + kj) + e. See pdf-file for an exact definition (this sequence gives an initial term 1); Version "jes". A123456 Ludwig van Beethoven, Bagatelle No. 25, "Fuer Elise". A126626 A floretion-generated sequence based on the iterative procedure defined in the link given. A144488 Ludwig van Beethoven, Bagatelle No. 25, "Fuer Elise". A240827 a(n) = n for 1<=n<=6; thereafter a(n) = a(n-a(n-3))+a(n-a(n-6)). A242353 Number T(n,k) of two-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows. A248756 a(n) = smallest k such that a(n-k) and n have the same number of 1's in their binary expansions, or a(n) = n if no such k exists. A254868 Recaman [-, +, *]-sequence with seed 6 and step 4. A261684 Array T(n,k) = lunar product n*k (n >= 0, k >= 0) read by antidiagonals. A261422 Number of ordered triples (u,v,w) of palindromes such that u+v+w=n. A073334 The so-called "rhythmic infinity system" of Danish composer Per Noergaard. A117153 The floretion + .25'i + .25'j + .25'k + .25i' + .25j' + .25k' + .25'ii' + .25'jj' + .25'kk' + .25'ij' + .25'ik' + .25'ji' + .25'jk' + .25'ki' + .25'kj' + .25e. A126949 Moduli n for which -1 is a power residue for some power greater than 2: i.e. m^k == -1 mod n for some k>1 and some m>1. A190906 GCD(n! / floor(n/2)!^2, 3^n) A235431 The smallest positive number that must be added to or subtracted from the sum of the first n primes in order to get a prime. A240829 a(1)=-1, a(2)=0, a(3)=1; thereafter a(n) = Sum(a(n-i-s-a(n-i-1)),i=0..k-1) where s=0, k=3. A247074 a(n) = phi(n)/(product_{primes p dividing n } GCD(p - 1, n - 1)). A254873 Recaman [divide, -, +, *]-sequence with seed 14 and step 2. A212952 Decimal expansion of 3*sqrt(3)/16. A215459 Arises in quick gossiping without duplicate transmission. A255253 Complete list of siteswaps (indecomposable ground-state in concatenated decimal notation organized first by sum of digits and then by magnitude). A255877 a(n) = (2n-2)^3 +(2n-2) - 1. Can we draw any conclusions from this list? Almost all even of these especially musical sequences still are pretty horrible as music. The musical ones seem to include a suspiciously large amount of... 1. Most obviously, sequences with a lot of "note propinquity," i.e. most internote-transitions are short-distances. Examples A000005, A000010, A000120, A000120, A005811, A003602, A166133, A115368, A093873, A004718, A235431, ... 2. Fibonacci and its ilk, e.g. A000045, A001610, A001612 3. sequences invented by actual composers e.g. Beethoven and Noergaard: A123456, A144488, A073334,... 4. Recaman sequences. 5. Various 2D tables read by rows. 6. Floretions (whatever they are). My music theory (actually other people's music theories too...) would predict (1) and obviously (3). Also (5) seems plausible. I'm not sure about (4). For (2) it is mysterious to me why those should be good music (if they are). Some of Noergaard's sequences seem particularly interesting and it ought to be possible to define similar recurrences to his, but designed to enjoy additional musical properties...

1 0

[math-fun] animated music, OEIS, theory of music
by Warren D Smith 09 Sep '15

09 Sep '15

My theory of "what music is" is described here in the too-long and too-short versions respectively: https://dl.dropboxusercontent.com/u/3507527/MusicTh.html https://dl.dropboxusercontent.com/u/3507527/MusicThShort.html Re furthering the understanding of that whole question, it might be interesting to know which OEIS sequences sound the best & worst when converted to music. (And I do not know the method you use to convert them to music. Presumably many conversion methods are possible.) If you had a music-quality-rating for each, generated by OEIS users, then eventually we'd know that. (It also is possible some people might like while others dislike some music, e.g. the whole distribution of ratings on an 0-9 scale might be good to keep, not just its mean.)

3 2