Well, that's a nicer approach than mine! But ultimately equivalent, I believe. I've slightly improved the Python script to work correctly under both Python2 and Python3; I'm not sure everyone on math-fun is familiar with the unfortunate details of the Python language that cause the "python" command not to work on modern "Python" programs. Spoiler space 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 ---- import math TABLE = { (0, +1): (+1, True), # () (1, +1): (-1, False), # (0 1 2) (2, +1): (-1, True), # (0 2 1) (0, -1): (+1, False), # (0 1) (1, -1): (-1, True), # (1 2) (2, -1): (+1, True) # (0 2) } def compose(tr1, tr2): (t1, r1), (t2, r2) = tr1, tr2 return (t1 + r1*t2, r1*r2) def subst(x, y): z = {} for ((t0, r0), n0) in x.items(): # Let tr1 be the dequoted version of (t0, r0) t1 = (-t0) // 3 r1, should_substitute = TABLE[t0 % 3, r0] tr1 = (t1, r1) # and substitute where appropriate if should_substitute: for (tr2, n2) in y.items(): tr3 = compose(tr1, tr2) z[tr3] = z.get(tr3, 0) + n0 * n2 else: z[tr1] = z.get(tr1, 0) + n0 return z x = { (-1, +1): 1, (0, +1): 1, (+1, +1): 1 } print(sum(x.values())) for i in range(10): print(i) x = subst(x, x) print(sum(x.values())) On Wed, Aug 26, 2020 at 8:56 AM Robin Houston <robin.houston@gmail.com> wrote:
Since Tomas has now found the answer, perhaps it’s time for me to reveal my method. If you’re still thinking about it, and you don’t want a spoiler, don’t read on!
.
.
.
.
SPOILER BREAK
.
.
.
.
The reason this problem is not amenable to naive brute force is that the strings explode in length very rapidly. So the problem is really to find a more manageable representation of these strings. What I did – which I believe is the natural representation in a sense – is to represent them as **elements of the group ring of the infinite dihedral group**. Don’t worry, I shall explain…
Notation: I shall write ‘$x’ to refer to the two-character string consisting of a dollar sign followed by the letter x, and I shall write $x to refer to the value of the shell variable x.
If there were no quotation marks, and we were to start, more simply, with:
x=\$x\$x\$x
then each time we execute
eval x=$x
the number of occurrences of ‘$x’ would be squared, and so the sequence would be 3, 9, 81, ... with the (n+1)’st term equal to 3^2^n. This is therefore an upper bound on the true sequence.
That is not a great deal of use by itself, but it does suggest that the growth rate of the true sequence could be doubly-exponential – and certainly that it is no greater than that.
The complication we need to take account of in the real sequence is that occurrences of ‘$x’ that appear in single quotes inside $x will not be substituted.
If $x contains α occurrences of ‘$x’ that are in single quotes and β that are not, then the next value, obtained after executing
eval x=$x
will contain α + β(α + β) occurrences of ‘$x’.
For example, the initial value has α=1 and β=2, hence the second value of the sequence is 7.
In order to do this repeatedly, however, we need to know how many of the occurrences of ‘$x’ in the *new* value of $x occur within single quotes. And we must retain enough information that we can do this as many times as we need.
It would suffice to know, for each occurrence of ‘$x’ in $x, the sequence of ' and " characters to the left of that occurrence. Strings over a two-character alphabet are, of course, elements of the free monoid on two generators, which I’ll denote 2*.
So it would be sufficient to represent each value of $x as a set of elements of 2*. This is not a useful representation, yet, since it’s larger than just storing the whole string; but we shall improve it.
To determine whether an occurrence of ‘$x’ should be subject to substitution, we need to know whether it is inside single quotes. There is a (surjective) homomorphism of monoids from 2* to the symmetric group S_3 that maps ' to the permutation (0 1) and " to the permutation (0 2). I shall refer to the image under this homomorphism of some string of quotation marks as the “quotational effect” of that string.
To determine whether an occurrence of ‘$x’ is inside single quotes, we may take the string of quote marks to the left of that occurrence and compute the element of S_3 that it maps to under this homomorphism. Consider this permutation as a bijection π: {0,1,2} → {0,1,2}. If π(0) = 1 then the occurrence is inside single quotes; if π(0) = 2 then it is inside double quotes; and if π(0) = 0 then it is not inside quotes at all. So, to determine whether an occurrence of ‘$x’ should be substituted we need only check whether or not π(0) = 1.
The element of 2* does, however, contain information that is irrelevant to us. For example, the strings
$x ''$x ""$x "''"$x
(and so forth) are all equivalent for our purposes, since the quotational action is all fully resolved before the occurrence of ‘$x’ has been reached.
On the other hand, we cannot go all the way to elements of S_3, for these do not contain enough information. For example, the occurences of ‘$x’ in the strings
$x '"'"'"$x"'"'"'
have the same quotational effect – the identity element of S_3 – but after one round of evaluation this is no longer the case: the second one has an additional "' preceding the substituted value of $x, which has a non-trivial quotational effect (0 2 1).
Therefore a suitable quotient is to ignore paired quotes, i.e. to take the quotient monoid 〈 a, b | a^2 = 0, b^2 = 0 〉 – where the generators a and b represent the characters ' and " respectively. This quotient monoid is in fact a group: the infinite dihedral group D_∞.
Our “quotational effect” homomorphism 2* → S_3 factors through this quotient, so we have 2* → D_∞ → S_3.
Therefore a suitable representation for our strings is as multisets of elements of D_∞, which we can more conveniently think of as elements of the group ring of D_∞ (over the integers, say).
Since D_∞ is the group of isometries of the integers, we may represent an element of D_∞ as a pair (t, r), where t ∈ ℤ and r ∈ {+1, -1}. The action of such a pair on the integers is z ↦ r(z + t): “t” stands for “translate”, and “r” for “reflect”. Our generators a and b will be represented by (0, -1) and (-1, -1), i.e. z ↦ -z and z ↦ 1 - z, respectively.
Composition is: (t1, r1) ; (t2, r2) = (t1 + r1 × t2, r1 × r2).
Now we need only work out how to compute, for each element of D_∞:
* which element of D_∞ it becomes after evaluation; and * whether the occurrences of ‘$x’ it represents should be substituted.
It is not too hard to see that (t, r) reduces to (⌈t/3⌉, r'), where r' depends only on r and the value of t modulo 3. In fact, reducing t modulo 3 is essentially the “quotational effect” homomorphism, so we can also decide whether or not to substitute these occurrences of ‘$x’ from the values of r and (t mod 3). The mapping from (r, t mod 3) to (r', substitute?) is:
(0, +1) ↦ (+1, True) # () (1, +1) ↦ (-1, False) # (0 1 2) (2, +1) ↦ (-1, True) # (0 2 1) (0, -1) ↦ (+1, False) # (0 1) (1, -1) ↦ (-1, True) # (1 2) (2, -1) ↦ (+1, True) # (0 2)
where I have also annotated each line with the relevant quotational effect.
All of this means that the following Python (3) program should print out the values of the sequence:
import math
TABLE = { (0, +1): (+1, True), # () (1, +1): (-1, False), # (0 1 2) (2, +1): (-1, True), # (0 2 1) (0, -1): (+1, False), # (0 1) (1, -1): (-1, True), # (1 2) (2, -1): (+1, True) # (0 2) }
def compose(tr1, tr2): (t1, r1), (t2, r2) = tr1, tr2 return (t1 + r1*t2, r1*r2)
def subst(x, y): z = {} for ((t0, r0), n0) in x.items(): # Let tr1 be the dequoted version of (t0, r0) t1 = -math.ceil(t0 / 3) r1, should_substitute = TABLE[t0 % 3, r0] tr1 = (t1, r1)
# and substitute where appropriate if should_substitute: for (tr2, n2) in y.items(): tr3 = compose(tr1, tr2) z[tr3] = z.get(tr3, 0) + n0 * n2 else: z[tr1] = z.get(tr1, 0) + n0
return z
x = { (-1, +1): 1, (0, +1): 1, (+1, +1): 1 } print(sum(x.values())) for i in range(10): x = subst(x, x) print(sum(x.values()))
Indeed, running the program produces:
3 7 37 973 642493 274981436065 50075673362453978752897 1660424958340272612902157434339071057416705025
1828659082532127294015555219377679316426731045207698280944194119017937814697416523736342529
2221932973262746587938621327316508263261099068744811444411319257981535885894143217671769171584514785091039842436855683166325319643148964213893272271303784306333684832769323249729537
3284840218479775743047790632317572154909424991433212164298865481805700811352338269615571535863546774083036854200912305419781334801792798527519528263346227635678885261969168464305471249372299734845553556695985956938868825596778725419448920773764852977163215319470541619936785213643936937876887597557533802625700859018364222540571399561867801071781407682811002881
where the last line is the answer to the puzzle, and matches what Tomas found with a different method.
Cheers, Robin _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --