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

0, 1, 1, 0, 1, 1, 2, 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, 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

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) = A287729(n) and the number of '+'-signs in the chf(n) word is the current sequence a(n) = s-fusc(n). See examples below.

Examples

			n         chf(n) A070939(n) A002487(n) A287729(n)    a(n)
                                fusc       c-fusc     s-fusc
1          '-'       1          1          1          0
2          '+'       2          1          0          1
3          '+-'      2          2          1          1
4          '-'       3          1          1          0
5          '--+'     3          3          2          1
6          '-+'      3          2          1          1
7          '-++'     3          3          1          2
8          '+'       4          1          0          1
9          '+++-'    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, A070939, A037227, A287729, 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([s(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 08 2017

Scheme

(definec (A287730 n) (cond ((= 1 n) 0) ((even? n) (A287729 (/ n 2))) (else (+ (A287729 (/ (- n 1) 2)) (A287729 (/ (+ n 1) 2))))))
;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization
;; Second version after the alternative formula given by the author:
(definec (A287730 n) (if (<= n 2) (- n 1) (- (* (A037227 (- n 1)) (A287730 (- n 1))) (A287730 (- n 2)) (* (if (= 1 (A002487 (- n 1))) 1 0) 2 (expt -1 (A070939 n)))))) ;; Antti Karttunen, Jun 01 2017

Formula

The mutual diatomic recurrence pair c(n) (A287729) and s(n) (this sequence) 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) + A287729(n) = A002487(n). [s-fusc(n) + c-fusc(n) = fusc(n).]

gcd(a(n), A287729(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) = 0, a(2) = 1.