A338237 a(n) is the number of nodes with depth of n in a binary tree defined as: root = 1 and a child (C) of a node (N) is such that C - primepi(C) = N, or A062298(C) = N. For a node with two children, the smaller child is assigned as the left child and the bigger one as the right child. Otherwise, the child is assigned as the left child.

1, 2, 4, 6, 8, 11, 15, 18, 24, 30, 36, 46, 54, 66, 78, 94, 110, 130, 154, 179, 205, 240, 278, 317, 365, 418, 474, 539, 612, 692, 783, 885, 993, 1116, 1254, 1399, 1570, 1752, 1950, 2166, 2408, 2690, 2976, 3287, 3644, 4023, 4449, 4892, 5391, 5946, 6523, 7169

Offset

0,2

Comments

The binary tree, read from left to right in the order of increasing depth n, is the positive integer sequence A000027. The first 65 numbers in the binary tree are shown in the figure below.

1

/ \

2 3

/ \ / \

4 5 6 7

/ / / \ / \

8 9 10 11 12 13

/ / / \ / \ / /

14 15 16 17 18 19 20 21

/ \ / / / / / \ / \ /

22 23 24 25 26 27 28 29 30 31 32

/ / / / \ / / / \ / \ / / / \

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

/ / / / / \ / / / / / \ / \ / / / /

48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

Every node has either one child or two children and, thus, the binary tree has no leaves. All left children except 2 are composites and all odd primes are right children.

a(n) for n >= 1 in this sequence is the number of terms in A090532 having the value of n.

The left side of the binary tree is A025003 with a(1) = 1. A025003 is the smallest number that takes n steps to reach 1 when map A062298 is applied to an integer.

Starting from the root, there is only one path in which all nodes have two children. The path is 1 -> 3 -> 6 -> 11 -> 19 -> 29 - > 43 -> 60 -> 83, which contains 9 nodes.

Links

Michael De Vlieger, Table of n, a(n) for n = 0..150

Mathematica

c = q = 0; w = {}; Do[Set[a[i], If[PrimeQ[i], c++, a[i - c]]]; q++; If[a[i] == 0, AppendTo[w, q]; q = 0], {i, 2, 10^5}]; Most[w]  (* Michael De Vlieger, Nov 04 2021 *)

Prog

(Python)
from sympy import primepi
def depth(k):
    d = 0
    while k > 1:
        k -= primepi(k)
        d += 1
    return d
m = 1
for n in range (0, 101):
    a = 0
    while depth(m + a) == n:
        a += 1
    print(a)
    m += a

Crossrefs

Cf. A000027, A025003, A062298, A090532.

Sequence in context: A205727 A213609 A374263 * A039823 A284617 A079972

Adjacent sequences: A338234 A338235 A338236 * A338238 A338239 A338240

Keyword

nonn

Author

Ya-Ping Lu, Oct 17 2020

Status

approved