[math-fun] Interleavings of three arithmetic progressions
Some of you may recall my interest in the sequence 1, 2, 4, 8, 14, 24, 36 ... of the number of ways it is possible to interleave N elements chosen from two non-intersecting arithmetic progressions. Another way to view this is as (closely related to) the number of rasterized straight line segments with N+1 pixels, where we light up a pixel if a geometric line intersects its rectangle of screen real estate. The sequence is in OEIS as A005598 ( http://www.research.att.com/~njas/sequences/A005598), and is apparently originally due to Leendert "Leo" Dorst, who wrote about it for his doctoral research, first mentioning it in 1984. Oddly, the corresponding sequence for three arithmetic progressions is, perhaps, not in OEIS yet. The alternative formulation involves polycube models of three-dimensional line segments. Unless I've made a mistake in my enumerations, the sequence begins 1, 3, 9, 27, 75, 189 ... and OEIS has nothing with those elements. Unfortunately, my calculations are all with pen and paper; I haven't written any code to do the counting. So it's quite possible that I blundered, and that OEIS has the sequence after all. Can another funster verify my work? (I have one more element, which I'm holding back to avoid the power of suggestion.) There is an obvious generalization to any number of progressions/dimensions.
For the counts f_3(n) of interleaving words in m = 3 dimensions, of length n for n = 0, ..., 8, I propose the values: 1, 3, 9, 27, 75, 189, 447, 951, 1911 It should be admitted that these are strictly speaking lower bounds. They confirm those of Allan's values currently revealed; those concealed are awaited with anticipation ... For n > 0, easily f_3(n) = 3 (mod 6); since under permutations of A,B,C, {A^n, B^n, C^n} is the only class having just 3 isomorphs rather than 6. Is f_3(n) asymptotically polynomial in n; has it a civilised explicit expression? [For comparison, OEIS A005598 asserts f_2(n) ~ n^3 / pi^2; and explicitly f_2(n) = 1 + \sum_1^n (n-i+1) phi(i), where phi(n) denotes the Euler totient A000010.] Having convincingly failed to come up with anything like a decently efficient algorithm, I was eventually driven to resort to a Monte-Carlo attack based on the original definition. Each trial generates m random AP's filling an interval, sorts them, recovers the generating AP for each term, and the resulting discrete sequence is added to the language set. If doubling the number of trials leaves the size of this language unaltered, its size is accepted as the final value of f_m(n). For m,n = 3,8 the final Maple run of 750,000 trials occupied 1.5 hrs. Fred Lunnon On 7/21/10, Allan Wechsler <acwacw@gmail.com> wrote:
Some of you may recall my interest in the sequence 1, 2, 4, 8, 14, 24, 36 ... of the number of ways it is possible to interleave N elements chosen from two non-intersecting arithmetic progressions. Another way to view this is as (closely related to) the number of rasterized straight line segments with N+1 pixels, where we light up a pixel if a geometric line intersects its rectangle of screen real estate. The sequence is in OEIS as A005598 ( http://www.research.att.com/~njas/sequences/A005598), and is apparently originally due to Leendert "Leo" Dorst, who wrote about it for his doctoral research, first mentioning it in 1984.
Oddly, the corresponding sequence for three arithmetic progressions is, perhaps, not in OEIS yet. The alternative formulation involves polycube models of three-dimensional line segments. Unless I've made a mistake in my enumerations, the sequence begins 1, 3, 9, 27, 75, 189 ... and OEIS has nothing with those elements.
Unfortunately, my calculations are all with pen and paper; I haven't written any code to do the counting. So it's quite possible that I blundered, and that OEIS has the sequence after all. Can another funster verify my work? (I have one more element, which I'm holding back to avoid the power of suggestion.)
There is an obvious generalization to any number of progressions/dimensions. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 7/23/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
For the counts f_3(n) of interleaving words in m = 3 dimensions, of length n for n = 0, ..., 8, I propose the values:
1, 3, 9, 27, 75, 189, 447, 951, 1911 ...
Value f_3(8) = 1911 further confirmed by 2-hour run of a million trials. If the words are assumed to be uniformly distributed, the expected number of trials to find all X = f_m(n) should be about X log X, by a standard cigarette card / Pokemon token collecting argument. The program performance is substantially worse, because uniform distribution of AP's skews words away from those with long blocks of fewer than m symbols: the situation might be improved by skewing the AP's deliberately to counterbalance the effect, but it's a delicate business. More satisfactory would be a viable deterministic algorithm! WFL
Counts up through length 12 are: 1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267 It's not hard to do deterministically, in a computer algebra package. To check if a string like "ABCABA" is a feasible interleaving characteristic string, you just transform it into a set of linear inequalities constraining the six unknowns describing the three arithmetic progressions, and test whether there's a solution. In addition to the obvious checks -- e.g. that the second term in the As progression is larger than the first of the Cs and smaller than the second of the Bs -- you need extra inequalities asserting that the last term mentioned in the string (here the third A) is smaller than each term that implicitly comes after the string (fourth A, third B, second C). And likewise for the terms that come before the string starts. Something like Mma has no trouble finding an arbitrary point in the solution space for a set of linear equalities, or else proving that the set is empty. Code below, as long as you promise not to complain about poor style. Of course you don't take all strings of length n; rather you first list all the strings of length n-1, and then append each of A,B,C to them and test the results. The time to verify each candidate string goes up with n, of course -- you're adding inequalities, though only at a linear rate and still over a six-dimensional space, and you're also increasing the number of putative strings that need checking. The exhaustive enumeration up through length 12 took under 7 minutes. --Michael (* Number of ways to interleave N elements from 3 arithmetic seqs *) (* Given a string like "ABCABA", produce a set of inequalities *) (* about the three arithmetic progressions giving successive A/B/Cs *) (* The Nth occurrence (1-indexed) of character X corresponds to the value *) (* BASE[X] + N * DELTA[X] *) (* In all functions, seq is eg {"A", "B", "C", "A", "B", "A"} *) (* The arithmetic-progression value of the ith element of seq *) value[seq_, i_] := BASE[seq[[i]]] + DELTA[seq[[i]]] * numoccur[seq,i] numoccur[seq_, i_] := Count[Take[seq,If[i>0,i,Length[seq]+i+1]],seq[[i]]] (* First element of the seq is greater than anything that would precede it *) lowerbound[seq_] := (BASE[#] < value[seq,1])& /@ Union[seq] (* Each element of the seq is greater than the previous one *) upperbound[seq_] := (value[seq,-1] < value[Append[seq,#],-1])& /@ Union[seq] (* Last element of the seq is less than anything that would follow it *) ordering[seq_] := Table[ value[seq,i] < value[seq,i+1], {i,Length[seq]-1} ] ineqs[seq_] := Join[ lowerbound[seq], ordering[seq], upperbound[seq] ] vars[seq_] := Join @@ ({BASE[#],DELTA[#]}& /@ Union[seq]) witness[seq_] := FindInstance[ ineqs[seq], vars[seq] ] witness[s_String] := witness[Characters[s]] (* All obtainable length-n shuffles of three arithmetic seqs: *) names = {"A", "B", "C"} shuf[0] := {""} candidates[n_] := Flatten[Table[ob<>ch, {ob,shuf[n-1]}, {ch, names}]] shuf[n_] := shuf[n] = Select[ candidates[n], witness[#] != {}& ] --------- In[18]:= Table[Length[shuf[i]],{i,0,12}] Out[18]= {1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267} In[19]:= TimeUsed[]/60 Out[19]= 6.73642 On Fri, Jul 23, 2010 at 7:12 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 7/23/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
For the counts f_3(n) of interleaving words in m = 3 dimensions, of length n for n = 0, ..., 8, I propose the values:
1, 3, 9, 27, 75, 189, 447, 951, 1911 ...
Value f_3(8) = 1911 further confirmed by 2-hour run of a million trials.
If the words are assumed to be uniformly distributed, the expected number of trials to find all X = f_m(n) should be about X log X, by a standard cigarette card / Pokemon token collecting argument. The program performance is substantially worse, because uniform distribution of AP's skews words away from those with long blocks of fewer than m symbols: the situation might be improved by skewing the AP's deliberately to counterbalance the effect, but it's a delicate business.
More satisfactory would be a viable deterministic algorithm! WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Oof -- and of course it would take 1/6 the time if you say WLOG that A/B/C first appear in alphabetical order, then count each string with weight 1 or 3 or 6, depending on whether it mentions 1 or 2 or 3 of the sequences. --Michael On Fri, Jul 23, 2010 at 10:39 AM, Michael Kleber <michael.kleber@gmail.com>wrote:
Counts up through length 12 are:
1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267
It's not hard to do deterministically, in a computer algebra package. To check if a string like "ABCABA" is a feasible interleaving characteristic string, you just transform it into a set of linear inequalities constraining the six unknowns describing the three arithmetic progressions, and test whether there's a solution.
In addition to the obvious checks -- e.g. that the second term in the As progression is larger than the first of the Cs and smaller than the second of the Bs -- you need extra inequalities asserting that the last term mentioned in the string (here the third A) is smaller than each term that implicitly comes after the string (fourth A, third B, second C). And likewise for the terms that come before the string starts.
Something like Mma has no trouble finding an arbitrary point in the solution space for a set of linear equalities, or else proving that the set is empty. Code below, as long as you promise not to complain about poor style.
Of course you don't take all strings of length n; rather you first list all the strings of length n-1, and then append each of A,B,C to them and test the results.
The time to verify each candidate string goes up with n, of course -- you're adding inequalities, though only at a linear rate and still over a six-dimensional space, and you're also increasing the number of putative strings that need checking. The exhaustive enumeration up through length 12 took under 7 minutes.
--Michael
(* Number of ways to interleave N elements from 3 arithmetic seqs *)
(* Given a string like "ABCABA", produce a set of inequalities *) (* about the three arithmetic progressions giving successive A/B/Cs *) (* The Nth occurrence (1-indexed) of character X corresponds to the value *) (* BASE[X] + N * DELTA[X] *)
(* In all functions, seq is eg {"A", "B", "C", "A", "B", "A"} *)
(* The arithmetic-progression value of the ith element of seq *) value[seq_, i_] := BASE[seq[[i]]] + DELTA[seq[[i]]] * numoccur[seq,i] numoccur[seq_, i_] := Count[Take[seq,If[i>0,i,Length[seq]+i+1]],seq[[i]]]
(* First element of the seq is greater than anything that would precede it *) lowerbound[seq_] := (BASE[#] < value[seq,1])& /@ Union[seq] (* Each element of the seq is greater than the previous one *) upperbound[seq_] := (value[seq,-1] < value[Append[seq,#],-1])& /@ Union[seq] (* Last element of the seq is less than anything that would follow it *) ordering[seq_] := Table[ value[seq,i] < value[seq,i+1], {i,Length[seq]-1} ]
ineqs[seq_] := Join[ lowerbound[seq], ordering[seq], upperbound[seq] ] vars[seq_] := Join @@ ({BASE[#],DELTA[#]}& /@ Union[seq])
witness[seq_] := FindInstance[ ineqs[seq], vars[seq] ] witness[s_String] := witness[Characters[s]]
(* All obtainable length-n shuffles of three arithmetic seqs: *) names = {"A", "B", "C"}
shuf[0] := {""} candidates[n_] := Flatten[Table[ob<>ch, {ob,shuf[n-1]}, {ch, names}]] shuf[n_] := shuf[n] = Select[ candidates[n], witness[#] != {}& ]
--------- In[18]:= Table[Length[shuf[i]],{i,0,12}]
Out[18]= {1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267}
In[19]:= TimeUsed[]/60
Out[19]= 6.73642
On Fri, Jul 23, 2010 at 7:12 AM, Fred lunnon <fred.lunnon@gmail.com>wrote:
On 7/23/10, Fred lunnon <fred.lunnon@gmail.com> wrote:
For the counts f_3(n) of interleaving words in m = 3 dimensions, of length n for n = 0, ..., 8, I propose the values:
1, 3, 9, 27, 75, 189, 447, 951, 1911 ...
Value f_3(8) = 1911 further confirmed by 2-hour run of a million trials.
If the words are assumed to be uniformly distributed, the expected number of trials to find all X = f_m(n) should be about X log X, by a standard cigarette card / Pokemon token collecting argument. The program performance is substantially worse, because uniform distribution of AP's skews words away from those with long blocks of fewer than m symbols: the situation might be improved by skewing the AP's deliberately to counterbalance the effect, but it's a delicate business.
More satisfactory would be a viable deterministic algorithm! WFL
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
-- Forewarned is worth an octopus in the bush.
Well, that's me put out of my misery, anyway. The OEIS entry did actually try to say owt about the inequality-based method, but it didn't sink in --- I scuttled off instead to cobble up a formal-language, morphism-based approach --- which did get somewhere at first, but then fell over once m > 2. On 7/23/10, Michael Kleber <michael.kleber@gmail.com> wrote:
Oof -- and of course it would take 1/6 the time if you say WLOG that A/B/C first appear in alphabetical order, then count each string with weight 1 or 3 or 6, depending on whether it mentions 1 or 2 or 3 of the sequences.
--Michael
But you shouldn't do this straight away --- collect as much test data as convenient with the dumb program, to verify the more complex (and logically fragile) faster version later! How about letting the final version rip for an hour or so, then submit something for OEIS to chew on?
On Fri, Jul 23, 2010 at 10:39 AM, Michael Kleber
<michael.kleber@gmail.com>wrote:
Counts up through length 12 are:
1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267
It's not hard to do deterministically, in a computer algebra package. To check if a string like "ABCABA" is a feasible interleaving characteristic string, you just transform it into a set of linear inequalities constraining the six unknowns describing the three arithmetic progressions, and test whether there's a solution.
In addition to the obvious checks -- e.g. that the second term in the As progression is larger than the first of the Cs and smaller than the second of the Bs -- you need extra inequalities asserting that the last term mentioned in the string (here the third A) is smaller than each term that implicitly comes after the string (fourth A, third B, second C). And likewise for the terms that come before the string starts.
Something like Mma has no trouble finding an arbitrary point in the solution space for a set of linear equalities, or else proving that the set is empty. Code below, as long as you promise not to complain about poor style.
"linear inequalities" presumably? Not sure how, or if, Maple tackles these. [What, me complain? Nah --- I'm too busy chewing the carpet ...]
Of course you don't take all strings of length n; rather you first list all the strings of length n-1, and then append each of A,B,C to them and test the results.
The time to verify each candidate string goes up with n, of course -- you're adding inequalities, though only at a linear rate and still over a six-dimensional space, and you're also increasing the number of putative strings that need checking. The exhaustive enumeration up through length 12 took under 7 minutes.
--Michael
Any ideas on functional recursions, explicit expressions, asymptotics? Fred Lunnon
On Fri, Jul 23, 2010 at 12:34 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Well, that's me put out of my misery, anyway. The OEIS entry did actually try to say owt about the inequality-based method, but it didn't sink in --- I scuttled off instead to cobble up a formal-language, morphism-based approach --- which did get somewhere at first, but then fell over once m > 2.
Yep: I didn't have time to think, which is why I had Mma do it for me...
On 7/23/10, Michael Kleber <michael.kleber@gmail.com> wrote:
Oof -- and of course it would take 1/6 the time if you say WLOG that A/B/C first appear in alphabetical order, then count each string with weight 1 or 3 or 6, depending on whether it mentions 1 or 2 or 3 of the sequences.
--Michael
But you shouldn't do this straight away --- collect as much test data as convenient with the dumb program, to verify the more complex (and logically fragile) faster version later!
How about letting the final version rip for an hour or so, then submit something for OEIS to chew on?
I'm satisfied with the first 12 terms validating the correctness of the symmetry-aware version. Just made the change, and it reproduced those 12 terms in 67 seconds. During the time I spent composing this email, it's gotten up to n=16: 1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267, 29013, 44691, 67251, 98547 I'll let it run for a while and post here. Allan is welcome to own the OEIS entry :-).
On Fri, Jul 23, 2010 at 10:39 AM, Michael Kleber
<michael.kleber@gmail.com>wrote:
Counts up through length 12 are:
1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267
It's not hard to do deterministically, in a computer algebra package. To check if a string like "ABCABA" is a feasible interleaving characteristic string, you just transform it into a set of linear inequalities constraining the six unknowns describing the three arithmetic progressions, and test whether there's a solution.
In addition to the obvious checks -- e.g. that the second term in the As progression is larger than the first of the Cs and smaller than the second of the Bs -- you need extra inequalities asserting that the last term mentioned in the string (here the third A) is smaller than each term that implicitly comes after the string (fourth A, third B, second C). And likewise for the terms that come before the string starts.
Something like Mma has no trouble finding an arbitrary point in the solution space for a set of linear equalities, or else proving that the set is empty. Code below, as long as you promise not to complain about poor style.
"linear inequalities" presumably? Not sure how, or if, Maple tackles these.
Yes, "linear inequalities", of course. Mma will even let you restrict to integer solutions, though in this case the systems are homogeneous, so there's no difference in solvability. I don't know anything about the maple side.
[What, me complain? Nah --- I'm too busy chewing the carpet ...]
Of course you don't take all strings of length n; rather you first
list all
the strings of length n-1, and then append each of A,B,C to them and test the results.
The time to verify each candidate string goes up with n, of course -- you're adding inequalities, though only at a linear rate and still over a six-dimensional space, and you're also increasing the number of putative strings that need checking. The exhaustive enumeration up through length 12 took under 7 minutes.
--Michael
Any ideas on functional recursions, explicit expressions, asymptotics?
Not I; see "didn't have time to think" above... --Michael -- Forewarned is worth an octopus in the bush.
On 7/23/10, Michael Kleber <michael.kleber@gmail.com> wrote:
On Fri, Jul 23, 2010 at 12:34 PM, Fred lunnon <fred.lunnon@gmail.com> wrote: ... I'm satisfied with the first 12 terms validating the correctness of the symmetry-aware version. Just made the change, and it reproduced those 12 terms in 67 seconds. During the time I spent composing this email, it's gotten up to n=16:
1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267, 29013, 44691, 67251, 98547
Great stuff! (methodically unclenching teeth)
I'll let it run for a while and post here. Allan is welcome to own the OEIS entry :-).
Yes indeed.
Any ideas on functional recursions, explicit expressions, asymptotics?
Not I; see "didn't have time to think" above...
Hmm ... evalf(log(98547/67251)/log(16/15)); 5.920521497 evalf(log(67251/44691)/log(15/14)); 5.923217032 I wonder if perchance f_3(n) = O(n^6) ?? f_2(n) = O(n^3) must follow straightforwardly via standard results from the explicit formula in A005598; but I presently haven't a clue why that should hold either. Fred Lunnon
Interleavings of two translate to words reperesemting simple curves on a punctured torus. I think each one is also valid when extended in this case. The lex-min cyclic permutations are associated <--> their slope. Tjere are O(n^2) slopes admitting O(n) cyclic permutations. -- is there a good logical analysis of the 3D simplification base = slope for interleavings of 3? You can think of in terms of the cynical subdivision, as seen from the origin. Bill Sent from my iPhone On Jul 23, 2010, at 8:35 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 7/23/10, Michael Kleber <michael.kleber@gmail.com> wrote:
On Fri, Jul 23, 2010 at 12:34 PM, Fred lunnon <fred.lunnon@gmail.com> wrote: ... I'm satisfied with the first 12 terms validating the correctness of the symmetry-aware version. Just made the change, and it reproduced those 12 terms in 67 seconds. During the time I spent composing this email, it's gotten up to n=16:
1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267, 29013, 44691, 67251, 98547
Great stuff! (methodically unclenching teeth)
I'll let it run for a while and post here. Allan is welcome to own the OEIS entry :-).
Yes indeed.
Any ideas on functional recursions, explicit expressions, asymptotics?
Not I; see "didn't have time to think" above...
Hmm ... evalf(log(98547/67251)/log(16/15)); 5.920521497 evalf(log(67251/44691)/log(15/14)); 5.923217032 I wonder if perchance f_3(n) = O(n^6) ??
f_2(n) = O(n^3) must follow straightforwardly via standard results from the explicit formula in A005598; but I presently haven't a clue why that should hold either.
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Data update: the sequence through n=30 is 1,3,9,27,75,189,447,951,1911,3621,6513,11103,18267,29013,44691,67251,98547,140865,197679,272799,370659,497403,658371,859863,1110453,1420527,1799373,2260161,2815401,3479235,4269279 Looks more n^5ish than n^6ish, at a casual glance. The last term took something like 11 hours to count, so I think it's time to give Mma a break. --Michael On Fri, Jul 23, 2010 at 5:35 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 7/23/10, Michael Kleber <michael.kleber@gmail.com> wrote:
On Fri, Jul 23, 2010 at 12:34 PM, Fred lunnon <fred.lunnon@gmail.com> wrote: ... I'm satisfied with the first 12 terms validating the correctness of the symmetry-aware version. Just made the change, and it reproduced those 12 terms in 67 seconds. During the time I spent composing this email, it's gotten up to n=16:
1, 3, 9, 27, 75, 189, 447, 951, 1911, 3621, 6513, 11103, 18267, 29013, 44691, 67251, 98547
Great stuff! (methodically unclenching teeth)
I'll let it run for a while and post here. Allan is welcome to own the OEIS entry :-).
Yes indeed.
Any ideas on functional recursions, explicit expressions, asymptotics?
Not I; see "didn't have time to think" above...
Hmm ... evalf(log(98547/67251)/log(16/15)); 5.920521497 evalf(log(67251/44691)/log(15/14)); 5.923217032 I wonder if perchance f_3(n) = O(n^6) ??
f_2(n) = O(n^3) must follow straightforwardly via standard results from the explicit formula in A005598; but I presently haven't a clue why that should hold either.
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
On Jul 25, 2010, at 12:52 PM, Michael Kleber wrote:
1,3,9,27,75,189,447,951,1911,3621,6513,11103,18267,29013,44691,67251,98547,140865,197679,272799,370659,497403,658371,859863,1110453,1420527,1799373,2260161,2815401,3479235,4269279
Looks more n^5ish than n^6ish, at a casual glance.
The last term took something like 11 hours to count, so I think it's time to give Mma a break.
I noticed that your code recursively memorizes the results for smaller instances (dfn of shuf[n_]), so the timing should depend whether you're starting for scratch, or whether you just did a slightly smaller case --- especially if this is implemented as a polynomial time computation. But whatever, Mma probably has better things to do. Bill
On 7/25/10, Michael Kleber <michael.kleber@gmail.com> wrote:
Data update: the sequence through n=30 is
1,3,9,27,75,189,447,951,1911,3621, 6513,11103,18267,29013,44691,67251,98547,140865,197679,272799, 370659,497403,658371,859863,1110453,1420527,1799373,2260161,2815401,3479235, 4269279
Looks more n^5ish than n^6ish, at a casual glance.
evalf(log(4269279/3479235)/log(30/29)); # 6.036081126 evalf(log(3479235/2815401)/log(29/28)); # 6.033051457 No way --- it's order n^6 !!
The last term took something like 11 hours to count, so I think it's time to give Mma a break.
--Michael
Sterling effort. I've been trying hard to upstage it by finding an explicit formula, but am beginning to understand that the 3-D case may well qualitatively harder than the 2-D. There is a literature about generalisations of Sturmian sequences from 2-D / 2-symbol alphabet to n-D, which connects them to MDCF's. This particular generalisation is called "billiard words" (or "billiards words") --- the "words" here being what we might call infinite sequences, and "factors" finite words occurring within them. One reference which surveys these is the 2003 preprint available on the web: Laurent Vuillon "Balanced Words". A detailed study (also available on the web) is NICOLAS BEDARIDE "CLASSIFICATION OF ROTATIONS ON THE TORUS T^2" The following may well be very relevant, but I can't get at them from home: Jean-Pierre Borel "How to build billiard words using decimations" RAIRO-Theor. Inf. Appl. Volume 44, Number 1, January-March 2010 59--77 Jean-Pierre Borel "A geometrical Characterization of factors of multidimensional Billiards words and some Applications" Theoretical Computer Science 380 (2007) 286--303 http://hal.archives-ouvertes.fr/hal-00465586/fr/ The particular difficulty afflicting billiards --- in comparison with, say, the more common Arnaud-Rauzy generalisation --- is their nonlinear complexity: apparently, the number of distinct factors of length n in any given trajectory of cubical billiards (Allan's original problem) is in general n^2 + n + 1 . Fred Lunnon
participants (4)
-
Allan Wechsler -
Bill Thurston -
Fred lunnon -
Michael Kleber