login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 IntSeq-library.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 22 02:02 EDT 2019. Contains 325210 sequences. (Running on oeis4.)