- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Fwd: Thue-Morse and cubefree first seq
by Bill Gosper 19 Jan '17

19 Jan '17

Rapid prototyping: In[396]:= StringReplace[ "AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB AB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB B", " " | " " -> ""] Out[396]= "AABAABABAABAABBAABAABABAABAABBAABAABABAABABBAABAABABAABAABBAABAABABAABAABBAABAABABAABBAABAABABAABAABBAABAABABAABAABBAABAABABBAABAABABAABAABBAABAABABAABAABBAABAABABAABB" cubeFree[s_String] := !StringMatchQ[s, ___ ~~ a__ ~~ a__ ~~ a__ ~~ ___] In[410]:= cubeFree@%396 // Timing Out[410]= {0.001793, True} In[411]:= cubeFree[%396 ~~ "AABAABABAABB" ~~ "AABAABABAABB"] // Timing Out[411]= {0.000096, False} --rwg Date: 2017-01-18 18:26 From: "David Wilson" <davidwwilson(a)comcast.net> To: "'math-fun'" <math-fun(a)mailman.xmission.com> Reply-To: math-fun <math-fun(a)mailman.xmission.com> Using a C++ program, I was able to generate 10001 (a(0..10000)) initial values of this sequence in well under a second. The first few elements agree with Alan Wechsler's values in an earlier post. I used a recursive algorithm that performs a "cube test" on each newly added element, and backtracks if that element introduces a cube. I assume this is the straightforward recursive approach. Backtracking appears sparse, so I suspect that the number of confirmed elements is essentially linear in the number of cube tests. Whereas the cube test for a(n) is O(n^2), I'm guessing the entire algorithm is circa O(n^3). Assuming my algorithm correct, I am fairly confident of the correctness of the 10001 elements. I independently generated 10200 elements, and the first 10001 agreed, so I don't believe backtracking will trash any of the final elements. I can send a b-file of a(0..10000) to any party interested confirming cubefreeness of the sequence and/or creating an OEIS sequence. Unfortunately, my program croaks on 100000 elements. The elements allocate fine, so I suspect I suspect that the O(n) recursion depth is blowing the stack. I think I could convert the algorithm to an iterative algorithm using O(1) stack, but I'm not all that motivated. Over the first 10000 elements, the density of 1's seems dances around a point on the high side of [0.4079, 0.4080]. > -----Original Message----- > From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On > Behalf Of Jeffrey Shallit > Sent: Wednesday, January 18, 2017 10:26 AM > To: James Propp; jean-paul allouche; Eric.Angelini(a)kntv.be; gef(a)iap.fr; > Nicolas.Graner(a)u-psud.fr; math-fun > Subject: Re: [math-fun] Fwd: Thue-Morse and cubefree firs seq > > The status of the lexicographically least cubefree sequence v over {0,1} > is the same as the status of the lexicographically least squarefree > sequence over {0,1,2}: namely, although it is possible to write down > with certainty the first few terms of this sequence, almost nothing is > known about it, for example: > - does every finite cubefree word eventually appear in v? > - do the letters 0 and 1 (and more generally any subword) have a > limiting frequency in v, and if so, what is it? > - is the word v generated by a finite automaton (in the way Thue- > Morse > is), or as the iteration of a morphism or image of such a word (in the > way Thue-Morse is)? > > James Currie, in a series of papers with Shelton ("fixing blocks") > developed a method to test, given a squarefree prefix p, whether p > infinitely extendable to the right while maintaining the squarefree > property. His method gives, in principle, a bound B on how many bits > you need to extend such a prefix p before you know it is infinitely > extendable, but I am not sure anyone has explicitly estimated how big B > is in terms of |p|. Currie once told me it is o(|p|). This method > should, in principle, apply to cubefree words, also. > > In contrast, the situation for overlap-free words is much better. > The lexicographically least overlap-free word over {0,1} is known, and > it is 001001 t', where t' is obtained from the Thue-Morse word t by > interchanging 0 and 1. This was proved in this paper: > > http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r27 > > > > On 1/18/17 10:14 AM, James Propp wrote: > > I seem to recall that this question is addressed in one of articles Jeff > > sent me last week, but I don't remember which. > > > > Thanks, > > > > Jim > > ---------- Forwarded message ---------- > > From: *Eric Angelini* <Eric.Angelini(a)kntv.be > <mailto:Eric.Angelini@kntv.be>> > > Date: Wed, Jan 18, 2017 at 8:30 AM > > Subject: [math-fun] Thue-Morse and cubefree firs seq > > To: math-fun <math-fun(a)mailman.xmission.com > > <mailto:math-fun@mailman.xmission.com>> > > Cc: Gilles Esposito-Farese <gef(a)iap.fr <mailto:gef@iap.fr>>, Nicolas > > Graner <Nicolas.Graner(a)u-psud.fr <mailto:Nicolas.Graner@u-psud.fr>> > > > > > > Hello Math-Fun, [copy to Gilles and Nicolas] > > > > The late post about Thue-Morse raises (perhaps) this question: > > - what is the lexicographically first binary cubefree seq? > > Certainly not the Thue-Morse sequence [which starts with > > 0110 -- as this could be bettered by the start 00100101]. > > I find nothing about this putative seq I'm looking for in > > the OEIS, but I might be shortsighted or wrong (wrong in > > the sense that this lexicographically first seq is perhaps > > impossible to build). > > My friend Gilles Esposito-Farèse, for instance, has built > > a 3000-term seq which is cubefree (checked by computer) -- > > but is it the first one? And will the cubefree constraint > > hold in the seq he found if the said seq is extended, say, > > to 1 million terms? Could the million-and-one term affect > > the 1234-th one (for example), via a kind of backtracking? > > Best, > > É. > >

1 0

[math-fun] Cubefree Thue-Morse like
by Eric Angelini 19 Jan '17

19 Jan '17

On behalf of Gilles Best, É. On January 18th 2017 at 14:30, <Eric.Angelini(a)kntv.be<mailto:Eric.Angelini@kntv.be>> wrote: - what is the lexicographically first binary cubefree seq? Dear cube-free sequence fans (I am impressed to see some great names in the list!) Many thanks for your already deep answers. The construction of the first elements of the sequence is indeed straightforward, and one finds: AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB AB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB B AAB AAB AB AAB AAB B AAB AAB AB AAB AAB B AAB AAB AB AAB B ... (where I used A and B instead of your 0 and 1). A kind of chaotic pattern appears, and one may thus define a more compact notation: 1 = AAB AAB AB AAB AAB B 2 = AAB AAB AB AAB AB B 3 = AAB AAB AB AAB B 4 = AAB AAB AB B 5 = AAB AB AAB AAB B 6 = AB AAB AAB B 7 = AB AAB B which allows me to give you now more than 15000 terms : 112 113 114 113 114 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 113 12 113 114 113 114<tel:12%20113%20114%20113%20114> 115 116 115 116 115<tel:115%20116%20115%20116%20115> 117 114 113 114 113 114<tel:114%20113%20114%20113%20114> 115 116 115 ... There again appears a clear structure, but it is obviously non periodic (cube-free), and the property of being the lexicographically first sequence seems to generate more chaos than for Prouhet-Thue-Morse. It can be shown that these first terms are correct, i.e., that they will never be modified by some subsequent term inducing a very long cube. [My naive way of proving so was to note that the substring BBAABB never appears, therefore that one may glue the infinite Prouhet-Thue-Morse sequence (starting from its 22nd term, i.e., precisely BBAABB) at a point, and this proves that the backtracking cannot spoil what we already computed.] Can Esposito-Farèse report the maximum amount of backtracking that he needed Well, I needed to program a specific routine to answer this question, as my method of construction did not work letter by letter (to increase its speed, and I therefore needed to backtrack more sometimes). When I work letter by letter, it seems that the backtracking never exceeds 3. It simply happens when one tries to add an extra A at the end of a string of the form ...ABB, and that this generates a cube (sometimes very long!). One should then a priori try to add a B instead, but ...ABBB is also forbidden. Therefore one has to go back to the previous ...A and replace it by ...B. [I checked that only on the first thousand of terms, and not on the full result above.] Many questions may be asked. One of the most immediate would be: Can it be proven that this sequence will never become equivalent to another known cube-free sequence (Prouhet-Thue-Morse, Kolakoski, Stewart's choral, ...) after a given term? A probably more difficult question: Does this sequence have any mathematical interest? (besides the fact that it also gives the lexicographically last cube-free sequence by replacing A <--> B ;-) Looking forward to your insights; sincerely, G.E-F à+ É. Catapulté de mon aPhone

1 0

[math-fun] Analytic geometry question
by David Wilson 19 Jan '17

19 Jan '17

Is there a planar figure describable whose boundary is a polynomial in x and y, and whose area is 6/pi^2?

2 1

Re: [math-fun] Fwd: Thue-Morse and cubefree first seq
by David Wilson 18 Jan '17

18 Jan '17

Using a C++ program, I was able to generate 10001 (a(0..10000)) initial values of this sequence in well under a second. The first few elements agree with Alan Wechsler's values in an earlier post. I used a recursive algorithm that performs a "cube test" on each newly added element, and backtracks if that element introduces a cube. I assume this is the straightforward recursive approach. Backtracking appears sparse, so I suspect that the number of confirmed elements is essentially linear in the number of cube tests. Whereas the cube test for a(n) is O(n^2), I'm guessing the entire algorithm is circa O(n^3). Assuming my algorithm correct, I am fairly confident of the correctness of the 10001 elements. I independently generated 10200 elements, and the first 10001 agreed, so I don't believe backtracking will trash any of the final elements. I can send a b-file of a(0..10000) to any party interested confirming cubefreeness of the sequence and/or creating an OEIS sequence. Unfortunately, my program croaks on 100000 elements. The elements allocate fine, so I suspect I suspect that the O(n) recursion depth is blowing the stack. I think I could convert the algorithm to an iterative algorithm using O(1) stack, but I'm not all that motivated. Over the first 10000 elements, the density of 1's seems dances around a point on the high side of [0.4079, 0.4080]. > -----Original Message----- > From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On > Behalf Of Jeffrey Shallit > Sent: Wednesday, January 18, 2017 10:26 AM > To: James Propp; jean-paul allouche; Eric.Angelini(a)kntv.be; gef(a)iap.fr; > Nicolas.Graner(a)u-psud.fr; math-fun > Subject: Re: [math-fun] Fwd: Thue-Morse and cubefree firs seq > > The status of the lexicographically least cubefree sequence v over {0,1} > is the same as the status of the lexicographically least squarefree > sequence over {0,1,2}: namely, although it is possible to write down > with certainty the first few terms of this sequence, almost nothing is > known about it, for example: > - does every finite cubefree word eventually appear in v? > - do the letters 0 and 1 (and more generally any subword) have a > limiting frequency in v, and if so, what is it? > - is the word v generated by a finite automaton (in the way Thue- > Morse > is), or as the iteration of a morphism or image of such a word (in the > way Thue-Morse is)? > > James Currie, in a series of papers with Shelton ("fixing blocks") > developed a method to test, given a squarefree prefix p, whether p > infinitely extendable to the right while maintaining the squarefree > property. His method gives, in principle, a bound B on how many bits > you need to extend such a prefix p before you know it is infinitely > extendable, but I am not sure anyone has explicitly estimated how big B > is in terms of |p|. Currie once told me it is o(|p|). This method > should, in principle, apply to cubefree words, also. > > In contrast, the situation for overlap-free words is much better. > The lexicographically least overlap-free word over {0,1} is known, and > it is 001001 t', where t' is obtained from the Thue-Morse word t by > interchanging 0 and 1. This was proved in this paper: > > http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r27 > > > > On 1/18/17 10:14 AM, James Propp wrote: > > I seem to recall that this question is addressed in one of articles Jeff > > sent me last week, but I don't remember which. > > > > Thanks, > > > > Jim > > ---------- Forwarded message ---------- > > From: *Eric Angelini* <Eric.Angelini(a)kntv.be > <mailto:Eric.Angelini@kntv.be>> > > Date: Wed, Jan 18, 2017 at 8:30 AM > > Subject: [math-fun] Thue-Morse and cubefree firs seq > > To: math-fun <math-fun(a)mailman.xmission.com > > <mailto:math-fun@mailman.xmission.com>> > > Cc: Gilles Esposito-Farese <gef(a)iap.fr <mailto:gef@iap.fr>>, Nicolas > > Graner <Nicolas.Graner(a)u-psud.fr <mailto:Nicolas.Graner@u-psud.fr>> > > > > > > Hello Math-Fun, [copy to Gilles and Nicolas] > > > > The late post about Thue-Morse raises (perhaps) this question: > > - what is the lexicographically first binary cubefree seq? > > Certainly not the Thue-Morse sequence [which starts with > > 0110 -- as this could be bettered by the start 00100101]. > > I find nothing about this putative seq I'm looking for in > > the OEIS, but I might be shortsighted or wrong (wrong in > > the sense that this lexicographically first seq is perhaps > > impossible to build). > > My friend Gilles Esposito-Farèse, for instance, has built > > a 3000-term seq which is cubefree (checked by computer) -- > > but is it the first one? And will the cubefree constraint > > hold in the seq he found if the said seq is extended, say, > > to 1 million terms? Could the million-and-one term affect > > the 1234-th one (for example), via a kind of backtracking? > > Best, > > É. > > > > > > _______________________________________________ > > math-fun mailing list > > math-fun(a)mailman.xmission.com <mailto:math- > fun(a)mailman.xmission.com> > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > <https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun> > > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

Re: [math-fun] Fwd: Thue-Morse and cubefree firs seq
by Jeffrey Shallit 18 Jan '17

18 Jan '17

The status of the lexicographically least cubefree sequence v over {0,1} is the same as the status of the lexicographically least squarefree sequence over {0,1,2}: namely, although it is possible to write down with certainty the first few terms of this sequence, almost nothing is known about it, for example: - does every finite cubefree word eventually appear in v? - do the letters 0 and 1 (and more generally any subword) have a limiting frequency in v, and if so, what is it? - is the word v generated by a finite automaton (in the way Thue-Morse is), or as the iteration of a morphism or image of such a word (in the way Thue-Morse is)? James Currie, in a series of papers with Shelton ("fixing blocks") developed a method to test, given a squarefree prefix p, whether p infinitely extendable to the right while maintaining the squarefree property. His method gives, in principle, a bound B on how many bits you need to extend such a prefix p before you know it is infinitely extendable, but I am not sure anyone has explicitly estimated how big B is in terms of |p|. Currie once told me it is o(|p|). This method should, in principle, apply to cubefree words, also. In contrast, the situation for overlap-free words is much better. The lexicographically least overlap-free word over {0,1} is known, and it is 001001 t', where t' is obtained from the Thue-Morse word t by interchanging 0 and 1. This was proved in this paper: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v5i1r27 On 1/18/17 10:14 AM, James Propp wrote: > I seem to recall that this question is addressed in one of articles Jeff > sent me last week, but I don't remember which. > > Thanks, > > Jim > ---------- Forwarded message ---------- > From: *Eric Angelini* <Eric.Angelini(a)kntv.be <mailto:Eric.Angelini@kntv.be>> > Date: Wed, Jan 18, 2017 at 8:30 AM > Subject: [math-fun] Thue-Morse and cubefree firs seq > To: math-fun <math-fun(a)mailman.xmission.com > <mailto:math-fun@mailman.xmission.com>> > Cc: Gilles Esposito-Farese <gef(a)iap.fr <mailto:gef@iap.fr>>, Nicolas > Graner <Nicolas.Graner(a)u-psud.fr <mailto:Nicolas.Graner@u-psud.fr>> > > > Hello Math-Fun, [copy to Gilles and Nicolas] > > The late post about Thue-Morse raises (perhaps) this question: > - what is the lexicographically first binary cubefree seq? > Certainly not the Thue-Morse sequence [which starts with > 0110 -- as this could be bettered by the start 00100101]. > I find nothing about this putative seq I'm looking for in > the OEIS, but I might be shortsighted or wrong (wrong in > the sense that this lexicographically first seq is perhaps > impossible to build). > My friend Gilles Esposito-Farèse, for instance, has built > a 3000-term seq which is cubefree (checked by computer) -- > but is it the first one? And will the cubefree constraint > hold in the seq he found if the said seq is extended, say, > to 1 million terms? Could the million-and-one term affect > the 1234-th one (for example), via a kind of backtracking? > Best, > É. > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com <mailto:math-fun@mailman.xmission.com> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > <https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun> >

3 2

[math-fun] "Share the Squares" dissection puzzle?
by James Propp 18 Jan '17

18 Jan '17

Has anyone devised a fun puzzle in which a 1-by-1, 4-by-4, 6-by-6, and 7-by-7 square are divided into smaller polyominoes which can then be reassembled to form a 2-by-2, 3-by-3, 5-by-5, and 8-by-8 square? (The title of the thread is a variation on Matt Parker's "Share the Power" puzzle, which is a generalization of this to higher powers, but without the embodiment via polyominoes.) My guess is that the best puzzle of this kind (i.e., the most challenging to solve) would be one that used a near-minimal number of pieces. I'm also seeking a polyomino implementation of the identity 0^2+3^2+5^2+6^2 = 1^2+2^2+4^2+7^2, though of course one of the squares has vanished! Jim Propp

10 14

[math-fun] Thue-Morse and cubefree firs seq
by Eric Angelini 18 Jan '17

18 Jan '17

Hello Math-Fun, [copy to Gilles and Nicolas] The late post about Thue-Morse raises (perhaps) this question: - what is the lexicographically first binary cubefree seq? Certainly not the Thue-Morse sequence [which starts with 0110 -- as this could be bettered by the start 00100101]. I find nothing about this putative seq I'm looking for in the OEIS, but I might be shortsighted or wrong (wrong in the sense that this lexicographically first seq is perhaps impossible to build). My friend Gilles Esposito-Farèse, for instance, has built a 3000-term seq which is cubefree (checked by computer) -- but is it the first one? And will the cubefree constraint hold in the seq he found if the said seq is extended, say, to 1 million terms? Could the million-and-one term affect the 1234-th one (for example), via a kind of backtracking? Best, É.

3 4

[math-fun] Christian Boyer?
by Keith F. Lynch 18 Jan '17

18 Jan '17

Does anyone have contact information for Christian Boyer? He used to post here regularly, but not since last September. He's not responding to email sent to cboyer(a)club-internet.fr. Does anyone here know if he's okay? Thanks.

2 1

[math-fun] booltools
by Bill Gosper 17 Jan '17

17 Jan '17

Rohan requested all 7581 monotonic pentadic boolean functions. Instead of reading up on the smart way to do this (Vol IV?), I built a little sandbox, iteratively Outer Anding and Outer Oring the initial pool {0,p,q,r,s,t,1} with itself. Interestingly, if one Outerand is always {0,p,q,r,s,t,1}, this only finds 7580. The missing one is easy to guess. For brevity, we illustrate with the triadics: In[384]:= three = alg2bool /@ {0, p, q, r, 1} Out[384]= {(#1[[1]]; False) &, #1[[1]] &, #1[[2]] &, #1[[3]] &, (#1[[1]]; True) &} (For philosophical reasons, the constants True and False are monadic (vs nulladic.) What is the truth table of a constant?) ttab is truth table: In[385]:= ttab /@ three During evaluation of In[385]:= Transpose::nmtx: The first two levels of {} cannot be transposed. (A harmless glitch.) Out[385]= {{False}, {False, True}, {False, True, False, True}, {False, True, False, True, False, True, False, True}, {True}} In[386]:= three; cull is just delete duplicates by truth table. tim prints time and length. In[387]:= cull[Union[% // tim, cull[Outer[Distribute[And[#1, #2], Function] &, three, %] // Flatten // tim] // tim, cull[Outer[Distribute[Or[#1, #2], Function] &, three, %] // Flatten // tim] // tim]] // tim During evaluation of In[387]:= 6.*10^-6,5 (6 μs, 5 fcns) During evaluation of In[387]:= 0.000064,25 During evaluation of In[387]:= 0.015481,8 During evaluation of In[387]:= 0.000063,25 During evaluation of In[387]:= 0.002756,8 During evaluation of In[387]:= 0.020625,11 (Redundantly culling smaller pieces saves time.) Out[387]= {(#1[[1]]; False) && (#1[[1]]; False) &, (#1[[1]]; True) && (#1[[1]]; True) &, #1[[1]] && #1[[1]] &, #1[[1]] && #1[[ 2]] &, #1[[1]] && #1[[3]] &, #1[[2]] && #1[[2]] &, #1[[2]] && #1[[ 3]] &, #1[[3]] && #1[[3]] &, #1[[1]] || #1[[2]] &, #1[[1]] || #1[[ 3]] &, #1[[2]] || #1[[3]] &} This brought us up to 11 functions. Rub these against the original 5: In[388]:= cull[Union[% // tim, cull[Outer[Distribute[And[#1, #2], Function] &, three, %] // Flatten // tim] // tim, cull[Outer[Distribute[Or[#1, #2], Function] &, three, %] // Flatten // tim] // tim]] // tim During evaluation of In[388]:= 0.000013,11 During evaluation of In[388]:= 0.000124,55 During evaluation of In[388]:= 0.031731,15 During evaluation of In[388]:= 0.00013,55 During evaluation of In[388]:= 0.007292,15 During evaluation of In[388]:= 0.044341,19 Out[388]= {(#1[[1]]; False) && ((#1[[1]]; False) && (#1[[1]]; False)) &, (#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)) &, (#1[[1]]; True) && (#1[[1]] || #1[[2]]) &, (#1[[1]]; True) && (#1[[1]] || #1[[3]]) &, (#1[[1]]; True) && (#1[[2]] || #1[[3]]) &, #1[[ 1]] && ((#1[[1]]; True) && (#1[[1]]; True)) &, #1[[ 1]] && (#1[[1]] && #1[[2]]) &, #1[[ 1]] && (#1[[1]] && #1[[3]]) &, #1[[ 1]] && (#1[[2]] && #1[[3]]) &, #1[[ 1]] && (#1[[2]] || #1[[3]]) &, #1[[ 2]] && ((#1[[1]]; True) && (#1[[1]]; True)) &, #1[[ 2]] && (#1[[2]] && #1[[3]]) &, #1[[ 2]] && (#1[[1]] || #1[[3]]) &, #1[[ 3]] && ((#1[[1]]; True) && (#1[[1]]; True)) &, #1[[ 3]] && (#1[[1]] || #1[[2]]) &, #1[[ 1]] || (#1[[2]] && #1[[3]]) &, #1[[ 1]] || (#1[[2]] || #1[[3]]) &, #1[[ 2]] || (#1[[1]] && #1[[3]]) &, #1[[3]] || (#1[[1]] && #1[[2]]) &} We got 19 of the 20. But when we try again, In[389]:= cull[Union[% // tim, cull[Outer[Distribute[And[#1, #2], Function] &, three, %] // Flatten // tim] // tim, cull[Outer[Distribute[Or[#1, #2], Function] &, three, %] // Flatten // tim] // tim]] // tim During evaluation of In[389]:= 0.000017,19 During evaluation of In[389]:= 0.000214,95 During evaluation of In[389]:= 0.063244,19 During evaluation of In[389]:= 0.000211,95 During evaluation of In[389]:= 0.016854,19 During evaluation of In[389]:= 0.090048,19 . . . we stick at 19. The solution is to Outer with the first iterate, In[458]:= bool2alg /@ %387 Out[458]= {0, 1, p, p q, p r, q, q r, r, p + q, p + r, q + r} rather than {0, p, q, r, 1}, the 0th. In[390]:= cull[Union[% // tim, cull[Outer[Distribute[And[#1, #2], Function] &, %387, %] // Flatten // tim] // tim, cull[Outer[Distribute[Or[#1, #2], Function] &, %387, %] // Flatten // tim] // tim]] // tim During evaluation of In[390]:= 0.000018,19 During evaluation of In[390]:= 0.000466,209 During evaluation of In[390]:= 0.200324,20 During evaluation of In[390]:= 0.00059,209 During evaluation of In[390]:= 0.037646,20 During evaluation of In[390]:= 0.248116,20 Out[390]= {((#1[[1]]; False) && (#1[[1]]; False)) && ((#1[[1]]; False) && ((#1[[1]]; False) && ((#1[[1]]; False) && (#1[[1]]; False)))) &, ((#1[[ 1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]] || #1[[2]]))) &, ((#1[[ 1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]] || #1[[3]]))) &, ((#1[[ 1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[2]] || #1[[3]]))) &, ((#1[[ 1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && (#1[[1]] || (#1[[2]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && (#1[[1]] || (#1[[2]] || #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && (#1[[2]] || (#1[[1]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && (#1[[3]] || (#1[[1]] && #1[[2]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && ((#1[[1]]; True) && (#1[[2]] || #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && (#1[[1]] && (#1[[1]] && #1[[2]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && (#1[[1]] && (#1[[1]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && (#1[[1]] && (#1[[2]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 2]] && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 2]] && ((#1[[1]]; True) && (#1[[1]] || #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 2]] && (#1[[2]] && (#1[[2]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 3]] && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 3]] && ((#1[[1]]; True) && (#1[[1]] || #1[[2]]))) &, (#1[[ 1]] || #1[[2]]) && ((#1[[1]]; True) && (#1[[3]] || (#1[[1]] && #1[[2]]))) &} The last one: In[391]:= bool2alg@%[[-1]] Out[391]= (p + q) (p q + r) is not obviously symmetric. In[392]:= ttab@%%[[-1]] == ttab@alg2bool[p q + p r + q r] Out[392]= True Note that this function is insensitive to swapping And with Or: In[459]:= p q + p r + q r /. {Times -> Plus, Plus -> Times} Out[459]= (p + q) (p + r) (q + r) In[460]:= bool2alg@alg2bool@Expand@% Out[460]= p q + p r + q r + p q r (I didn't write a simplifier, but the p q r is clearly redundant.) The 7581st function was (p + q + r) (p + q + s) (p + r + s) (q + r + s) (p + q + t) (p + r + t) (q + r + t) (p + s + t) (q + s + t) (r + s + t) == p q r + p q s + p r s + q r s + p q t + p r t + q r t + p s t + q s t + r s t While guessing and testing this, the all-day (46000 second) cull finished. But I was a couple of minutes bringing up the window, and the PoS OSX decided to reboot. This was almost certainly not a hardware error. Tom Knight told me Microsoft and Apple don't even try to makes stable environments. Symbolics Genera stayed up months at a time. If anyone from Symbolics offered to teach the big guys how to make stable systems, they would have been shown the door. But I bet Google knows how to do it. Code: In[376]:= Clear@bool2alg; bool2alg[bool_] := (bool /. {False -> 0, True -> 1, And -> Times, Or -> Plus})@{p, q, r, s, t} /. x_^_ :> x In[377]:= five = {(#[[1]]; False) &, #[[1]] &, #[[2]] &, #[[3]] &, #[[ 4]] &, #[[5]] &, (#[[1]]; True) &} Out[377]= {(#1[[1]]; False) &, #1[[1]] &, #1[[2]] &, #1[[3]] &, #1[[ 4]] &, #1[[5]] &, (#1[[1]]; True) &} In[378]:= bool2alg /@ % Out[378]= {0, p, q, r, s, t, 1} In[448]:= Clear@alg2bool; alg2bool[exp_] := exp //. Except[0, _Integer] :> 1 /. { 0 -> ((#1[[1]]; False) &), 1 -> ((#1[[1]]; True) &)} /. S : (p | q | r | s | t) :> (#[[x]] & /. x :> Evaluate@(Position[{p, q, r, s, t}, S][[1, 1]])) /. {Times -> And, Plus -> Or} //. f : (And | Or)[Function[_] ..] :> Distribute[f, Function] In[380]:= alg2bool /@ %% Out[380]= {(#1[[1]]; False) &, #1[[1]] &, #1[[2]] &, #1[[3]] &, #1[[ 4]] &, #1[[5]] &, (#1[[1]]; True) &} In[381]:= Clear@ttab; ttab[fn_] := shrink[fn /@ Block[{n = Cases[fn, HoldPattern@Part[_, n_] :> n, 99] // Max}, PadLeft[#, n, False] & /@ (IntegerDigits[#, 2] & /@ Range[0, 2^n - 1]) /. {0 -> False, 1 -> True}]] In[382]:= shrink[L_List] := NestWhile[Transpose[Partition[#, 2]][[1]] &, L, Riffle[#2, #2] == #1 &, 2, \[Infinity], -1] Clear@cull; cull[L_List] := #[[1]] & /@ DeleteDuplicates[Prepend[ttab@#, #] & /@ L, Rest@#1 == Rest@#2 &] --rwg

2 1

[math-fun] Draft of my January 2017 blog post
by James Propp 12 Jan '17

12 Jan '17

Hi, I started writing a new draft titled "Avoiding chazakah with the Prouhet-Thue-Morse sequence" and would love to get your feedback. I plan on publishing it on the 17th (sorry to be sending this out so late!). I would be especially interested in knowing about more good visuals (and "audibles"!) related to the Prouhet-Thue-Morse sequence. (I'm trying to get the publisher of Per Norgard's "Drumbook" to give me permission to use an excerpt from the accompanying CD, but I don't know if that will come through in time.) Suggestions for references, and comments of all kinds, are welcome. As usual, the piece is too long, so one useful form of feedback would be "The part about X isn't bad, but it's not as interesting as the other parts" (especially if many pre-readers single out the same X). And, more generally, I appreciate candid criticism from people who are sympathetic to my aims but think I've fallen short of them. My prose style is designed to make the material accessible, but my breeziness should not be interpreted as indicating indifference to scholarly correctness. Keep in mind that all math-fun feedback goes into one mail-feed, so I won't know whose feedback is whose unless you sign your comment. Also, all substantive suggestions that I use will be acknowledged (unless you specifically ask me not to do this). Please leave your feedback here: https://mathenchant.wordpress.com?p=1422&shareadraft=587802aa41b63 Title: Avoiding chazakah with the Prouhet-Thue-Morse sequence Beginning: The ingredients of today's midwinter mathematical stew will include beans, boats, never-ending chess games, a Dane named Per who's into aperiodic percussion, an ABBA that hails from Norway rather than Sweden, a song from Jewish summer camps, and a way to prove 0^2 + 3^2 + 5^2 + 6^2 = 1^2 + 2^2 + 4^2 + 7^2 using calculus instead of a calculator ... Read more: https://mathenchant.wordpress.com?p=1422&shareadraft= 587802aa41b63 Thanks, Jim Propp

1 0