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