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

Author

N. J. A. Sloane, Oct 10 2021

Keywords

• nonn

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.

Crossrefs

Cf. A000120, A347697.

Programs

C

See Links section.

Extensions

More terms from Rémy Sigrist, Oct 11 2021