cp's OEIS Frontend

From Antti Karttunen, Jun 22 2014: (Start)

Also called "Greedy Catalan Base" for short.

Note: unlike A239903, this is a true base system, thus A244158(a(n)) = n holds for all n. See also A244159 for another, "less greedy" Catalan Base number system.

No digits larger than 3 will ever appear, because C(n+1)/C(n) approaches 4 from below, but never reaches it. [Where C(n) is the n-th Catalan number, A000108(n)].

3-digits cannot appear earlier than at the fifth digit-position from the right, the first example being a(126) = 30000.

The last digit is always either 0 or 1. (Cf. the sequences A244222 and A244223 which give the corresponding k for "even" and "odd" representations). No term ends as ...21.

No two "odd" terms (ending with 1) may occur consecutively.

A244217 gives the k for which a(k) starts with the digit 1, while A244216 gives the k for which a(k) starts with the digit 2 or 3.

A000108(n+1) gives the position of numeral where 1 is followed by n zeros.

A014138 gives the positions of repunits.

A197433 gives such k that a(k) = A239903(k). [Actually, such k, that the underlying strings of digits/numbers are same].

For the explanations, see the attached notes.

(End)

For n<100, this is the same result as "If n = Sum c_i 10^i then a(n) = Sum c_i (i+1)". - Henry Bottomley, Apr 20 2001

n_2 in the notation of A122618.

Left inverse of A007088 (binary numbers), cf. formula from Karttunen. - M. F. Hasler, Jun 13 2023

We write the nonnegative integers as restricted growth strings (so called by J. Arndt in his book fxtbook.pdf, p. 325) in such a way that the Catalan numbers (cf. A000108) are expressed: 1=1, 10=2, 100=5, 1000=14, etc., 10...0 (with k zeros) = the k-th Catalan number. Once the entries of a restricted-growth string grow above 9, one would need commas or parentheses, say, to separate those entries. See Dejter (2017) for the precise definition.

In the paper "A system of numeration for middle-levels", restricted growth strings (RGSs) are defined as sequences that begin with either 0 or 1, with each successive number to the right being at least zero and at most one greater than its immediate left neighbor. Moreover, apart from case a(0), the RGSs are finite integer sequences of restricted growth which always start with 1 as their first element b_1 in position 1, and from then on, each successive element b_{i+1} in the sequence is restricted to be in range [0,(b_i)+1].

This sequence gives all such finite sequences in size-wise and lexicographic order, represented as decimal numbers by concatenating the integers of such finite sequences (e.g., from [1,2,0,1] we get 1201). The 58784th such sequence is [1, 2, 3, 4, 5, 6, 7, 8, 9, 9], thus a(58784) = 1234567899, after which comes the first RGS, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], where an element larger than 9 is present, which means that the decimal system employed here is unambiguous only up to n=58784. Note that 58785 = A000108(11)-1.

Also, if one considers Stanley's interpretation (u) of Catalan numbers, "sequences of a_1, a_2, ..., a_n of integers such that a_1 = 0 and 0 <= a_{i+1} <= a_{i} + 1" (e.g., 000, 001, 010, 011, 012 for C_3), and discards their initial zero, then one has a bijective correspondence with Dejter's RGSs of one element shorter length, which in turn are in bijective correspondence with the first C_n terms of this sequence (by discarding any leading zeros), from a(0) to a(C_n - 1). From this follows that the k-th Catalan number, A000108(k) (k>0), is represented in this system as 1 followed by k-1 zeros: a(1)=1, a(2)=10, a(5)=100, a(14)=1000, etc., and also that there exist exactly A000245(k) RGSs of length k.

Note how this differs from other number representations utilizing Catalan numbers, A014418 and A244159, in that while the latter are base-systems, where a simple weighted Sum_{k} digit(k)*C(k) recovers the natural number n (which the n-th numeral of such system represents), in contrast here it is the sum of appropriate terms in Catalan's Triangle (A009766, A030237), obtained by unranking a unique instance of a certain combinatorial structure (one of the Catalan interpretations), that gives a correspondence with a unique natural number. (Cf. also A014486.)

This sequence differs from "Semigreedy Catalan Representation", A244159, for the first time at n=10, where a(10) = 120, while A244159(10) = 121. That is also the first position where A244158(a(n)) <> n.

Please see Dejter's preprint for a more formal mathematical definition and how this number system is applied in relation to Havel's Conjecture on the existence of Hamiltonian cycles in the middle-levels graphs.

a(n) is given by the concatenation (with leading zeros removed) of the terms of row n + 23714 of A370222. - Paolo Xausa, Feb 17 2024

Algorithm for constructing the sequence: Define a(0) as 0, and for larger values of n, find first the largest Catalan number which is less than or equal to n [which is A081290(n)], and the index k = A244160(n), of that Catalan number. Initialize a vector of k zeros, [0, 0, ..., 0]. Set n_remaining = n - A000108(k) and add 1 to the leftmost element of vector, so that it will become [1, 0, ..., 0]. Then check whether the previous Catalan number, C(m) = A000108(m), where m = k-1, exceeds the n_remaining, and provided that C(m) <= n_remaining, then set n_remaining = n_remaining - C(m) and increment by one the m-th element of the vector (where the 1st element is the rightmost), otherwise just decrement m by one and keep on doing the same with lesser and lesser Catalan numbers, and whenever it is possible to subtract them from n_remaining (without going less than zero), do so and increment the corresponding m-th element of the vector, as long as either n_remaining becomes zero, or after subtracting C(1) = 1 from n_remaining, it still has not reached zero. In the latter case, find again the largest Catalan number which is less than or equal to n_remaining, and start the process again. However, after a finite number of such iterations, n_remaining will finally reach zero, and the result of a(n) is then the vector of numbers constructed, concatenated together and represented as a decimal number.

This shares with "Greedy Catalan Base" (A014418) the property that a simple weighted sum of Sum_{k=1..} digit(k)*C(k) recovers the natural number n, which the given numeral string like A014418(n) or here, a(n), represents. (Here C(k) = the k-th Catalan number, A000108(k), and digit(1) = the digit in the rightmost, least significant digit position.)

In this case, A244158(a(n)) = n holds for only up to 33603, after which comes the first representation containing a "digit" larger than nine, at a(33604), where the underlying string of numbers is [1,2,3,4,5,6,7,8,9,10] but the decimal system used here can no more unambiguously represent them.

On the other hand, with the given Scheme-functions, we always get n back with: (CatBaseSumVec (A244159raw n)).

For n >= 1, A014138(n) gives the positions of repunits: 1, 11, 111, 1111, ...

The "rep-2's": 22222, 222222, 2222222, 22222222, 222222222, ..., etc., occur in positions 128, 392, 1250, 4110, 13834, ... i.e. 2*A014138(n) for n >= 5.

Replace 2^k with A000108(k+1) in binary expansion of n.

From Antti Karttunen, Jun 22 2014: (Start)

On the other hand, A244158 is similar, but replaces 10^k with A000108(k+1) in decimal expansion of n.

This sequence gives all k such that A014418(k) = A239903(k), which are precisely all nonnegative integers k whose representations in those two number systems contain no digits larger than 1. From this also follows that this is a subsequence of A244155.

(End)

In range 0 .. 58784, these are numbers k such that A244158(A239903(n)) = k. (see comments at A244157).

More terms than usual are given to distinguish the sequence from A081594, A028897 and A244158, which agree up to a(99). The last two correspond to k! replaced by 2^k resp. Catalan(k).

This is a left inverse to A007623 (factorial base representation of n): A322001(A007623(n)) = n for all n >= 0. One could imagine variants which have a(n) = 0 or a(n) = -1 if n is not a term of A007623. Restricted to the range of A007623, it is also a right inverse to A007623, at least up to the 10 digit terms, beyond which A007623 becomes non-injective.