Monday, June 20, 2016

Meta recurrences

In my freshman year at college, my roommate Joe introduced me to the book "Gödel, Escher, Bach: an Eternal Golden Braid" by Douglas Hofstadter that I really enjoyed reading.  In this book, Hofstadter considers sequences whose recurrence relation is such that the arguments themselves depend on the terms of the sequence.  For instance, the classical Fibonacci sequence is defined by f(n) = f(n-1) + f(n-2), with f(1) =  f(2) = 1.  Hofstadter considered a meta Fibonacci sequence defined by q(1) = q(2) = 1, and q(n) = q(n-q(n-1)) + q(n-q(n-2)).  Not much is known about this sequence, except that it behaves wildly.  It is not even known whether the sequence is well defined!
Several variants of meta Fibonacci sequences have been analyzed in Refs. [1-4].

For some simpler meta recurrences, much more can be said about them. For instance Golomb showed that sequences satisfying the recursion a(n) = a(n - a(n-1)) is eventually periodic when it is well-defined. He also showed several meta recurrences with explicit solutions, such as a(n) = a(a(n)).
In particular, he showed that the recursion a(n) = a(n-a(n-1)) + 1 with a(1) = 1 has a simple solution described by the sequence 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ....

Next we show that this last recursion can be generalized as follows. For an integer k, define the meta recurrence a(n) = a(n-a(n-k))+k with initial conditions a(i) = i for i = 1,...,k.  This recurrence has a simple solution and it can be constructed starting with km copies of k(m+1), followed by km+1, km+2, ..., k(m+1), as m varies from 0, 1, 2, ... It is straightforward to verify that this construction satisfies the recurrence relation. Thus for each k the sequence corresponding to the meta recurrence is well defined, every positive integer is in the sequence, and every integer not a proper multiple of k appears once. If t is a multiple of k, then t appears t-k+1 times.

The cases of k=2 and k=3 are shown in OEIS sequences A193358 and A274213 respectively.

For k = 4, the sequence is: 1, 2, 3, 4, 8, 8, 8, 8, 5, 6, 7, 8, 12, 12, 12, 12, 12, 12, 12, 12, 9, 10, 11, 12, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 13, 14, 15, 16, ....

References
[1] S.M Tanny "A well-behaved cousin of the Hofstadter sequence," Discrete Math., 105 (1992), pp. 227–239.
[2] Callaghan, Joseph, John J. Chew III, and Stephen M. Tanny. "On the behavior of a family of meta-Fibonacci sequences." SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824.
[3] B. Balamohan, A. Kuznetsov and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
[4] C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12.

Continued fraction expansion of the square root of n

Results from Galois imply that the continued fraction expansion of $\sqrt{n}$ is of the form $[a_0; \overline{a_1,a_2,\cdots, a_2, a_1, 2a_0}]$ (see also Ref.[1], page 469).

In OEIS sequences A031710, A031712, A031713, A031749 and several other sequences, the least number among the periodic part of the continued fraction expansion is considered, i.e what is $\delta(n) \triangleq \min (a_1,a_2,\cdots, a_2, a_1, 2a_0)$?

If  $t$ is an integer that divides $2k$, then it is straightforward to verify that the continued fraction expansion of $\sqrt{(km)^2+tm}$ for $m \geq 1$ is equal to $[km; \overline{\frac{2k}{t}, 2km}]$.  This implies the following result:

If $r$ is even, then $\delta((\frac{rm}{2})^2+m) = r$ for all $m\geq 1$.
If $r$ is odd, then $\delta((rm)^2+2m) = r$ for all $m\geq 1$.

References:
[1] Charles Smith, A Treatise on Algebra, Fifth Edition, Macmillan and Co., 1896.