Message Boards Message Boards

Enumerate all periodic sequences of some linear recurrences?

GROUPS:

For scientific purposes (code research) I am using Mathematica to enumerate all periodic sequences of some linear recurrences. As an example the command

Table[{Mod[i * 2^n + j * 4^n + k * 6^n, 7]},{i, 0, 5\}, {j, 0,   5}, {k, 0, 5}, {n, 0, 5}]

allows to enumerate all 216 distinct linear recurrent sequences in a finite field of order 7 (or mod 7) with characteristic polynomial whose roots are 2,4 and 6. The first five sequences it produces are:

{0, 0, 0, 0, 0, 0}, {1, 6, 1, 6, 1, 6}, {2, 5, 2, 5, 2, 5}, {3, 4, 3, 4, 3, 4}, {4, 3, 4, 3, 4, 3}, …

I have two questions:

i) The first sequence is obtained when i=0,j=0,k=0; the second when i=0,j=0,k=1, the third when i=0,j=0,k=2, etc. Is there a way to join these numbers with the sequence they generate so that I will know these parameters and therefore to be able to, later (if needed), generate a particular sequence? That is I would like that the output would be something like this

{{0, 0, 0, 0, 0, 0},{0,0,0}},  {{1, 6, 1, 6, 1, 6},{0,0,1}},  {{2, 5, 2, 5, 2, 5},{0,0,2}} , etc.

ii) In the example above (3rd order linear recurrence, and mod 7) the number of sequences obtained (216) is manageable by hand; but this number grows very quickly when the linear recurrence has order higher than 3 and the field has characteristic higher than 7. And, in those cases, most of the sequences that are produced are of no interest to me. I think that I could throw away at least 99% of the sequences that do not interest me if I could add a command that would read the output (the sequences obtained) and would say “I only want the sequences such that the products of its elements is 216 (say)”: from the five sequences above only {1, 6, 1, 6, 1, 6} would remain because 1 x6x1x6x1x6 = 216; or “I only want the sequences such that the products of its elements is 216 or 1000 (say)” from the five sequences above {1, 6, 1, 6, 1, 6} and {2, 5, 2, 5, 2, 5} would remain because 1x6x1x6x1x6 = 216 and 2x5x2x 5x2x 5=1000.

Is it possible to do this?

Thank you in advance.

POSTED BY: Joaquim Nogueira
Answer
1 month ago

Everything is an expression in Mathematica. If you imagine that you're using commands, you'll thoroughly misunderstand what's going on.

In particular, the first argument of Table can be pretty much any expression at all. So, make it a list of all the things you want to tabulate together:

Table[{Mod[i*2^n + j*4^n + k*6^n, 7], {i, j, k}}, ...

Now, the result is:

{{{{{0, {0, 0, 0}}, {0, {0, 0, 0}}, {0, {0, 0, 0}}}, {{1, {0, 0, 1}}, {6, {0, 0, 1}}, 
{1, {0, 0, 1}}}, {{2, {0, 0, 2}}, {5, {0, 0, 2}}, {2, {0, 0, 2}}}}, ...
POSTED BY: John Doty
Answer
1 month ago

As your needs get more elaborate, it is useful to factor your problem into simpler subproblems. You may then combine the factors to get your result. So, your elementary calculation appears to be:

seq[i_, j_, k_] := Table[Mod[i*2^n + j*4^n + k*6^n, 7], {n, 0, 5}]

Try it:

seq[0, 0, 1]

yields:

{1, 6, 1, 6, 1, 6}

There are various ways to approach your filter problem. You can generate the whole list, and filter with something like Select, or you can check "on the fly". The latter is more fun here, so:

filtseq[i_, j_, k_, test_] := 
 With[{s = seq[i, j, k]}, If[test[s], {s, {i, j, k}}, Nothing]]

This takes your indices, along with a test function. If the test, applied to the sequence, yields True, it yields the sequence packaged with its indices. If not, it yields Nothing. Mathematica is not a procedural programming language. It is an expression rewriting system. In particular, the rewrite rules bound to Nothing cause it to disappear without a trace from lists. Here, the With allows me to avoid evaluating the sequence twice by evaluating it once and giving the result a local name, s.

The next step is to write your test:

testprod[seq_] := Times @@ seq == 216 || Times @@ seq == 1000

Times@@ is an idiom for multiplying the elements of a list. Look at its FullForm some time. A With would be good here, too, but I'm lazy.

Always try out your definitions. Keep them simple. Don't expect to construct a complicated program and have it work the first time, or to produce comprehensible output if it doesn't.

testprod[{1, 6, 1, 6, 1, 6}]

Yields True. Other tests omitted here. Next, try the higher level:

filtseq[0, 0, 1, testprod]
{{1, 6, 1, 6, 1, 6}, {0, 0, 1}}

filtseq[1, 0, 1, testprod]
Nothing

I don't entirely understand what you want at higher level, but at least we have some basic building blocks. Here's a function that keeps your original definition of the sequences, but lets you change the filter criterion:

seqlist[test_] := 
 Flatten[Table[filtseq[i, j, k, test], {i, 0, 5}, {j, 0, 5}, {k, 0, 5}], 2]

The Table makes a deeply nested list. The Flatten here takes away the top two layers of nesting.

seqlist[testprod]
{{{1, 6, 1, 6, 1, 6}, {0, 0, 1}}, {{2, 5, 2, 5, 2, 5}, {0, 0, 2}}, {{5, 2, 5, 2, 5, 2}, {0, 0, 5}}}

Note that the test need not be a named function. An anonymous Function expression works fine:

seqlist[Times @@ # == 64 &]
{{{1, 4, 2, 1, 4, 2}, {0, 1, 0}}, {{2, 1, 4, 2, 1, 4}, {0, 2, 0}},
 {{4, 2, 1, 4, 2, 1}, {0, 4, 0}}, {{1, 2, 4, 1, 2, 4}, {1, 0, 0}}, 
 {{2, 4, 1, 2, 4, 1}, {2, 0, 0}}, {{4, 1, 2, 4, 1, 2}, {4, 0, 0}}}
POSTED BY: Updating Name
Answer
1 month ago

Thank you. I will try these instructions and see if they can be adapted to my needs.

By the way the reason I was checking the product of the elements of these sequences was because I am trying to find if they belong to a multiplicative group. As I know beforehand the multiplicative groups that exist mod 7, or mod 11, or mod 13, etc. I also know what is the result obtained when multiplying their elements; call M such a number. So, if I search sequences such that when I multyply their elements I obtain the number M, this sequence (as a set) is a good candidate to be a group, and thus I must check it more carefully.

POSTED BY: Joaquim Nogueira
Answer
1 month ago

Group Abstract Group Abstract