A337978 -id:A337978 - cp's OEIS frontend

A338260 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 A337978(C) = N. For nodes with two children, the smaller child is assigned as the left child and the bigger one as the right child. A child of a one-child node is assigned as the left child.

1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 3, 2, 3, 3, 3, 3, 3, 3, 4, 5, 4, 5, 4, 3, 4, 5, 6, 6, 5, 5, 4, 4, 4, 6, 6, 7, 6, 7, 7, 8, 7, 7, 6, 8, 7, 8, 8, 10, 10, 9, 8, 11, 8, 9, 9, 10, 10, 10, 11, 12, 11, 12, 13, 14, 13, 14, 14, 13, 12, 11, 13, 13, 14

Offset: 0

Ya-Ping Lu, Oct 19 2020

nonn

The binary tree, read from left to right in the order of increasing depth n, is the positive integer sequence A000027. The first 66 numbers 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  (66)
All right children are composite numbers and all prime numbers are left children.
a(n) in this sequence is the number of terms with value of n in A337979.

Cf. A000027, A062298, A095117, A337978, A337979.

from sympy import primepi
def depth(k):
    d = 0
    while k > 1:
        k += primepi(k)
        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

A337979 Define a map f(n):= n-> n + pi(n) - pi(n + pi(n)), where pi(n) is the prime count of n (n>=1). a(n) is the number of steps for n to reach 1 under repeated iteration of f.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 14, 15, 15, 16, 16, 17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 28, 29, 29

Offset: 1

Ya-Ping Lu, Oct 05 2020

nonn

For any integer n > 1, pi(n + pi(n)) > pi(n) according to Lu and Deng (see Links). Thus, n + pi(n) - pi(n + pi(n)) < n, which means n is reduced by at least 1 every time map f is applied, eventually reaching 1 under repeated iteration of f.

It seems that the sequence contains all nonnegative integers.

			a(1) = 0 because f^0(1) = 1;
a(2) = 1 because f(2) = 2 + pi(2) - pi(2 + pi(2)) = 1;
a(4) = 3 because f^3(4) = f^2(f(4)) = f^2(3) = f(f(3)) = f(2) = 1.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Ya-Ping Lu and Shu-Fang Deng, An upper bound for the prime gap, arXiv:2007.15282 [math.GM], 2020.

Cf. A000720, A025003, A062298, A095117, A337978.

a:= proc(n) option remember; `if`(n=1, 0, 1+a((
      pi-> n+pi(n)-pi(n+pi(n)))(numtheory[pi])))
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Oct 24 2020

f[n_] := Module[{x = n + PrimePi[n]}, x - PrimePi[x]];
a[n_] := Module[{nb = 0, m = n}, While[m != 1, m = f[m]; nb++]; nb];
Array[a, 100] (* Jean-François Alcover, Oct 24 2020, after PARI code *)

f(n) = {my(x = n + primepi(n)); x - primepi(x);} \\ A337978
a(n) = {my(nb=0); while (n != 1, n = f(n); nb++); nb;} \\ Michel Marcus, Oct 06 2020

from sympy import primepi
print(0)
n = 2
for n in range (2, 10000001):
    ct = 0
    n_l = n
    pi_l = primepi(n)
    while ct >= 0:
        n_r = n_l + pi_l
        pi_r = primepi(n_r)
        n_l = n_r - pi_r
        pi_l = primepi(n_l)
        ct += 1
        if n_l == 1:
            print(ct)
            break

f^a(n) (n) = 1, where f = A062298(A095117) and m-fold iteration of f is denoted by f^m.

A338215 a(n) = A095117(A062298(n)).

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 5, 6, 8, 9, 9, 11, 11, 12, 13, 14, 14, 16, 16, 17, 19, 20, 20, 21, 22, 24, 25, 27, 27, 28, 28, 29, 30, 32, 33, 34, 34, 35, 36, 37, 37, 39, 39, 40, 42, 43, 43, 44, 45, 46, 47, 49, 49, 50, 51, 52, 54, 55, 55, 57, 57, 58, 59, 60, 62, 63, 63, 64

Offset: 1

Ya-Ping Lu, Oct 17 2020

nonn

It can be shown that there is at least one prime number between n-pi(n) and n for n >= 3, or pi(n-1)-pi(n-pi(n)) >= 1. Since a(n)=n-pi(n)+pi(n-pi(n)) <= n-pi(n-1)+pi(n-pi(n)) <= n-1, we have a(n) < n for n > 1.

a(n)-a(n-1) = 1 - (pi(n)-pi(n-1)) + pi(n-pi(n)) - pi(n-(1+pi(n-1))), where pi(n)-pi(n-1) <= 1 and 1+pi(n-1) >= pi(n) or pi(n-(1+pi(n-1))) <= pi(n-pi(n)). Thus, a(n) - a(n-1) >= 0, meaning that this is a nondecreasing sequence.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000720, A062298, A095117, A337978.

Array[PrimePi[#] + # &[# - PrimePi[#]] &, 68] (* Michael De Vlieger, Nov 04 2020 *)

from sympy import primepi
for n in range(1, 10001):
    b = n - primepi(n)
    a = b + primepi(b)
    print(a)

a(n) = A095117(A062298(n));

a(n) = n - pi(n) + pi(n - pi(n)), where pi(n) is the prime count of n.

cp's OEIS Frontend

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

A337979 Define a map f(n):= n-> n + pi(n) - pi(n + pi(n)), where pi(n) is the prime count of n (n>=1). a(n) is the number of steps for n to reach 1 under repeated iteration of f.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A338215 a(n) = A095117(A062298(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula