A287729 The c-fusc function c(n) = a(n): a(1)=1, a(2n) = s(n), a(2n+1) = s(n)+s(n+1), where s(n) = A287730(n).

1, 0, 1, 1, 2, 1, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 3, 2, 3, 1, 2, 1, 1, 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 5, 4, 7, 3

Offset: 1

Author

I. V. Serov, May 30 2017

Keywords

• nonn
• look

Comments

Define a sequence chf(n) of Christoffel words over an alphabet {-,+}:

chf(1) = '-',

chf(2*n+0) = negate(chf(n)),

chf(2*n+1) = negate(concatenate(chf(n),chf(n+1))).

Then the length of the chf(n) word is fusc(n) = A002487(n), the number of '-'-signs in the chf(n) word is c-fusc(n) = a(n) (the current sequence) and the number of '+'-signs in the chf(n) word is s-fusc(n) = A287730(n). See examples below.

Examples

			A000027(n) chf(n) A070939(n) A002487(n)    a(n)    A287730(n)
                                fusc       c-fusc     s-fusc
01         '-'       1          1          1          0
02         '+'       2          1          0          1
03         '+-'      2          2          1          1
04         '-'       3          1          1          0
05         '--+'     3          3          2          1
06         '-+'      3          2          1          1
07         '-++'     3          3          1          2
08         '+'       4          1          0          1
09         '+++-'    4          4          1          3
10         '++-'     4          3          1          2
11         '++-+-'   4          5          2          3
12         '+-'      4          2          1          1
13         '+-+--'   4          5          3          2
14         '+--'     4          3          2          1
15         '+---'    4          4          3          1
16         '-'       5          1          1          0
17         '----+'   5          5          4          1
		

Links

• I. V. Serov (terms 1..1025) & Antti Karttunen, Table of n, a(n) for n = 1..8192
• Index entries for sequences related to Stern's sequences

Crossrefs

Cf. A002487, A007814, A037227, A070939, A287730, A255738, A053644.

Cf. mutual recurrence pair A000360, A284556 and also A213369.

Programs

Python

from sympy.core.cache import cacheit
@cacheit
def c(n): return 1 if n==1 else s(n//2) if n%2==0 else s((n - 1)//2) + s((n + 1)//2)
@cacheit
def s(n): return 0 if n==1 else c(n//2) if n%2==0 else c((n - 1)//2) + c((n + 1)//2)
print([c(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 08 2017

Scheme

(definec (A287729 n) (cond ((= 1 n) n) ((even? n) (A287730 (/ n 2))) (else (+ (A287730 (/ (- n 1) 2)) (A287730 (/ (+ n 1) 2))))))
;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization - Antti Karttunen, Jun 01 2017

Formula

The mutual diatomic recurrence pair c(n) (this sequence) and s(n) (A287730) are defined by c(1)=1, s(1)=0, c(2n) = s(n), c(2n+1) = s(n)+s(n+1), s(2n) = c(n), s(2n+1) = c(n)+c(n+1).

a(n) + A287730(n) = A002487(n). [c-fusc(n) + s-fusc(n) = fusc(n).]

gcd(a(n), A287730(n)) = gcd(a(n), A002487(n)) = 1.

Let k(n) = A037227(n) = 1 + 2*A007814(n) = 1 + 2*floor(A002487(n-1)/A002487(n)) for n > 1.

Let d(n) = 2*A255738(n)*(-1)^A070939(n) = 2*(n==2^(A070939(n)-1)+1)*(-1)^A070939(n) = 2*(n==A053644(n)+1)*(-1)^A070939(n) = 2*(A002487(n-1)==1)*(-1)^A070939(n) for n > 1;

then a(n) = k(n-1)*a(n-1) - a(n-2) + d(n) for n > 2 with a(1) = 1, a(2) = 0.

From Yosu Yurramendi, Apr 09 2019: (Start)

For m >= 0, m even, 0 <= k < 2^m, a(2^m+k) = A002487(2^m-k).

For m >= 0, m odd, 0 <= k < 2^m, a(2^m+k) = A002487(k).

(End)