2005年4月22日（金）

"Hofstadter Sequences" Provisional Script

（英語話者が当ページを読むとは思えませんが、オンラインウェブ翻訳サイトがどうにも信頼なりませんので、自分で英訳してみます。日本語文は下記の4月20日付の「「ホフスタッター数列群」仮稿」にあります。数学に興味のない方は、4月19日付の「LAN奮闘記、もしくは日本橋紀行」からお読みください）
We must say in advance, our consortium uses the term "Hofstadter sequences" as its original one, not in the meaning same as the public mathematical term. Please note in advance if you are willing to quote, that this article may also have some unpermitted names and easily-made terms.
"Hofstadter Sequences" are the abbreviation of "Hofstadter-type high-order recursive sequences," and are the generic term of the sequences which Douglas R. Hofstadter published in his book "Gödel, Escher, Bach: An Eternal Golden Braid" and ones which posterior mathematicians studied inspired by them. However, since this is too rough for a mathematical definition, we want to define them as the generic term of Hofstadter G-sequence, Hofstadter Q-sequence, Hofstadter-Conway 10,000-dollar sequence, and the sequences which are generated with methods similar and has properties similar to these. While even this hardly can be said to be a rigid definition, we think that we do not need to define so rigidly, since these started from non-practical concepts based on "recreational mathematics"-like interests.
To be more exact, we can define them as "infinite sequences which are generated by a finite number of initial values and a recursive relation of one formula generated in the manner where 1, the index, the term for the index generated by adding or subtracting the index and 1 finite times and all the terms generated in the same manner repeated finite times are added or subtracted finite times, and which have integer terms for all the indeces, increase generally, and be approximated roughly to curves represented with simple polynomials, or linear lines, when represented in graphs." However, it does not mean that we do not have a doubt whether the definition should include "increase generally" and "be approximated roughly to curves" as neccesary conditions, since they are "properties." Moreover, defining too exactly might exclude some sequences with interesting property which we want to include in "Hofstadter sequences."
Let us show an example. We originally defined them as "be approximated roughly to straight lines" because Hofstadter G-sequence, Hofstadter Q-sequence and Hofstadter-Conway 10,000-dollar sequence can all be approximated to straight lines. However, while the sequence containing one 1, two 2's, three 3's, ... and n n's in order can be generated in Hofstadter-like manner, it is graphed not in a line but of course in a parabola. We consider the definition above as only a tentative presentation since discovering a new sequence can renew the exact definition like this.
Now, survey the sequences individually.
Hofstadter G-sequence is the sequence defined by G[1]=1 and G[n]=n-G[G[n-1]] (n<=2), and the first few terms are 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, .... It has a similar example, Hofstadter H-sequence, which is defined by H[1]=1 and H[n]=n-H[H[H[n-1]]] (n<=2), and whose first few terms are 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, .... We can make the nests of the recursion deeper. These sequences have common properties that every integer appears once or twice in order and that the deeper the recursion is, the larger the value of the term is for a fixed index.
Hofstadter Q-sequence is the sequence defined by Q[1]=Q[2]=1 and Q[n]=Q[n-Q[n-1]]+Q[n-Q[n-2]] (n<=3), and the first few terms are 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, .... While it basically travels around n/2, it shows a complicated behavior that it oscillates up and down intensely and converges occationally, which brings us an emotion as if we had a glimpse of a chaos.
Various sequences generated by similar recurrence relations have been studied, and most of them show complicated behaviors like Q-sequence. However, "Allenby sequence" studied by R. Allenby, which is defined by A[1]=A[2]=1 and A[n]=A[n-A[n-1]]+A[n-1-A[n-2]] (n<=3), shows an ordered behavior like Hofstadter-Conway 10,000-dollar sequence below-mentioned where every integer appears continuously t+1 times in order where n=(2^t)r (r is an odd number) except that the initial 1 appears twice. As might have been expected, when A[n-1] is subtracted from n, it should be quite natural that A[n-2] is subtracted from n-1.
Hofstadter-Conway 10,000-dollar sequence is the sequence defined by a[1]=a[2]=1 and a[n]=a[a[n-1]]+a[n-a[n-1]] (n<=3), and the first few terms are 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, .... It has some properties that :
(1) Every term is equal to, or 1 larger than its previous term (every integer appears in order)
(2) a[2^t] is equal to 2^(t-1), and a[n] is within n/2 to n even for all other n
(3) a[2n] is equal to, or smaller than 2a[n]
(4) a[n]/n converges to 1/2 as n -> infinity
(5) A[2^t+r] is equal to A[2^(t+1)-r] for 0<=r<=2^t where A[n]=2a[n]-n,
and particularly marvelous one that when A[n] is graphed curves similar to blancmanger function (or Takagi fractal function) appear continuously while getting larger gradually.
Our consortium is making an especially concentrated study of this Hofstadter-Conway 10,000-dollar sequence and sequences similar to it. Our pre-open site also took up 10,000-dollar sequence and proved the property (1) above. Here we try to investigate some sequences generalized from 10,000-dollar sequence.
Firstly, we try to generalize the initial values. While 10,000-dollar sequence has two 1's as its initial terms, terms to any number will do. So let a[1]=a[2]=a[3]=1 and a[n]=a[a[n-1]]+a[n-a[n-1]] (n<=4), and we will get a sequence with terms 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 7, 7, 8, .... Our consortium proposes calling this sequence "Conway sequence" after the name of the veteran mathematician J. Conway who offered a prize problem of 10,000 dollars on 10,000-dollar sequence to throw the mathematicians' society into an uproar.
Secondly, we try to generalize the index in the recurrence relation. While 10,000-dollar sequence has a formula with n-1 as an index, we can subtract from n a number larger than 1. However, subtracting too large a number may make the index 0 or less to cause calculation impossible, so we need to add to the number of initial terms as many. Let a[1]=a[2]=a[3]=1 and a[n]=a[a[n-2]]+a[n-a[n-2]] (n<=4), and we will get a sequence with terms 1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 7, 7, 8, .... Our consortium proposes calling this sequence "Mallows sequence" after the name of the mathematician C. L. Mallows who failed (?) to get the prize of 10,000 dollars.
Lastly, we try to generalize the depth of recursion of the recurrence relation like G-sequence and H-sequence. We can cover the first term of the formula a[a[n-1]] and a[n-1] in the second term a[n-a[n-1]] with a[...] same times. So let a[1]=a[2]=1 and a[n]=a[a[a[n-1]]]+a[n-a[a[n-1]]] (n<=3), and we will get a sequence with terms 1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 10, 11, 12, .... Our consortium proposes calling this sequence "Grytczuk sequence" after the name of the rising Polish mathematician J. Grytczuk who published a paper on a study of similar sequences including this last year 2004.
These three sorts of generalization, not only alone, can also be applied at the same time. So we consider a set of sequences generated by the recurrence relations :
H{c,m,g}[n]=1 (1<=n<=c+m)
H{c,m,g}[n]=H{c,m,g}[H^(g){c,m,g}[n-m]]+H{c,m,g}[n-H^(g){c,m,g}[n-m]] (n>=c+m+1)
(where H^(0){c,m,g}[n]=n and H^(t){c,m,g}[n]=H{c,m,g}[H^(t-1){c,m,g}[n]])
for four variables c, m, g and n with values of natural numbers. When c=m=g=1, the sequence H{1,1,1}[n] is 10,000-dollar sequence. Moreover, Conway sequence is the example where c=2 and m=g=1, Mallows sequence where m=2 and c=g=1, and Grytczuk sequence where g=2 and c=m=1. We call the variables c, m and g "Conway factor," "Mallows factor" and "Grytczuk factor" respectively.
Our consortium calls this set of sequences "Hofstadter's drawbridge sequences." We named so after the situation where a line linking the head of the sequence to the term indicated by the first term and a line linking the tail of the sequence to the term indicated by the second term contact and separate as n increases (However, except the case of 10,000-dollar sequence, they are almost always together or apart).
According to this naming rule, A[n] of the "property (5)" above could be named "Hofstadter's blancmanger sequences." However, while its recurrence relation can be achieved (A[n]=A[((n-1)+A[n-1])/2]+A[((n+1)-A[n-1])/2]), it is not included in "Hofstadter sequences" since A[n] can be 0 (the recurrence relation does not satisfy the condition either). "Hofstadter's blancmanger sequences" will be exactly defined below.
Hofstadter's drawbridge sequences satisfy the property (1) of 10,000-dollar sequence for all c, m and g. This can be easily proven by a method similar to 10,000-dollar sequence. Moreover, this indicates that drawbridge sequences satisfy a part of the neccesary conditions in order to be included in "Hofstadter sequences."
Drawbridge sequences H{c,m,g}[n] have a general tendency that for fixed n the term gets smaller as c or m increases and gets larger as g increases. The properties like (2), (3) and (4) above differ with the values of c, m and g. The symmetry like the property (5) does not stand up except that c=m=g=1.
Here we define a set of sequences in order to investigate the properties above. The famous Fibonacci sequence (exactly, the sequences containing Fibonacci numbers) is defined by F[1]=F[2]=1 and F[n]=F[n-1]+F[n-2] (n>=3). We generalize the second term of the recurrence relation, and introduce "generalized Fibonacci sequences" defined by L[t,n]=1 (1<=n<=t) and L[t,n]=L[t,n-1]+L[t,n-t] (n>=t+1). L[t,n]=2^(n-1) when t=1, Fibonacci sequence when t=2, and when t=3 it contains 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, ....
Drawbridge sequences have a property when m=1 that H{c,1,g}[L[cg,n]]=L[cg,n-c] for all the term of a generalized Fibonacci sequence L[cg,n]. From this, it is expected that H[c,1,g] is a root of an equation x=(1-x^g)^c (0<x<1) where H[c,m,g]=lim[n->infinity] H{c,m,g}[n]/n, the limit of the term divided by the index (I am not very good at estimation of convergence of sequences because I did not take my math classes seriously at my university ages). The limit H[1,1,1] for the case of 10,000-dollar sequence H{1,1,1}[n] is 1/2, the root of x=1-x.
On the other hand, when m>=2, they do not have an easy property such as above. This can be thought to have a factor that the whole sequence cannot be regulated because, while the circumstance of H{c,m,g}[n] is directly reflected to H{c,m,g}[n+1] when m=1, the reflection delays when m>=2. The limit H[c,m,g] may exist even when m>=2, but while H{c,m+1,g}[n] is almost always smaller than H{c,m,g}[n], H[c,m+1,g] is not always smaller than H[c,m,g]. As for Mallows sequence, H[1,2,1] is expected to be 1/2 same as H[1,1,1] since H{1,2,1}[n]/n>1/2 roughly for r around 1.25<r<1.75 and H{1,2,1}[n]/n<1/2 roughly for r around 1.75<r<2.5 where n=(2^t)r.
"Hofstadter's blancmanger sequences" can be defined, using this limit H[c,m,g], as B{c,m,g}[n]=H{c,m,g}[n]-nH[c,m,g]. A[n] above is equal to 2B{1,1,1}[n]. Blancmanger sequences are not included in "Hofstadter sequences" since they generally have terms in not natural number nor integer, but they are expected to make it easy to investigate the properties of "Hofstadter sequences" since their graphs travel around 0. The graph of B{1,1,1}[n] draws curves similar to blancmanger function, and for general c, m and g they may draw individually specific beautiful curves.
The ultimate aim of the study of "Hofstadter sequences" is to discover a method by which we can directly find the term for the specific index n. The study can be said to be successful if we discover an algorithm by which we can find it faster than we calculate it in order from n=1.
G-sequence can be represented as G[n]=floor[p(n+1)] where floor[x] is the maximum integer which does not exceed x and p=(-1+root[5])/2 (the reciprocal of the golden ratio). However, it may need further investigation whether the algorithm finding the fractional part of a irrational number root[5] enough exactly for G[n] is really faster than calculating G[n] in order from n=1. Moreover, H-sequence etc. can also be represented in a manner floor[q(n+1)] roughly, but some adjustment may be needed according to the value of n.
On the other hand, the situation is hopeless over Q-sequence. We observate it for small n and might expect a property that it generally stands up (for example, Q[3*2^t]=2^(t+1) for 0<=t<=8), but it hardly stands up when n gets larger. It is so difficult problem which has been annoying the mathematicians all over the world that it is whispered that they could win the Fields prize, a Nobel prize for mathematics, if they could solve a property of Q-sequence.
As for 10,000-dollar sequence, we can find it very fast with a foothold of a[2^t] since it has a property a[2^t]=2^(t-1) and the method is also known by which we find how many times a specific value appears in the sequence, while it is not so simple as Allenby sequence. As for generic drawbridge sequences, we can take a method similar to 10,000-dollar sequence when m=1, but we are still studying in the case of m>=2.
"Hofstadter sequences" are categorized into "recreational mathematics," so its practicality is not considered from the first, but we dare think that they may be able to be applied to drawing softwares because these sequences can be considered as integer appoximation of fractal. Fractal is a property of figures which are not smooth everywhere and whose parts are not simpler than the whole, studied as a reconsideration to the traditional mathematics which studied only simple figures. Some softwares draw out graphics with a natural feel applying fractal. However, finding fractal rigidly needs calculation of the fractional parts again and again to cause computers a heavy burden. If we could find an integer recursive sequence with a behavior similar to the fractal which we want to draw, it is expected that the amount of calculation would be remarkably smaller and that drawing also would be faster. However, now we are not even on the start line of such a study.
Are you interested in "Hofstadter sequences," and do you also want to study them by yourself? There is a method of drawing a tree diagram where the values of the indeces and the terms are linked as a useful mean for investigating "Hofstadter sequences" (Hofstadter calls the tree "G-map" from the fact that he used it for investigating G-sequence). It will be also good making a program calculating the sequences with JavaScript with which we can make an interactive program easily on the browser.
（翻訳ソフトよりは正確であることは確かなのですが、ネイティブにも意味が通るのかということは、ちょっと自信がありません。ミスがあったら、おいおい直していきます）