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,5

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.

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

Formula

The mutual diatomic recurrence pair c(n) (A287729) and s(n) (A288730) 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)

Example

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

Prog

(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
(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

Crossrefs

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

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

Sequence in context: A025906 A213369 A020944 * A367582 A025897 A029421

Adjacent sequences: A287726 A287727 A287728 * A287730 A287731 A287732

Keyword

nonn,look

Author

I. V. Serov, May 30 2017

Status

approved