A341742 Nodes read by depth in a binary tree defined as: Root = 1; an even node N has a left child N + 1 if N + 1 is not a prime, and an odd node N has a left child sqrt(N + 2) if sqrt(N + 2) is a prime; the right child of a node N is 2*N.

1, 2, 4, 8, 9, 16, 18, 32, 36, 33, 64, 72, 66, 65, 128, 144, 132, 130, 129, 256, 145, 288, 133, 264, 260, 258, 512, 290, 289, 576, 266, 265, 528, 261, 520, 259, 516, 513, 1024, 291, 580, 578, 1152, 267, 532, 530, 529, 1056, 522, 1040, 518, 517, 1032, 1026

Offset: 1

Author

Ya-Ping Lu, Feb 18 2021

Keywords

• nonn

Comments

Let d be the depth of a node N in the binary tree and f be the map of A340801. The d-th iteration of map A340801 on N gives 1, or f^d(N) = 1.

If Conjectures 1 and 2 made in A340801 hold, the sequence contains all positive integers and each integer appears once in the sequence.

The first odd prime does not appear until d reaches 30 and the first five odd primes appearing in the sequence are:

n a(n) d

------- ----- --

140735 4099 30

151872 1543 31

1574120 8689 36

1841645 2917 36

2111465 32771 36

The first two odd primes less than 100 appear in the binary tree are 17 at d = 4426 and 71 at d = 4421.

Examples

			The binary tree for depths up to 9 is given below.
  1
   \
    2
     \
      4
       \
        8
     /    \
   9       16
    \        \
    18        32
     \       /  \
     36    33    64
      \     \    / \
      72    66  65  128
       \     \   \   / \
      144   132 130 129 256
      / \   / \   \   \   \
   145 288 133 264 260 258 512
		

Crossrefs

Cf. A340801, A006577, A340008, A339991, A340419.

Programs

Python

from sympy import isprime
from math import sqrt
def children(N):
    C = []
    if N%2 == 0:
        if isprime(N + 1) == 0: C.append(N+1)
    else:
        p1 = sqrt(N + 2.0); p2 = int(p1 + 0.5)
        if p2**2 == N + 2 and isprime(p2) == 1: C.append(p2)
    C.append(2*N)
    return C
L_last = [1]; print(L_last)
for d in range(1, 18):
    L_1 = []
    for i in range(0, len(L_last)):
        C_i = children(L_last[i])
        for j in range(0, len(C_i)): L_1.append(C_i[j])
    print(L_1); L_last = L_1