Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

Some new Formulas for the Kolakoski Sequence A000002

Abdallah Hammam

Département de Mathématiques et Informatique, Université Moulay Ismaїl Faculté des sciences, Meknès, Morocco

Abstract: We present here two formulas for the Kolakoski sequence (Kn)n≥₁. The first one is in concern with the frequency of the letters 1 and 2 in this sequence. Our investigation seems to support the hypothesis of the Keane’s conjecture. In the second part of this paper, we give an expression of the nth term of the sequence, Kn, according to K₁,K₂,...Kp, with improving so, the former known value given by Bordellès [2].

Keywords: Kolakoski sequence, recursion, recursive formula.

Citation: Abdallah Hammam, Some new Formulas for the Kolakoski Sequence A000002. Turkish Journal of Analysis and Number Theory, 4 (3). 54-59. January 2016. doi:10.12691/tjant-4-3-1

1. Introduction

The Kolakoski sequence [13], with named so in 1965 but used for the first time in 1935 by Oldenburger [16], is the unique sequence beginning with 1 and which is invariant by the run-length encoding operation It starts as follows: 12211212212211211221211…. This sequence is also known as the Sloane’s sequence A000002 [17]. It has been investigated by many authors using different technics (see [1,3,5,4,7,20,21,22] for instance). In particular, Kimberling [12] asked many questions about this sequence. We try here to find the way to give answers to the two most known of them: The first, is asking whether the density of the letter 2 in the word defined by

has an asymptotic limit when n goes to ∞ ? and if this limit exists, is it equal to 1/2 ? This question is also known as the Keane’s conjecture [11]. Shallit [18] classified this question in the twelfth position in his list of some Open Problems in concern with the automatic sequences. No answer to this attractive question has been given until now. Chvàtal [6], used the structure of some special graphs and established that

Kupin [14], used the Gouldon-Jackson’s method and obtain

Bordellès [2], applied the Dirichlet’s pigeonhole principle and got a better bound:

In this paper, we will present a recursive formula connecting the density of 2’s with some differences between terms of even and odd indices. This formula seems to support Keane’s conjecture.

The second question we investigate here, looks for an explicit expression of the term Steinsky [23] and Fédou [9] found two equivalent recursive formulas which give according to Using an inductif argument, Bordellès [2] presented a relation between and defined by: We will try, in this paper, to improve these results by reducing the number of data we need to compute We shall use a certain smaller than Furthermore, we derive a simple expression of using this time, the integer part of the truncated rational .

2. Notation

We first introduce some definitions and notation:

Let be the input alphabet set and let be the set of all finite words over We let denote the run-length encoding operator, such that if is an element of then will be the new word containing lengths of blocs of similar digits, in the initial word As an example,

We now define the two useful primitives and in the same way than Oldenburger [16], Sing [20,21], Dekking [8], Fédou [9] and Huang [10] by:

If is an element of then (resp ) will be the unique word starting from the left by 1 (resp ), consisting of, exactly elements and satisfying the encoding condition: For instance, and As a consequence, if we let denote, for every the word then Here, is the partial sum and also the Sloane’s sequence A054353 defined by:

and as it has been used by Bordellès [2]. Therefore, the infinite Oldenburger-Kolakoski word can be seen as a fixed point of the function Shallit [19] has defined K as a fixed point of some extendable homomorphism, such as on 12, since we can write:

More generally, for every , we can extend as follows:

Table 1. How the 1’s of Wn are transformed by Δ₁⁻¹

Table 2. How the 2’s of Wn are transformed by Δ₁⁻¹

We also need to define the double sequence by :

On the other hand, for each and we associate the set of elements in such that:

for We will write in a symbolic way, what we call the index notation:

The existence of is supported by Theorem 2 below. We also define the cardinals:

As an example, we have and

In the end, let us remark that, when we integrate by applying , every letter of this word, will be transformed in a bloc whose the index of the last element is as illustrated by Table 1 and Table 2. More generally, after each integration using , each will give a bloc whose last element, in the extreme right, is .

3. A Recursive Formula for the Density of 2’s in the Kolakoski Sequence

We now begin by presenting a useful connection between , the density of 2’s in the word , and some linear combination of

Lemma 1. For every :

Proof. For the first, there are two cases: if is even, then the number of odd indices in is equal to the number of even ones. If is odd, the number of odd indices is greater than the evens since the first term has an odd index. We will refer to this equation by “the index balance sheet in ”.

We write now the same equation for :

As the elements of are created by the integration of using the operator, this balance sheet equation, will not take into account the blocs of two similar elements in since they consist of an odd and an even index and do not have any impact on the balance sheet of indices. So, only the elements created by 1’s, as illustrated by Table 1 and Table 2, similar to those used by Nilsson [15] to perform his algorithm, will be useful in the final equation. This restriction allows us to get the desired equation. To prove the third relation, We just write the “index balance sheet” for just after eliminating all the blocs whose number of elements is even.

Theorem 2. for all we have

Proof. Let be an integer ≥ 1.

We begin by making useful connections between the four sequences:

and which represent respectively, the number of 2s in the word the number of 1s, the density of 2s and the partial sum

Using the fact that We find that

which becomes as follows:

Bordellès et Al. [2], proved this equation using an induction on . We now use the index notation and get:

The proof is finally achieved, by using the index balance sheet equation for , given in Lemma 1. For the third equality, we replace by in the second equation to obtain:

If we take now a look at the second line of Table 1 and Table 2, we can see that, only blocs of single 1’s in have to be taken into account. The conclusion is then, easily derived. To prove the fourth, We replace this time, by and find:

Finally, a quick look at the third line of Table 1 and Table 2 gives the expected result.

As a conclusion, we proved that, for each we can compute and so on, only from some elements between and This possibility is the answer to the existence of the sequence

Corollary 3. For each integer n ≥ 1 fixed and i ≥ 0, we define the following sequences by:

Then, Theorem 2 allows us to write:

1.

2.

3.

4.

More generally, we can show by induction that for each

The two coefficients and take quickly changing values and signum.

On the other hand, for enough great integer i, we have

and

Hence, the sequence increases at least exponentially. Finally, as a conclusion, we can say that the answer to Keane’s conjecture, depends on the signum of the sequence If this signum is always changing, it means that the sequence has no limit or goes to zero, i.e., the frequency of 2’s goes to .

4. A New Formula for the nth Term Kn

At first, we will present a simple recursive formula, which computes from the input values, and

In the second part of this section, we will try to improve this result.

Lemma 4. For every integer

Proof. We consider the decimal numbers defined by :

for every Hence, by integration using the operator we find a new rational :

also given by

and then, using the fact that the Kolakoski-Oldenburger constant , is a fixed point of , we will have

from which we extract the digit using the integer part: [ ].

In the end, let us remark that this recursive computation of , depicted of its interesting mathematical side, takes too much time and obviously need to be improved.

Lemma 5. For every n ≥ 2, there exist two unique integers p and q, both > 0 such that:

Proof. Let be an integer and assume that for every Then, in the best case, there will exist and This is not possible since

For the second, the basics of he proof come from the following two cases: for each and then or , which gives

We will now derive a second recursive formula for using less input parameters.

Theorem 6. Let and let be the unique integer, such that

Then we have if

if and

if

Proof. For each let us remember that

Using the integration operator we obtain

and

When goes to infinity, the three series , and , converge absolutely to the same limit , namely, the Oldenburger-Kolakoski constant 0, 1221121221..... . So, by identification of the coefficients in the base, we derive the expression of , according to the value of the difference

We now try to simplify the expressions we got above.

Theorem 7. Let and let be the unique integer, such that: then,

Proof. We separate the three cases: or 2 or 3 and use Table 1 and Table 2. We find almost easily that if then and if then These two conditions can be replaced by

Finally, to include also the almost trivial case we unify all the expressions in the following unique one:

Figure 1. Signum variation of the product for different values of n

Table 3. Comparison between n,kn and kn'

5. Concluding Remarks

Our attempt to respond to the Keane’s conjecture, does not allow us to give a final answer. However, the Corollary 3 seems clearly to support this hypothesis, since, in the left-hand side of its equations, the term increases at least exponentially with while the right hand side does not and can not have a constant signum as illustrated by the graph in Figure 1. It contains a complicated linear combination of terms which are generated nearly randomly by the integration operator as seen in Corollary 3. In the future, we will focus our work, to investigate deeply this last assertion. On the other hand, to answer the question about the explicit expression of term let us begin by saying that the self-describing nature of the Oldenburger-Kolakoski sequence, makes it impossible to predict from only. What we can just do, is to give an expression of according to where p is as smaller as we can. We have shown that, we can take verifying This value is clearly smaller than, found by Steinsky [23] and presented by Bordellès [2]. We will try to improve this result by looking for simple expressions and much smaller values of like those satisfying with In this case, will be not far from as illustrated in Table 3.

Acknowledgments

The author would like to thank the referees for their careful reading of the manuscript and the fruitful suggestions they provided, and Assim for helpful discussion.

References

[1]   | J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge Univ. Press, Cambridge, 2003.
[2]   | O. Bordellès and B. Cloitre, Bounds for the Kolakoski Sequence, Journal of Integer Sequences, Vol. 14 (2011).
[3]   | S. Brlek, S. Dulucq, A. Ladouceur, and L. Vuillon, Combinatorial properties of smooth infinite words, Theor. Comp. Sci. 352 (2006), 306-317.
[4]   | K. Culik, J. Karhumäki, Iterative devices generating infinite words, Lec. Notes in Comp. Sc. 577 (1992), 531-544.
[5]   | A. Carpi, On repeated factors in C∞-words, Inf. Process. Lett. 52 (1994), 289-294.
[6]   | V. Chvàtal, Notes on the Kolakoski sequence, DIMACS Technical Report, 93-84. (1994).
[7]   | The Kolakoski Transform of words, Inf. Process. Lett. 52 (1994), 289-294.
[8]   | F. M. Dekking, What is the long range order in the Kolakoski sequence?, The Mathematics of Long–range Aperiodic Order, NATO Adv. Sci. Inst. Ser. C Maths. Phys. Sci., 489, Kluwer Acad. Publ., Dordrecht (1997), 115-125.
[9]   | J. M. Fédou and G. Fici, Some Remarks on Differentiable Sequences and Recursivity, Journal of Integer Sequences, Vol. 13 (2010).
[10]   | Y. Huang, The Complexity of Cbω-words of the form ωχω, Theoritical Computer Science, Vol. 410 (2009), 4892-4904.
[11]   | Keane and C. Series (eds.), Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press, 1991, pp. 35-70.
[12]   | C.Kimberling,http://faculty.evansville.edu/ck6/integer/index.html.
[13]   | W. Kolakoski, Problem 5304: Self Generating Runs, Amer. Math. Monthly 72 (1965), 674.
[14]   | E. J. Kupin and E. S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, arXiv:0809.2776 [math. CO] Sept 16, 2008.
[15]   | F. M. Dekking, What is the long range order in the Kolakoski sequence?, The Mathematics of Long-Range A eriodic Order, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 489, Kluwer Acad. Publ., Dordrecht (1997), 115-125.
[16]   | Rufus Oldenburger, Exponent trajectories in symbolic dynamics, Trans Amer. Math. Soc. 46 (1939), 453-466.
[17]   | N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, published electronically at http://oeis.org.
[18]   | J. Shallit, Open Problems in Automata Theory:An Idiosyncratic View, School of Computer Science.
[19]   | J. Shallit, Emerging Applications of Number Theory. Springer Verlag Coll. The IMA Volumes in Ms and its Applications (n◦ 109), (1999), 547-570.
[20]   | B. Sing, More Kolakoski sequences, Integers A14, 11B (2011).
[21]   | B. Sing, Spektrale Eigenschaften der Kolakoski-Sequenzen, Diploma thesis, Universit¨at T¨ubingen, (2002).
[22]   | R. Steacy. Structure in the Kolakoski sequence. Bull. European Assoc. Theor. Comput. Sci., No. 59, (1996), 173-182.
[23]   | B. Steinsky, A recursive formula for the Kolakoski sequence, J. Integer Seq. 9 (2006), Article 06.3.7.