

A227643


Each a(n) is one more than the count of all descendant nodes in a tree constructed from all nonnegative integers, where the relation p = c + bitcount(c) defines the edges between parent (p) and child (c) nodes. Function bitcount(c) is the count of binary 1's in c (A000120).


10



1, 1, 2, 3, 1, 5, 1, 6, 2, 3, 7, 4, 8, 1, 13, 1, 2, 16, 1, 18, 2, 1, 21, 1, 2, 22, 3, 2, 23, 4, 1, 26, 1, 6, 2, 7, 29, 1, 37, 1, 2, 38, 3, 2, 39, 4, 1, 42, 1, 5, 3, 1, 48, 4, 1, 50, 1, 5, 2, 2, 51, 6, 3, 1, 54, 55, 7, 59, 8, 2, 68, 1, 3, 69, 4, 2, 70, 5, 1, 73, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Each a(n) = 1 + the count of nodes in the finite subtree defined by the edge relation parent = child + A000120(child). In other words, one more than the count of n's descendants, by which we mean the whole transitive closure of all children emanating from the parent at n. The subtree is finite because successive descendant values get smaller and approach zero.


LINKS

Andres M. Torres, Table of n, a(n) for n = 0..9999
Andres M. Torres, Blitz3D Basic code for computing this sequence
Index entries for Colombian or self numbers and related sequences


FORMULA

a(0)=1; and for n>0, if A228085(n)=0 then a(n)=1; if A228085(n)=1 then a(n)=1+a(A228086(n)); if A228085(n)=2 then a(n)=1+a(A228086(n))+a(A228087(n)); otherwise (when A228085(n)>2) cannot be computed with this formula, which works only up to n=128.  Antti Karttunen, Aug 16 2013
a(0)=1; and for n>0, a(n) = 1+sum_{i=A228086(n)..A228087(n)} [A092391(i) = n]*a(i). (Here [...] denotes the Iverson bracket, resulting 1 when i+A000120(i) = n and 0 otherwise. This formula works with all n.)  Antti Karttunen, Aug 16 2013


EXAMPLE

0 has no children distinct from itself (we only have A092391(0)=0), so we define a(0) = (0+1) = 1,
1 has no children (it is one of the terms of A010061), so a(1) = (0+1) = 1,
4 and 6 are also members of A010061, so both a(4) and a(6) = (0+1) = 1,
7 has 1,2,3,4 and 5 among its descendants (as A092391(5)=7, A092391(3)=A092391(4)=5, A092391(2)=3, A092391(1)=2), so a(7) = (5+1) = 6,
8 has 6 as a child value, so a(8) = (1+1) = 2,
9 has 6 and 8 as descendants, so a(9) = (2+1) = 3,
10 has {1,2,3,4,5,7} so a(10) = (6+1) = 7.


PROG

(Scheme)
;; A deficient definition which works only up to n=128:
(definec (A227643deficient n) (cond ((zero? n) 1) ((zero? (A228085 n)) 1) ((= 1 (A228085 n)) (+ 1 (A227643deficient (A228086 n)))) ((= 2 (A228085 n)) (+ 1 (A227643deficient (A228086 n)) (A227643deficient (A228087 n)))) (else (error "Not yet implemented for cases where n has more than two immediate children!"))))
;; Another definition that works for all n, but is somewhat slower:
(definec (A227643full n) (cond ((zero? n) 1) (else (+ 1 (add (lambda (i) (if (= (A092391 i) n) (A227643full i) 0)) (A228086 n) (A228087 n))))))
;; Auxiliary function add implements sum_{i=lowlim..uplim} intfun(i)
(define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))
;; by Antti Karttunen, Aug 16 2013, macro definec can be found in his IntSeqlibrary.


CROSSREFS

Cf. A010061 (gives the positions of ones), A000120, A092391, A228082, A228083, A228085, A227359, A227361, A227408.
Cf. also A213727 for a descendant counts for a similar tree defined by the edge relation parent = child  A000120(child).
Sequence in context: A140706 A200068 A139764 * A249386 A089026 A080305
Adjacent sequences: A227640 A227641 A227642 * A227644 A227645 A227646


KEYWORD

nonn,base


AUTHOR

Andres M. Torres, Jul 18 2013


STATUS

approved



