A218616 The infinite trunk of beanstalk (A179016) with reversed subsections.

0, 1, 3, 7, 4, 15, 11, 8, 31, 26, 23, 19, 16, 63, 57, 53, 49, 46, 42, 39, 35, 32, 127, 120, 116, 112, 109, 104, 101, 97, 94, 89, 85, 81, 78, 74, 71, 67, 64, 255, 247, 240, 236, 231, 225, 221, 215, 209, 205, 200, 197, 193, 190, 184, 180, 176, 173, 168, 165, 161

Offset

0,3

Comments

This can be viewed as an irregular table: after the initial zero on row 0, start each row n with (2^n)-1 and subtract repeatedly the number of 1-bits to get successive terms, until the number that has already been listed (which is always (2^(n-1))-1) is encountered, which is not listed second time, but instead, the current row is finished and the next row starts with (2^(n+1))-1, with the same process repeated.

This contains the terms in the infinite trunk of beanstalk (A179016) listed in partially reversed manner: after the initial zero each subsequence lists A213709(n) successive terms from A179016, descending from (2^n)-1 downwards, usually down to 2^(n-1) (conjectured to indeed be a power of 2 in each case, apart from 2 itself missing from the beginning of the sequence).

Currently A179016 and many of the derived sequences are much easier and somewhat faster to compute with the help of this sequence, especially if the program computes any other required values incrementally in the same loop.

Links

Antti Karttunen, Rows 0..16, flattened

Formula

a(0)=0, a(1)=1, and for n > 1, if n = A213710(A213711(n)-1) then a(n) = (2^A213711(n)) - 1, and in other cases, a(n) = A011371(a(n-1)).

Alternatively: For n < 4, a(n) = (2^n)-1, and for n >= 4, a(n) = A004755(A004755(A011371(a(n-1)))) if A011371(a(n-1))+1 is power of 2, otherwise just A011371(a(n-1)).

Example

After zero, we start with (2^1)-1 = 1, subtract A000120(1)=1 from it, resulting 1-1=0 (which is of the form (2^0)-1, thus not listed second time), instead, start the next row with (2^2)-1 = 3, subtract A000120(3)=2 from it, resulting 3-2=1, which has been already encountered, thus start the next row with (2^3)-1 = 7, subtract A000120(7)=3 from it, resulting 7-3=4, which is listed after 7, then 4-A000120(4)=4-1=3, which is of the form (2^k)-1 and already encountered, thus start the next row with (2^4)-1 = 15, etc. This results an irregular table which begins as:
0; 1; 3; 7, 4; 15, 11, 8; 31, 26, 23, 19, 16; 63, 57, ...
After zero, each row n is A213709(n-1) elements long.

Prog

(Scheme with memoization macro definec):
(definec (A218616 n) (cond ((< n 2) n) ((= (A213710 (-1+ (A213711 n))) n) (- (expt 2 (A213711 n)) 1)) (else (A011371 (A218616 (-1+ n))))))
;; Somewhat simpler recursive definition added Nov 11 2012, which do not require so many auxiliary functions:
(definec (A218616 n) (cond ((< n 4) (-1+ (expt 2 n))) ((A011371 (A218616 (-1+ n))) => (lambda (next) (if (pow2? (1+ next)) (A004755 (A004755 next)) next)))))
(define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1))))) ;; A004198 is bitwise AND

Crossrefs

a(n) = A179016(A218602(n)). The rows are the initial portions of every (2^n)-1:th row in A218254.

Sequence in context: A112305 A231396 A231463 * A323173 A324184 A114691

Adjacent sequences: A218613 A218614 A218615 * A218617 A218618 A218619

Keyword

nonn,tabf

Author

Antti Karttunen, Nov 10 2012

Status

approved