Brad, [Apologies for the delay in responding; I forgot about this until today, when I worked through Bill Gosper's exercise ("find a short, branchless MMIX computation that computes the inverse of any given 8x8 matrix X of 0s and 1s, modulo 2, if det X is odd") from TAOCP and therefore ended up being reminded of exponents of the general linear group GL_n(F_2).] The idea behind my Mathematica code is to compute the period much more efficiently (in terms of asymptotic complexity) than explicitly running the cellular automaton and using a cycle detection algorithm. Specifically, we know that the order must divide the exponent of the general linear group GL_n(F_2) because the rule is a linear function on the vector space (F_2)^n. So we just need to do the following: 1. Let k := exponent of GL_n(F_2) (see http://oeis.org/A211171) 2. For each prime factor p dividing k, check whether the oscillator repeats with a period of k/p. (We can simulate k/p steps in time polynomial in log(k/p) by repeated squaring of the matrix which describes the linear map.) 3. If some prime exists, set k to be k/p and jump back to step 2. 4. Otherwise, k is the period of the oscillator. The only non-polynomial-time step here is the prime factorisation, but we already know the prime factors of the exponents of GL_n(F_2) when n <= 1206 (see https://oeis.org/A046800) so it's practical to compute the first 1206 terms of A211171. -------- I'm thinking of writing a program to solve problems of the form 'given a matrix A over F_2 and vectors {u, v}, find the smallest positive integer n (if such an n exists) satisfying A^n u == v'. I think it's reducible to discrete logarithm in a power-of-2 finite field, which can be done relatively efficiently: http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf In particular, it would allow one to efficiently find a solution to the 'no explicit example has been made' at the end of this webpage: https://www.ics.uci.edu/~eppstein/ca/replicators/b368s12578.html Of perhaps greater practical interest is the fact that it solves the problem: 'given a PRNG which uses a known linear feedback shift register, and given its initial state and current output, compute the number of steps for which it has been run'. Best wishes, Adam P. Goucher
Sent: Wednesday, May 06, 2020 at 6:45 PM From: "Brad Klee" <bradklee@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Subject: [math-fun] Missing C.A. Period Analyses.
I double checked, and made a few more conjectures on case splitting:
1. Periodic cases: a(c1*(n+1)+c2)=a(c1*n+c2)+c3(c2) {190, 41, 9, 107, 25} -> {A334501, A334509, A334511, A33514, A33513}
2. For large n, a(n)=3 {62, 131} -> {A334502, A334503}
3. Sequence should be viewed as table with rows a(2^n),a(2^n+1),...,a(2^(n+1)-1) {26, 169, 161, 45, 105} -> {A334504, A334505, A334506, A334508, A334512} Also, 73->A334510, but the pattern is not as easy to see.
The most interesting case was anomalous 122 -> A334507. It is halfway periodic, only on the even terms:
In[]= a[122, 2 #] & /@ Range[1, 20] In[]=a[122, 2 # + 1] & /@ Range[1, 20]
Out[]= {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2} Out[]= {1, 2, 1, 6, 4, 14, 1, 14, 12, 62, 8, 126, 28, 30, 1, 30, 28, 1022, 24, 126}
Highly likely that the second sequence is http://oeis.org/A268754. Comparing with APG's mma def. Jan. 13 2009, definition via C.A. seems the more simple. This looks interesting, but I don't know the convention of A268754, so could not check rigorously just yet.
Maybe it is easy though. Adam, is there an isomorphism here?
--Brad
On Tue, May 5, 2020 at 3:56 PM Neil Sloane <njasloane@gmail.com> wrote:
Brad, Thanks for answering (on April 26) my questions about the period length of rule 30, etc.
I've just created sequences A334496, A334497, and A334501-A334515 as a result of your reply.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun