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

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.

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

Example

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

Prog

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

Crossrefs

Cf. A002487, A007814, A070939, A037227, A287729, A053644.

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

Sequence in context: A331779 A243556 A048233 * A260452 A005679 A232927

Adjacent sequences: A287727 A287728 A287729 * A287731 A287732 A287733

Keyword

nonn,look

Author

I. V. Serov, May 30 2017

Status

approved