A277020 Unary-binary representation of Stern polynomials: a(n) = A156552(A260443(n)).

0, 1, 2, 5, 4, 13, 10, 21, 8, 45, 26, 93, 20, 109, 42, 85, 16, 173, 90, 477, 52, 957, 186, 733, 40, 749, 218, 1501, 84, 877, 170, 341, 32, 685, 346, 3549, 180, 12221, 954, 7133, 104, 14269, 1914, 49021, 372, 28605, 1466, 5853, 80, 5869, 1498, 30685, 436, 61373, 3002, 23517, 168, 12013, 1754, 24029, 340, 7021, 682, 1365

Offset: 0

Author

Antti Karttunen, Oct 07 2016

Keywords

• nonn
• base

Comments

Sequence encodes Stern polynomials (see A125184, A260443) with "unary-binary method" where any nonzero coefficient c > 0 is encoded as a run of c 1-bits, separated from neighboring 1-runs by exactly one zero (this follows because A260442 is a subsequence of A073491). See the examples.

Terms which are not multiples of 4 form a subset of A003754, or in other words, each term is 2^k * {a term from a certain subsequence of A247648}, which subsequence remains to be determined.

Examples

			n    Stern polynomial       Encoded as              a(n)
                            "unary-binary" number   (-> decimal)
----------------------------------------------------------------
0    B_0(x) = 0                     "0"               0
1    B_1(x) = 1                     "1"               1
2    B_2(x) = x                    "10"               2
3    B_3(x) = x + 1               "101"               5
4    B_4(x) = x^2                 "100"               4
5    B_5(x) = 2x + 1             "1101"              13
6    B_6(x) = x^2 + x            "1010"              10
7    B_7(x) = x^2 + x + 1       "10101"              21
8    B_8(x) = x^3                "1000"               8
9    B_9(x) = x^2 + 2x + 1     "101101"              45
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..8191
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A087808 (a left inverse), A156552, A260443, A277189 (odd bisection).

Cf. also A000079, A000120, A000225, A002450, A002487, A003754, A073491, A247648, A260442, A277010, A277012, A276081.

Programs

Scheme

(define (A277020 n) (A156552 (A260443 n)))
;; Another implementation, more practical to run:
(define (A277020 n) (list_of_numbers_to_unary_binary_representation (A260443as_index_lists n)))
(definec (A260443as_index_lists n) (cond ((zero? n) (list)) ((= 1 n) (list 1)) ((even? n) (cons 0 (A260443as_index_lists (/ n 2)))) (else (add_two_lists (A260443as_index_lists (/ (- n 1) 2)) (A260443as_index_lists (/ (+ n 1) 2))))))
(define (add_two_lists nums1 nums2) (let ((len1 (length nums1)) (len2 (length nums2))) (cond ((< len1 len2) (add_two_lists nums2 nums1)) (else (map + nums1 (append nums2 (make-list (- len1 len2) 0)))))))
(define (list_of_numbers_to_unary_binary_representation nums) (let loop ((s 0) (nums nums) (b 1)) (cond ((null? nums) s) (else (loop (+ s (* (A000225 (car nums)) b)) (cdr nums) (* (A000079 (+ 1 (car nums))) b))))))

Formula

a(n) = A156552(A260443(n)).

Other identities. For all n >= 0:

A087808(a(n)) = n.

A000120(a(n)) = A002487(n).

a(2n) = 2*a(n).

a(2^n) = 2^n.

a(A000225(n)) = A002450(n).