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

%I

%S 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,

%T 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,

%U 6,3,1,54,55,7,59,8,2,68,1,3,69,4,2,70,5,1,73,1

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

%C 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.

%H Andres M. Torres, <a href="/A227643/b227643.txt">Table of n, a(n) for n = 0..9999</a>

%H Andres M. Torres, <a href="/A227643/a227643.bb.txt">Blitz3D Basic code for computing this sequence</a>

%H <a href="/index/Coi#Colombian">Index entries for Colombian or self numbers and related sequences</a>

%F 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

%F 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

%e 0 has no children distinct from itself (we only have A092391(0)=0), so we define a(0) = (0+1) = 1,

%e 1 has no children (it is one of the terms of A010061), so a(1) = (0+1) = 1,

%e 4 and 6 are also members of A010061, so both a(4) and a(6) = (0+1) = 1,

%e 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,

%e 8 has 6 as a child value, so a(8) = (1+1) = 2,

%e 9 has 6 and 8 as descendants, so a(9) = (2+1) = 3,

%e 10 has {1,2,3,4,5,7} so a(10) = (6+1) = 7.

%o (Scheme)

%o ;; A deficient definition which works only up to n=128:

%o (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!"))))

%o ;; Another definition that works for all n, but is somewhat slower:

%o (definec (A227643full n) (cond ((zero? n) 1) (else (+ 1 (add (lambda (i) (if (= (A092391 i) n) (A227643full i) 0)) (A228086 n) (A228087 n))))))

%o ;; Auxiliary function add implements sum_{i=lowlim..uplim} intfun(i)

%o (define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))))))

%o ;; by _Antti Karttunen_, Aug 16 2013, macro definec can be found in his IntSeq-library.

%Y Cf. A010061 (gives the positions of ones), A000120, A092391, A228082, A228083, A228085, A227359, A227361, A227408.

%Y Cf. also A213727 for a descendant counts for a similar tree defined by the edge relation parent = child - A000120(child).

%K nonn,base

%O 0,3

%A _Andres M. Torres_, Jul 18 2013

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 August 23 11:24 EDT 2019. Contains 326222 sequences. (Running on oeis4.)