# On Some Properties of the Hofstadter–Mertens Function

Authors: Pavel Trojovský
Journal: Complexity
 (2020)

---

## Abstract

Many mathematicians have been interested in the study of recursive sequences. Among them, a class of “chaotic” sequences are named “meta-Fibonacci sequences.” The main example of meta-Fibonacci sequence was introduced by Hofstadter, and it is called theQ-sequence. Recently, Alkan–Fox–Aybar and the author studied the pattern induced by the connection between the Q-sequence and other known sequences. Here, we continue this program by studying a “Mertens’ version” of the Hofstadter sequence, defined (for x>0) by x↦∑n≤xμnQn, where µ(n) is the Möbius function. In particular, as we shall see, this function encodes many interesting properties which relate prime numbers to “meta-sequences”.


---

## Body

## 1. Introduction

The set of the integer sequences, denoted byℤ∞, is in the main stream of the mathematical studies. For example, the problems associated with the set of prime numbers are central topics in mathematics and in many recent applications (including modern cryptography) are based on these sequences. Another very famous numerical sequence is the sequence of Fibonacci numbers Fnn≥0 defined by the recurrence Fn+2=Fn+Fn+1 (for n≥2), with initial values F0=0andF1=1. The Fibonacci sequence is a binary recurrence; i.e., each term is the sum of the two preceding ones. Binary means order 2, so for an order k sequence, we need to know the previous k terms (in some combinations).There are classes of sequences which are not linear (like the Fibonacci sequence). For instance, the sequenceann≥0 defined by the quadratic recurrence an+1=an2+c, with an=0 (where c is a given complex number), is a standard example of fractal sequence (connected to Mandelbrot’s set). However, besides being nonlinear, it still has order 1.Probably the first class of recursive sequences without a fixed order, was proposed, in 1979, by Hofstadter and Gödel [1]. In fact, they defined Qnn≥1 by the self-recurrence relation as follows:(1)Qn=Qn−Qn−1+Qn−Qn−2,with initial values Q1=Q2=1. The term “self-recurrence” is the key point here. Because we must first know the value of maxQn−1,Qn−2 in order to calculate the value of Qn, the prefix “meta” means that this kind of sequence transcends, in some sense (maybe because of the nonexistence of a fixed order), the usual examples (i.e., it is “beyond” the standard recurrent sequences). The first terms of Qn are(2)1,1,2,3,3,4,5,5,6,6,6,8,8,8,10,9,10,…,and the graph of Qn in the interval 1;1,500,000 is plotted in Figure 1.Figure 1
HofstadterQ-sequence for (n) from 1 to 1,500,000.At first glance, the “self-definition” ofQ(n) appears to be a very strange definition. Paradoxically, so far, we do not know even if Q(n) exists for all positive integers n (this is confirmed for n<12·109) [2]).Many mathematicians worked on conditional results related to theHofstadter sequence (i.e., Qn) under the assumption of its well definition. For example, Golomb [3] was the first to prove that limn⟶∞Qn/n=1/2, provided that this limit exists. A much weaker version of this result would be enough to ensure that the Hofstadter sequence is well defined. In fact, it suffices that Qn≤n+1, for all n≥1 (the limit says that Qn grows as n/2).By knowing the growth ofQn, namely, Qn≈n/2, Pinn [4] developed the study of generations by paying attention to the Q-graph. For him, these generations are the intervals a,b such that the partial graph x,Qx:x∈a,b contains a complete “sausages” pattern as in Figure 1.In 2017, Alkan et al. [5] made a very interesting discovery by studying the sequence Hn:=Cn−Qn(named by them as Hofstadter chaotic heart sequence, see its “heart fractal-like structure” in Figure 2), where C(n) is the Hofstadter–Conway $10,000 sequence is defined by the following recurrence:(3)Cn=CCn−1+Cn−Cn−1,with initial values C1=C2=1 (in contrast with Qn, and it was proved that this sequence is well defined on ℤ>0).Furthermore, we recall theMöbius functionμn which is defined by(4)μn=1,ifn=1,−1N,ifnis a product ofNdistinct primes,0,ifNhas one or more repeated prime factors.A few values of this function are(5)1,−1,−1,0,−1,1,−1,0,0,1,−1,0,−1,1,1,0,−1,0,−1,0,….This function plays an important role in number theory and combinatorics (mainly due its unpredictable behavior). Itsaccumulation (or summation) function denoted by Mx (and called the Mertens function) is defined by Mx:=∑n≤xμn (here the sum is taken over all positive integers smaller or equal to x).Figure 2
Hn=Cn−Qn for n from 1 to 1,500,000.TheMertens function slowly grows in positive and negative directions both on the average and in peak value, oscillating in an apparently chaotic manner passing through zero when n has the following values:(6)2,39,40,58,65,93,101,145,149,150,159,160,163,164,166,214,231,….We point out the stronger relation betweenMx and some important number theoretic statements:(i)
ThePrime Number theorem (which says that πxlogx/xtends to 1 as x⟶∞) is equivalent to Mx=ox (here πx is the prime counting function, namely, the number of prime numbers belonging to 1,x)(ii)
TheRiemann Hypothesis is equivalent to Mx=Ox1/2+ε, for all ε>0 (see [6, Theorem 14.25]), where, as usual, O and o are the standard Big-O and Little-o Landau notationsRecall that, we sayfx=Ogx if there exists a positive constant C, such that fx≤Cgx for all sufficiently large x (the same meaning as f≪g and fx=ogx if limx⟶∞fx/gx=0). Also, we denote f∼g, if fx/gx tends to 1 as x⟶∞(f and g are said to be asymptotically equivalent).In the same spirit than by Alkan et al. [5], in a very recent paper, the author of [7] studied the relationship between the functions Qn and μn, by defining Bn:=Qn−nμn. In this paper, we continue this program by introducing and analyzing the accumulation function of μnQn which gives relations between meta-Fibonacci sequences, prime factorization, and random walks.Throughout the paper, we shall use the familiar notationa,b=a,a+1,…,b, for integers a<b.


## 2. Hofstadter–Mertens Function

Here, we intend to consider the behavior of the accumulation function ofμnQn, denoted by MQx, which we call Hofstadter–Mertens function and it is defined as follows.Definition 1.
LetMQx=∑n≤xμnQn, where Qn denotes the nth term of Hofstadter sequence and μ(n) is the Möbius function.
A few values of the sequence (MQ(n))n≥1 are(7)1,0,−2,−2,−5,−1,−6,−6,−6,0,−6,−6,−14,−6,4,4,−6,−6,−17,….
We note the apparently chaotic behavior ofMQx which passes through zero (i.e., MQx≤0 and MQx+1>0) when x takes the following integer values:(8)2,10,16,22,28,36,41,66,69,102,130,137,169,240,250,257,262,265,….
Also, its structure seems to be chaotic and its shape seems to be as a growing “electrocardiogram” (see Figure3).
Now, we shall split our study into four points: growth, generational structure, pseudo-periodicity, and statistical viewpoint.
In all what follows, we shall suppose thatQn is well defined and that Qn/n tends to 1/2 as n⟶∞. We shall quote this as “Hypothesis (H).”Figure 3
MQx=∑n<xμnQn for x∈1;5,000.


### 2.1. Growth

It is almost unnecessary to stress that one of the first properties to study in the direction of a better comprehension of the behavior of a “chaotic” function is its growth (for large time). In fact, the structure of such a function is strongly reflected in its growth properties. For this reason, this section will be devoted to this kind of study.By the Hypothesis (H) (in particular,Qn=On) together with the fact that μn∈0,1, we deduce that(9)MQx=Ox2.However, this upper bound can be sharpened with the aid of some analytic number theory facts. For example, we know thatMx=ox and by Hypothesis (H), we can write Qn=n/21+o1. This allows us to invoke a very useful formula due to Abel which makes an interplay between a discrete sum and an integral (continuous sum).


### 2.2. Abel’s Summation Formula

Letann be a sequence of real numbers, and define its partial sum Ax:=∑n≤xan. For a real number x>1, let f be a continuously differentiable function on 1,x. Then,(10)∑n≤xanfn=Axfx−∫1xAtf′tdt.Before applying the previous formula, observe thatMQx can be rewritten as(11)MQx=12∑n≤xnμn1+o1=12∑n≤xnμn+∑n≤xon.Note that, by the properties of Landau’s symbols,∑n≤xon=o∑n≤xn=ox2 and now, in order to obtain an estimate to ∑n≤xnμn, we are in the position to apply Abel’s Summation Formula with the choice of an:=μn and ft=t. Thus,(12)∑n≤xnμn=xMx−∫1xMtdt.By the prime number theorem, we haveMx=ox and then(13)∑n≤xnμn=ox2−∫1xotdt.Again, by the properties of Landau’s symbols, we have∫1xotdt=o∫1xtdt=ox2 and so we arrive at the following fact.Fact 1.
It holds that(14)MQx=ox2.
We remark that since the Riemann Hypothesis (RH) is equivalent toMx=Ox1/2+ε, then, by proceeding along the same lines as before, we deduce the following fact.Fact 2.
By assuming that the Riemann Hypothesis is true, then, for allɛ>0, it holds that(15)MQx=Ox3/2+ε.Remark 1.
Note that in Figure4, the bound x3/2 (red colored) seems to be very huge as compared to MQx. However, we point out that a similar feeling happens by plotting a similar graphic to Mx and x1/2. In fact, this leads to the “very probable” conjecture raised by Mertens: Mx<x, for all x>0. However, this conjecture was proved to be false (see [8]) for some (nonexplicit) counter examples of astronomical order about 101040.Figure 4
Graph ofMQn (black colored), for n from 1 to 25,000 between the bounds ±x3/2(red color dashed line).


### 2.3. Generational Structure

The growth behavior of the graphical structure ofMQn brings a complex fractal-like structure. In fact, these kinds of patterns are commonly called “generational structure” of a meta-Fibonacci sequence (for more information about these structures for other meta-Fibonacci sequences, we refer the reader to [9–11]). In our case, these “generations” are the repeated “zigzag” pattern. More precisely, with Pinn’s terminology, it is possible to partition the set of positive integers as(16)ℤ>0=∪g≥0Gg,where Gg is a finite interval of natural numbers which is known as the gthgeneration of the sequence. In our case, each generation Gg=x0g,x1gwill be in such a way that (see Figure 5)(i)
MQx0g<0(ii)
x1g=mint>x0g+1:MQt<0Figure 5
Graph ofMQx (gray colored) and the disposal of endpoints of a generation (interval generation in black color).In an extensive empirical/heuristical study (see Figure6), we were not able to find a pattern for x0g and x1g. The main reason may lie in the chaotic behavior of μn (related to random walks, for example).However, it is possible to deduce that x1g−x0g can be made arbitrarily large. That is, we have the following fact.Figure 6
MQn for n from 1 to 6000 with its first 101 “generations” separated by vertical lines.Fact 3.
For all positive integersN, there is an interval Gg with length strictly larger than N.
In the next section, we shall see that a kind of periodicity ofMQx is responsible for the veracity of this fact.
We point out that most of these findings are empirical observations, since virtually speaking, nothing has been proved rigorously about theQ-sequence, so far (as previously mentioned).


### 2.4. Pseudo-Periodicity

A functionf:ℝ⟶ℝ is said to be periodic if there exists a positive integer T such that fx+T=fx, for all x∈ℝ (in other words, the function repeats its values in regular intervals or periods). The most important examples of periodic functions are the trigonometric functions, which repeat over intervals of 2π radians. Periodic functions are used throughout science to describe oscillations, waves, and other phenomena that exhibit periodicity. Any function that is not periodic is called aperiodic.Clearly, the Hofstadter–Mertens function is aperiodic. However, we can define another kind of periodicity.Definition 2.
A functionf:ℝ⟶ℝ is said to be meta-periodic if for any positive integer T, there exist infinitely many positive values of x, such that fx+T=fx. Let T be a positive integer, and let p1<p1<,…,<pT be the first T prime numbers. We have that the congruence system(17)x≡−1modp12,x≡−2modp22,⋮x≡−TmodpT2has infinitely many solutions in x (in a residue class modulo p1p2,…,pT2), say nkk≥0, by the Chinese remainder theorem. Clearly, for a particular solution x=n0, we have that pi2n0+i and so μn0+i=0, for all i∈1,T. Thus, one has μn0=⋯=μn0+T=0. In particular, we have(18)MQnk+T=MQnk,for all k≥0. Thus, we have the following fact.Fact 4.
The Hofstadter–Mertens function is meta-periodic.
For instance, for some values ofT, we have the following:(i)
ForT=2, we have the family of solutions n≡7mod36(ii)
ForT=3, we have the family of solutions n≡547mod900(iii)
ForT=5, we have the family of solutions n≡1308247mod5336100


### 2.5. Statistical Viewpoint

Now, we wish to study the behavior ofMQx in a statistical vein. For this, our method will be based on a process that appeared in OEIS A283360 (see also its Link section) for the behavior that keeps the main characteristic of Q-sequence with deviations of noise in generations. Here, we define qn as the remainder after division of ∑k=1nMQk by n. So, for n∈1,20, qn attains the following values:(19)0,1,2,1,2,3,6,3,0,3,0,9,12,11,5,13,11,9,15,3.Now, we defineq∗n=qn+1−qn and Figure 7 is the scatter plot of MQn and q∗n for n from 1 to 10000.Figure 7
The scatter plot ofMQn (red colored) and q∗n (black colored) for n from 1 to 2,000.Figure8 shows the evaluation (in a statistical viewpoint) of the standard deviation (SD), mean (arithmetic mean), and median of values of MQn in the interval 1,m, for 2≤m≤5000.Figure 8
Standard deviation, mean, and median ofMQ(n).


## 2.1. Growth

It is almost unnecessary to stress that one of the first properties to study in the direction of a better comprehension of the behavior of a “chaotic” function is its growth (for large time). In fact, the structure of such a function is strongly reflected in its growth properties. For this reason, this section will be devoted to this kind of study.By the Hypothesis (H) (in particular,Qn=On) together with the fact that μn∈0,1, we deduce that(9)MQx=Ox2.However, this upper bound can be sharpened with the aid of some analytic number theory facts. For example, we know thatMx=ox and by Hypothesis (H), we can write Qn=n/21+o1. This allows us to invoke a very useful formula due to Abel which makes an interplay between a discrete sum and an integral (continuous sum).


## 2.2. Abel’s Summation Formula

Letann be a sequence of real numbers, and define its partial sum Ax:=∑n≤xan. For a real number x>1, let f be a continuously differentiable function on 1,x. Then,(10)∑n≤xanfn=Axfx−∫1xAtf′tdt.Before applying the previous formula, observe thatMQx can be rewritten as(11)MQx=12∑n≤xnμn1+o1=12∑n≤xnμn+∑n≤xon.Note that, by the properties of Landau’s symbols,∑n≤xon=o∑n≤xn=ox2 and now, in order to obtain an estimate to ∑n≤xnμn, we are in the position to apply Abel’s Summation Formula with the choice of an:=μn and ft=t. Thus,(12)∑n≤xnμn=xMx−∫1xMtdt.By the prime number theorem, we haveMx=ox and then(13)∑n≤xnμn=ox2−∫1xotdt.Again, by the properties of Landau’s symbols, we have∫1xotdt=o∫1xtdt=ox2 and so we arrive at the following fact.Fact 1.
It holds that(14)MQx=ox2.
We remark that since the Riemann Hypothesis (RH) is equivalent toMx=Ox1/2+ε, then, by proceeding along the same lines as before, we deduce the following fact.Fact 2.
By assuming that the Riemann Hypothesis is true, then, for allɛ>0, it holds that(15)MQx=Ox3/2+ε.Remark 1.
Note that in Figure4, the bound x3/2 (red colored) seems to be very huge as compared to MQx. However, we point out that a similar feeling happens by plotting a similar graphic to Mx and x1/2. In fact, this leads to the “very probable” conjecture raised by Mertens: Mx<x, for all x>0. However, this conjecture was proved to be false (see [8]) for some (nonexplicit) counter examples of astronomical order about 101040.Figure 4
Graph ofMQn (black colored), for n from 1 to 25,000 between the bounds ±x3/2(red color dashed line).


## 2.3. Generational Structure

The growth behavior of the graphical structure ofMQn brings a complex fractal-like structure. In fact, these kinds of patterns are commonly called “generational structure” of a meta-Fibonacci sequence (for more information about these structures for other meta-Fibonacci sequences, we refer the reader to [9–11]). In our case, these “generations” are the repeated “zigzag” pattern. More precisely, with Pinn’s terminology, it is possible to partition the set of positive integers as(16)ℤ>0=∪g≥0Gg,where Gg is a finite interval of natural numbers which is known as the gthgeneration of the sequence. In our case, each generation Gg=x0g,x1gwill be in such a way that (see Figure 5)(i)
MQx0g<0(ii)
x1g=mint>x0g+1:MQt<0Figure 5
Graph ofMQx (gray colored) and the disposal of endpoints of a generation (interval generation in black color).In an extensive empirical/heuristical study (see Figure6), we were not able to find a pattern for x0g and x1g. The main reason may lie in the chaotic behavior of μn (related to random walks, for example).However, it is possible to deduce that x1g−x0g can be made arbitrarily large. That is, we have the following fact.Figure 6
MQn for n from 1 to 6000 with its first 101 “generations” separated by vertical lines.Fact 3.
For all positive integersN, there is an interval Gg with length strictly larger than N.
In the next section, we shall see that a kind of periodicity ofMQx is responsible for the veracity of this fact.
We point out that most of these findings are empirical observations, since virtually speaking, nothing has been proved rigorously about theQ-sequence, so far (as previously mentioned).


## 2.4. Pseudo-Periodicity

A functionf:ℝ⟶ℝ is said to be periodic if there exists a positive integer T such that fx+T=fx, for all x∈ℝ (in other words, the function repeats its values in regular intervals or periods). The most important examples of periodic functions are the trigonometric functions, which repeat over intervals of 2π radians. Periodic functions are used throughout science to describe oscillations, waves, and other phenomena that exhibit periodicity. Any function that is not periodic is called aperiodic.Clearly, the Hofstadter–Mertens function is aperiodic. However, we can define another kind of periodicity.Definition 2.
A functionf:ℝ⟶ℝ is said to be meta-periodic if for any positive integer T, there exist infinitely many positive values of x, such that fx+T=fx. Let T be a positive integer, and let p1<p1<,…,<pT be the first T prime numbers. We have that the congruence system(17)x≡−1modp12,x≡−2modp22,⋮x≡−TmodpT2has infinitely many solutions in x (in a residue class modulo p1p2,…,pT2), say nkk≥0, by the Chinese remainder theorem. Clearly, for a particular solution x=n0, we have that pi2n0+i and so μn0+i=0, for all i∈1,T. Thus, one has μn0=⋯=μn0+T=0. In particular, we have(18)MQnk+T=MQnk,for all k≥0. Thus, we have the following fact.Fact 4.
The Hofstadter–Mertens function is meta-periodic.
For instance, for some values ofT, we have the following:(i)
ForT=2, we have the family of solutions n≡7mod36(ii)
ForT=3, we have the family of solutions n≡547mod900(iii)
ForT=5, we have the family of solutions n≡1308247mod5336100


## 2.5. Statistical Viewpoint

Now, we wish to study the behavior ofMQx in a statistical vein. For this, our method will be based on a process that appeared in OEIS A283360 (see also its Link section) for the behavior that keeps the main characteristic of Q-sequence with deviations of noise in generations. Here, we define qn as the remainder after division of ∑k=1nMQk by n. So, for n∈1,20, qn attains the following values:(19)0,1,2,1,2,3,6,3,0,3,0,9,12,11,5,13,11,9,15,3.Now, we defineq∗n=qn+1−qn and Figure 7 is the scatter plot of MQn and q∗n for n from 1 to 10000.Figure 7
The scatter plot ofMQn (red colored) and q∗n (black colored) for n from 1 to 2,000.Figure8 shows the evaluation (in a statistical viewpoint) of the standard deviation (SD), mean (arithmetic mean), and median of values of MQn in the interval 1,m, for 2≤m≤5000.Figure 8
Standard deviation, mean, and median ofMQ(n).


## 3. Hofstadter–Mertens Function × Riemann Zeta Function

We close this study by comparingMQx and the Riemann zeta function ζs=∑n≥11/ns (for ℜs>1). We know that ζ(s) converges for all ℜs>1 and admits an analytic continuation (via Abel Summation Formula) for ℜs≥1 except for a simple pole at s=1, with residue 1 (in fact, Riemann extended this continuation for all complex planes but s=1).The zeta function is only one example of the calledDirichlet series which, for an arithmetic function f:ℕ⟶ℝ, is defined by(20)Df,s:=∑n≥1fnns.Many properties of prime numbers are encoded by Dirichlet’s series and its Euler’s product. For example, for the Riemann zeta function, we have(21)ζs=∏p1−p−s−1,where the product is taken over all prime numbers. We know the huge importance of primes in mathematics and even in real life (as in cryptography). So, among the attempts made in this direction, we were able to provide the following fact.Fact 5.
We have that(22)∑n≥1μnQnns=1ζs∑n≥1ψnns,where(23)ψn∼−1ωn2ϕnn∏pnp.
Here, as usual,ωn denotes the number of distinct prime factors of n and φn=#k∈1,n:gcdk,n=1 is the Euler totient function.
In order to prove this fact, we recall theDirichlet convolution between two Dirichlet’s series.Definition 3.
Letf and g be arithmetic functions; then, the Dirichlet convolution of f and g, denoted by f∗g is defined by(24)f∗gn:=∏dnfdgnd.
A well-known fact is thatDf,s⋅Dg,s=Df∗g,s. Thus, let us considerfn=1 (for all n), i.e., Df,s=ζs and then,(25)DμnQn,s⋅ζs=DμnQn∗1,s=∑n≥1ψnns,where ψn=μnQn∗1n=∑dnμnQn. Since, by Hypothesis (H), Qn∼n/2, then ψn∼1/2∑dndμd. Note that(26)∑dndμd=−1ωnϕradn,where radn=∑pnp (where p is a prime) is called the radical of n (the proof of (26) follows from the fact that the left-hand side and the right-hand side, in formula (26), represent arithmetic multiplicative functions and so it is enough to compare them when n is a prime power). Now, we use ϕradn/radn=ϕn/nto conclude Fact 5.


## 4. Conclusion

In this paper, we continue the fruitful program started by Hofstadter, Golomb, Pinn, Alkan, Fox, and Aybar (among others) to study the behavior of meta-Fibonacci sequences, mainly theQ-sequence. Here, we studied the sequence MQn which is defined as the accumulation function of the product between the Q-sequence and the Möbius function (we call MQn as Hofstadter–Mertens function). The sequence MQ(n) is studied with emphasis on its chaotic behavior. We split the text into four parts. We started by growing properties of MQn and its relation with the Riemann hypothesis (here, we used some analytic tools). Then, we present some data regarding its “generational structures” together with some other facts. In the third part, we worked on the pattern repetition of MQx by showing that it satisfies a kind of “meta-periodicity.” We finish by mentioning some statistical viewpoints of the Hofstadter–Mertens function, such as its mean, median, and standard deviation (in a large scale). In the final section, we still present some theories of Dirichlet series related to μnQn which could have some theoretical interest in detection of primes or problems related to the Riemann zeta function.



---

*Source: 1816756-2020-09-15.xml*