login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A323665 a(n) is the number of vertices in the binary tree the root of which is assigned the value n and built recursively by the rule: write node's value as (2^c)*(2k+1); if c>0, create a left child with value c; if k>0, create a right child with value k. 2
1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 5, 5, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 4, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 6, 7, 7 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Mirroring (left <--> right) the tree corresponding to n and computing back a number gives rise to sequence A323710. Swapping the left and right subtrees of the root of the tree corresponding to n and computing back a number gives rise to sequence A117303.

LINKS

Luc Rousseau, Table of n, a(n) for n = 1..10000

EXAMPLE

100 = (2^2)*(2*12+1) and recursively, 2 = (2^1), 12 = (2^2)*(2*1+1). We then have the following binary tree representation:

     100                                         o

     / \                                        / \

    2  12                                      o   o

   /   / \              or more simply        /   / \

  1   2   1                                  o   o   o

     /                                          /

    1                                          o

7 vertices, so a(100) = 7.

MAPLE

a:= proc(n) option remember; `if`(n=0, 0, (j->

      1+a(j)+a((n/2^j-1)/2))(padic[ordp](n, 2)))

    end:

seq(a(n), n=1..100);  # Alois P. Heinz, Jan 23 2019

MATHEMATICA

nEdges[n_] :=

If[n == 0, 0,

  Module[{c, xx, k}, c = IntegerExponent[n, 2]; xx = n/2^c;

   k = (xx - 1)/2;

   Boole[c != 0]*(1 + nEdges[c]) + Boole[k != 0]*(1 + nEdges[k])]]

a[n_] := nEdges[n] + 1

Table[a[n], {n, 1, 87}]

PROG

(SWI-Prolog)

v(M, V) :-

        R is mod(M, 2),

        R = 1 -> (V = 0) ; (N is M / 2, v(N, W), V is 1 + W).

a(N, S, R) :- N = 0, !, S = x, R = 0.

a(N, S, R) :-

        v(N, C),

        X is (N / 2^C),

        K is (X - 1) / 2,

        a(C, SC, RC),

        a(K, SK, RK),

        S = o(SC, SK),

        R is 1 + RC + RK.

main :- forall(between(1, 87, N), (a(N, _, A), maplist(write, [A, ', ']))).

CROSSREFS

Cf. A117303, A323710.

Sequence in context: A130260 A276621 A111393 * A062537 A279596 A224458

Adjacent sequences:  A323662 A323663 A323664 * A323666 A323667 A323668

KEYWORD

nonn,look

AUTHOR

Luc Rousseau, Jan 23 2019

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 6 23:01 EDT 2020. Contains 335484 sequences. (Running on oeis4.)