A347696 Length of longest sequence of directed edges in the graph G (see Comments) that starts at node n.

0, 0, 1, 0, 2, 1, 2, 0, 3, 2, 3, 1, 4, 2, 3, 0, 5, 3, 4, 2, 5, 3, 4, 1, 6, 4, 5, 2, 6, 3, 4, 0, 7, 5, 6, 3, 7, 4, 5, 2, 8, 5, 6, 3, 7, 4, 5, 1, 9, 6, 7, 4, 8, 5, 6, 2, 9, 6, 7, 3, 8, 4, 5, 0, 10, 7, 8, 5, 9, 6, 7, 3, 10, 7, 8, 4, 9, 5, 6, 2, 11, 8, 9, 5, 10, 6

Offset

0,5

Comments

Let G be the directed graph with vertices labeled by the nonnegative integers and with an edge out of vertex n for each 0 in the binary representation of n (excluding leading zeros). If the 2^s term in n is 0, then the corresponding edge goes from vertex n to vertex n - 2^s.

Thus from vertex 12 = 1100_2 there are outgoing edges to vertex 11 = 12 - 1 and to vertex 10 = 12 - 2.

Then a(n) is the length of the longest sequence of edges starting at vertex n.

If we replace "0" by "1" in the definition, the analogous sequence is A000120. - Andrey Zabolotskiy, Oct 10 2021.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..8191

Rémy Sigrist, C program for A347696

Ravi Vakil, On the Steenrod length of real projective spaces: finding longest chains in certain directed graphs, Discrete Mathematics 204 (1999) 415-425.

Prog

(C) See Links section.

Crossrefs

Cf. A000120, A347697.

Sequence in context: A119387 A335905 A055941 * A365385 A366788 A290537

Adjacent sequences: A347693 A347694 A347695 * A347697 A347698 A347699

Keyword

nonn

Author

N. J. A. Sloane, Oct 10 2021

Extensions

More terms from Rémy Sigrist, Oct 11 2021

Status

approved