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@kntv.be; gef@iap.fr; Nicolas.Graner@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@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@mailman.xmission.com <mailto:math-fun@mailman.xmission.com>> Cc: Gilles Esposito-Farese <gef@iap.fr <mailto:gef@iap.fr>>, Nicolas Graner <Nicolas.Graner@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@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>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun