A338643 Cycle lengths arising from interpreting sequence prefixes as graph node offsets.

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

Offset: 1

Author

Matthew Malone, Apr 21 2021

Keywords

• nonn

Examples

			Start with a(1) = 1. Treat a(1) = 1 as a node pointing 1 space ahead which, wrapping around the end of the length-1 prefix, points to itself. This graph has a cycle length of 1, so a(2) = 1.
Now a(1..2) = [1, 1]. a(1) = 1 points 1 space ahead to a(2) and a(2) = 1 points 1 space ahead and wraps around to a(1), completing a cycle of length 2 so a(3) = 2.
Skipping ahead a bit, a(1..5) = [1, 1, 2, 2, 3]. In this prefix, a(1) = 1 points to a(2) = 1, which points to a(3) = 2, which points to a(5) = 3, which wraps around and points to a(3), for a cycle length of 2, so a(6) = 2.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..50000
• Rémy Sigrist, C program for A338643

Programs

C

See Links section.

Kotlin

fun graph_sequence(terms: Int): List {
    val a = mutableListOf(1)
    repeat(terms-1) { a += a.loopLength() }
    return a
}
fun List.loopLength(): Int {
    val visitedIndices = mutableMapOf()
    var idx = 0
    var counter = 0
    while (idx !in visitedIndices) {
        visitedIndices[idx] = counter++
        idx = (idx + this[idx]) % this.size
    }
    return counter - (visitedIndices[idx] ?: 0)
}