Can Esposito-Farèse report the maximum amount of backtracking that he needed to do on his depth-first search? That is, what is the longest suffix he had to abandon in order to extend the sequence by one bit? Also, has anybody carefully inspected the Esposito-Farèse sequence to see if it obeys any obvious production rules? By hand, I have 001001010010011001... On Wed, Jan 18, 2017 at 8:54 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Very interesting question!
We can say that there exists a minimal cubefree real, because the set of cubefree reals is a closed subset of Cantor space.
By compactness, if an interval [a, b] contains *no* cubefree reals, then there exists some N such that, for every real in [a, b], there is a witness to non-cubefree-ness in the first N digits.
So we *can* construct the minimal cubefree real, simply by performing a depth-first traversal of the tree of binary sequences, backtracking whenever we obtain a witness to non-cubefree-ness. This procedure is guaranteed to converge, but I don't have any explicit bounds for the rate of convergence (i.e. how many steps it takes before the Nth digit stabilises).
Best wishes,
Adam P. Goucher
Sent: Wednesday, January 18, 2017 at 1:30 PM From: "Eric Angelini" <Eric.Angelini@kntv.be> To: math-fun <math-fun@mailman.xmission.com> Cc: "Gilles Esposito-Farese" <gef@iap.fr>, "'Nicolas Graner'" < Nicolas.Graner@u-psud.fr> Subject: [math-fun] Thue-Morse and cubefree firs seq
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 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