login
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).
10

%I #90 Jul 27 2024 09:40:10

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

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

%U 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

%N 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).

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

%C chf(1) = '-',

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

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

%C 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.

%H I. V. Serov (terms 1..1025) & Antti Karttunen, <a href="/A287729/b287729.txt">Table of n, a(n) for n = 1..8192</a>

%H <a href="/index/St#Stern">Index entries for sequences related to Stern's sequences</a>

%F 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).

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

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

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

%F 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;

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

%F From _Yosu Yurramendi_, Apr 09 2019: (Start)

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

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

%F (End)

%e A000027(n) chf(n) A070939(n) A002487(n) a(n) A287730(n)

%e fusc c-fusc s-fusc

%e 01 '-' 1 1 1 0

%e 02 '+' 2 1 0 1

%e 03 '+-' 2 2 1 1

%e 04 '-' 3 1 1 0

%e 05 '--+' 3 3 2 1

%e 06 '-+' 3 2 1 1

%e 07 '-++' 3 3 1 2

%e 08 '+' 4 1 0 1

%e 09 '+++-' 4 4 1 3

%e 10 '++-' 4 3 1 2

%e 11 '++-+-' 4 5 2 3

%e 12 '+-' 4 2 1 1

%e 13 '+-+--' 4 5 3 2

%e 14 '+--' 4 3 2 1

%e 15 '+---' 4 4 3 1

%e 16 '-' 5 1 1 0

%e 17 '----+' 5 5 4 1

%o (Scheme) (definec (A287729 n) (cond ((= 1 n) n) ((even? n) (A287730 (/ n 2))) (else (+ (A287730 (/ (- n 1) 2)) (A287730 (/ (+ n 1) 2))))))

%o ;; An implementation of memoization-macro definec can be found for example in: http://oeis.org/wiki/Memoization - _Antti Karttunen_, Jun 01 2017

%o (Python)

%o from sympy.core.cache import cacheit

%o @cacheit

%o 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)

%o @cacheit

%o 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)

%o print([c(n) for n in range(1, 101)]) # _Indranil Ghosh_, Jun 08 2017

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

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

%K nonn,look

%O 1,5

%A _I. V. Serov_, May 30 2017