A385871 a(n) is the number of primes in the prime chain to which prime(n) belongs. Details are in the Comments.

3, 3, 3, 3, 3, 1, 1, 2, 3, 2, 1, 2, 2, 1, 3, 2, 1, 1, 1, 1, 2, 2, 3, 1, 2, 2, 2, 2, 1, 1, 1, 2, 3, 1, 3, 1, 2, 2, 2, 2, 2, 4, 1, 1, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 2, 1, 1, 3, 2

Offset: 1

Author

Tamas Sandor Nagy, Jul 11 2025

Keywords

• nonn

Comments

This sequence originates from a counting game, or process, along the sequence of prime numbers.

At a given prime, the next prime in its chain is determined as follows:

The primes are lined up, and we start counting incrementally at the prime with the value of that prime itself, walking step by step, back towards to the prime 2. At 2 we turn to forward direction without counting twice at 2, and carry on counting further. We pass our starting prime and from there on, we observe whether at some point the count will equal the prime at that count, or not.

If the count and its prime are equal, then that prime is the next in the chain; otherwise the starting prime has no next prime and its chain ends.

To put it more formally:

For prime(k), to find out whether a greater prime(k + m) is directly linked next to prime(k) in a chain, we test if the equation prime(k) + 2*(k - 1) + m = prime(k + m) is satisfied for some m integer > 0.

Each prime has at most 1 predecessor in this rule so that the steps make a chain.

If prime(n) does not chain to a next prime, and no preceding prime chains to it, then its chain consists of itself only and has length a(n) = 1.

Examples

			The counting walk from 5:
 2        3        5        7       11       13       17       19       23
 7   <-   6   <-   5
     ->   8   ->   9   ->  10   ->  11
                                     ^
                                     |
                                   Match
The counting walk from 11:
 2        3        5        7       11       13       17       19       23
15  <-   14   <-  13   <-  12  <-   11
    ->   16   ->  17   ->  18  ->   19   ->  20   ->  21   ->  22  ->   23
                                                                         ^
                                                                         |
                                                                       Match
Since 5 cannot be reached from any lesser prime, and no greater prime can be reached either from 23 by this method, 5, 11, and 23 belong to a common prime chain of length 3, allowing a(3), a(5), and a(9) terms the value of 3 each.
The counting walk from 13:
 2     3     5     7    11    13    17    19    23    29    31    37
18 <- 17 <- 16 <- 15 <- 14 <- 13
   -> 19 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 26 -> 27 -> 28 -> 29
                                                      ^
                                                      |
                                                  No match
                                            as the faster growing
                                            prime sequence here already
                                            overtook the counting sequence
                                            without reaching equal values
                                            at any second point.
.
Therefore 13 forms a chain with one solitary link only, and so a(6) = 1.
.
In another example, the primes 2, 3, and 7 are in a prime chain of length 3 because
  2 = prime(1), so k = 1
and
  prime(1) + 2*(1 - 1) + m = prime(1 + m)
  2 + 2*0 + m = prime(1 + m)
  2 + m = prime(1 + m)
Solved for m by search: m = 1
and since
  2 + 1 = prime(1 + 1)
  3 = prime(2) -> so far, 3 is linked to 2 in a prime chain.
Furthermore:
  3 = prime(2), so let now k = 2
and
  prime(2) + 2*(2 - 1) + m = prime(2 + m)
  3 + 2*1 + m = prime(2 + m)
  5 + m = prime(2 + m)
Solved for m by search: m = 2
and since
  5 + 2 = prime(2 + 2)
  7 = prime(4) -> so far, 7 is linked to 2 and 3 in a prime chain.
Checking for further members to the 2-3-7 prime chain:
  prime(4) + 2*(4 - 1) + m = prime(4 + m)
  7 + 2*3 + m = prime(4 + m)
  7 + 6 + m = prime(4 + m)
  13 + m = prime(4 + m)
No such m > 0 is found, so m and prime(4 + m) cannot exist to satisfy the equation.
The 2-3-7 prime chain has no more members, therefore they form a chain of length 3, and so the terms a(1), a(2), and a(4) each equal to 3.
The prime chains to which the first few primes belong:
   2     {2, 3, 7},
   3     {2, 3, 7},
   5     {5, 11, 23},
   7     {2, 3, 7},
  11     {5, 11, 23},
  13     {13},
  17     {17},
  19     {19, 37},
  23     {5, 11, 23},
  29     {29, 53},
  31     {31},
  37     {19, 37},
  41     {41, 73},
  43     {43},
  47     {47, 83, 137},
  53     {29, 53},
  ...
		

Links

• Sean A. Irvine, Java program (github)

Crossrefs

Cf. A000040.

Extensions

More terms from Michel Marcus, Jul 13 2025