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

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.

Links

Antti Karttunen, Table of n, a(n) for n = 0..8191

Index entries for sequences related to binary expansion of n

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

Example

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

Prog

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

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.

Sequence in context: A256464 A111681 A073122 * A084410 A338073 A080067

Adjacent sequences: A277017 A277018 A277019 * A277021 A277022 A277023

Keyword

nonn,base

Author

Antti Karttunen, Oct 07 2016

Status

approved