A014418 Representation of n in base of Catalan numbers (a classic greedy version).

0, 1, 10, 11, 20, 100, 101, 110, 111, 120, 200, 201, 210, 211, 1000, 1001, 1010, 1011, 1020, 1100, 1101, 1110, 1111, 1120, 1200, 1201, 1210, 1211, 2000, 2001, 2010, 2011, 2020, 2100, 2101, 2110, 2111, 2120, 2200, 2201, 2210, 2211, 10000

Offset

0,3

Comments

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)

Links

Olivier Gérard (first 1001 terms) & Antti Karttunen, Table of n, a(n) for n = 0..16796

Georg Cantor, Über die einfachen Zahlensysteme, Zeitschrift fur Mathematik und Physik, 14 (1869), 121-128.

Aviezri S. Fraenkel, Systems of numeration, The American Mathematical Monthly, Vol. 92, No. 2 (Feb., 1985), pp. 105-114.

Antti Karttunen, A few notes on A014418

Formula

From Antti Karttunen, Jun 23 2014: (Start)

a(0) = 0, a(n) = 10^(A244160(n)-1) + a(n-A000108(A244160(n))). [Here A244160 gives the index of the largest Catalan number that still fits into the sum].

a(n) = A007090(A244161(n)).

For all n, A000035(a(n)) = A000035(A244161(n)) = A244221(n).

(End)

Example

A simple weighted sum of Sum_{k} digit(k)*C(k) [where C(k) = A000108(k), and digit(1) is the rightmost digit] recovers the natural number n (which the given numeral a(n) represents) as follows:
a(11) = 201, and indeed 2*C(3) + 0*C(2) + 1*C(1) = 2*5 + 0*2 + 1*1 = 11.
a(126) = 30000, and indeed, 3*C(5) = 3*42 = 126.

Mathematica

CatalanBaseIntDs[n_] := Module[{m, i, len, dList, currDigit}, i = 1; While[n > CatalanNumber[i], i++]; m = n; len = i; dList = Table[0, {len}]; Do[currDigit = 0; While[m >= CatalanNumber[j], m = m - CatalanNumber[j]; currDigit++]; dList[[len - j + 1]] = currDigit, {j, i, 1, -1}]; If[dList[[1]] == 0, dList = Drop[dList, 1]]; FromDigits@ dList]; Array [CatalanBaseIntDs, 50, 0] (* Robert G. Wilson v, Jul 02 2014 *)

Prog

(MIT/GNU Scheme, with memoizing definec-macro from Antti Karttunen's IntSeq-library)
;; Version based on direct recurrence:
(definec (A014418 n) (if (zero? n) n (+ (expt 10 (- (A244160 n) 1)) (A014418 (- n (A000108 (A244160 n)))))))
;; The following implementation first constructs a vector/list, to which further sequences may refer to:
(define (A014418 n) (baselist-as-decimal (A014418raw n)))
(define (A014418raw n) (vector->list (A014418raw_vector n)))
(define (A014418raw_vector n) (if (zero? n) (make-vector 0) (let ((catbasevec (make-vector (A244160 n) 0))) (let loop ((n n)) (cond ((zero? n) (vector-reverse catbasevec)) (else (let ((k (A244160 n))) (vector-set! catbasevec (- k 1) (+ 1 (vector-ref catbasevec (- k 1)))) (loop (- n (A000108 k))))))))))
;; Antti Karttunen, Jun 22-23 2014
(Python)
from sympy import catalan
def a244160(n):
    if n==0: return 0
    i=1
    while True:
        if catalan(i)>n: break
        else: i+=1
    return i - 1
def a(n):
    if n==0: return 0
    x=a244160(n)
    return 10**(x - 1) + a(n - catalan(x))
print([a(n) for n in range(51)]) # Indranil Ghosh, Jun 08 2017

Crossrefs

Cf. A014420 (gives the sum of digits), A244221 (same sequence reduced modulo 2, or equally, the last digit of a(n)), A244216, A244217, A244222, A244223, A000108, A007623, A197433, A239903, A244155, A244158, A244320, A244318, A244159 (a variant), A244161 (in base-4), A014417 (analogous sequence for Fibonacci numbers).

Cf. also A033552, A176137, A161227, A161228.

Sequence in context: A102626 A306960 A178361 * A317204 A089591 A064039

Adjacent sequences: A014415 A014416 A014417 * A014419 A014420 A014421

Keyword

nonn,base,easy

Author

Olivier Gérard

Extensions

Description clarified by Antti Karttunen, Jun 22 2014

Status

approved