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,3

Links

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

Rémy Sigrist, C program for A338643

Example

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.

Prog

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

Crossrefs

Sequence in context: A366686 A071647 A034883 * A051125 A321126 A342765

Adjacent sequences: A338640 A338641 A338642 * A338644 A338645 A338646

Keyword

nonn

Author

Matthew Malone, Apr 21 2021

Status

approved