cp's OEIS Frontend

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

%I A338643 #16 Apr 23 2021 20:53:14
%S A338643 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,
%T A338643 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,
%U A338643 9,10,10,11,12,8,9,11,9,9,12,10,10,11,11,12,13
%N A338643 Cycle lengths arising from interpreting sequence prefixes as graph node offsets.
%H A338643 Rémy Sigrist, <a href="/A338643/b338643.txt">Table of n, a(n) for n = 1..50000</a>
%H A338643 Rémy Sigrist, <a href="/A338643/a338643.txt">C program for A338643</a>
%e A338643 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.
%e A338643 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.
%e A338643 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.
%o A338643 (Kotlin)
%o A338643 fun graph_sequence(terms: Int): List<Int> {
%o A338643     val a = mutableListOf(1)
%o A338643     repeat(terms-1) { a += a.loopLength() }
%o A338643     return a
%o A338643 }
%o A338643 fun List<Int>.loopLength(): Int {
%o A338643     val visitedIndices = mutableMapOf<Int,Int>()
%o A338643     var idx = 0
%o A338643     var counter = 0
%o A338643     while (idx !in visitedIndices) {
%o A338643         visitedIndices[idx] = counter++
%o A338643         idx = (idx + this[idx]) % this.size
%o A338643     }
%o A338643     return counter - (visitedIndices[idx] ?: 0)
%o A338643 }
%o A338643 (C) See Links section.
%K A338643 nonn
%O A338643 1,3
%A A338643 _Matthew Malone_, Apr 21 2021