Step by Step solution about How to resolve the algorithm Fusc sequence step by step in the Kotlin programming language

Let's start by looking at the fusc function, which takes a positive integer n and returns an IntArray of length n. This function generates the Fusc sequence, a sequence of numbers where each number is derived from the previous ones. The sequence starts with 0, and each subsequent number is calculated as follows:

1. If the index of the number is even, it is equal to the number at half the index.
2. If the index of the number is odd, it is equal to the sum of the numbers at the index immediately before and after it, divided by 2.

Here's a breakdown of the fusc function:

fun fusc(n: Int): IntArray {
   if (n <= 0) return intArrayOf()
   if (n == 1) return intArrayOf(0)
   val res = IntArray(n)
   res[1] = 1
   for (i in 2 until n) {
       if (i % 2 == 0) {
           res[i] = res[i / 2]
       } else {
           res[i] = res[(i - 1) / 2] + res[(i + 1) / 2]
       }
   }
   return res
}

The fuscMaxLen function takes an integer n and returns a list of pairs. Each pair consists of an index and the corresponding Fusc number with a length greater than any previous Fusc number. The function calculates the Fusc sequence up to n, stores the results in an array, and iterates through the array to find the numbers with a length greater than any previous number.

fun fuscMaxLen(n: Int): List<Pair<Int, Int>> {
   var maxLen = -1
   var maxFusc = -1
   val f = fusc(n)
   val res = mutableListOf<Pair<Int, Int>>()
   for (i in 0 until n) {
       if (f[i] <= maxFusc) continue // avoid string conversion
       maxFusc = f[i]
       val len = f[i].toString().length
       if (len > maxLen) {
           res.add(Pair(i, f[i]))
           maxLen = len
       }
   }
   return res
}

Finally, the main function showcases the fusc and fuscMaxLen functions. It outputs the first 61 Fusc numbers and prints a list of pairs indicating the index and Fusc number where the length of the number exceeds the length of any previous Fusc number.

Here's the output of the program for the first 20 million Fusc numbers:

The first 61 fusc numbers are:
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26]

The fusc numbers whose length > any previous fusc number length are:
1000   (index       999)
1,000,000   (index   999,999)
100,000,000   (index  99,999,999)
10,000,000,000   (index 9,999,999,999)

// Version 1.3.21

fun fusc(n: Int): IntArray {
    if (n <= 0) return intArrayOf()
    if (n == 1) return intArrayOf(0)
    val res = IntArray(n)
    res[1] = 1
    for (i in 2 until n) {
        if (i % 2 == 0) {
            res[i] = res[i / 2]
        } else {
            res[i] = res[(i - 1) / 2] + res[(i + 1) / 2]
        }
    }
    return res
}

fun fuscMaxLen(n: Int): List<Pair<Int, Int>> {
    var maxLen = -1
    var maxFusc = -1
    val f = fusc(n)
    val res = mutableListOf<Pair<Int, Int>>()
    for (i in 0 until n) {
        if (f[i] <= maxFusc) continue // avoid string conversion
        maxFusc = f[i]
        val len = f[i].toString().length
        if (len > maxLen) {
            res.add(Pair(i, f[i]))
            maxLen = len
        }
    }
    return res
}

fun main() {
    println("The first 61 fusc numbers are:")
    println(fusc(61).asList())
    println("\nThe fusc numbers whose length > any previous fusc number length are:")
    val res = fuscMaxLen(20_000_000)  // examine first 20 million numbers say
    for (r in res) {
        System.out.printf("%,7d (index %,10d)\n", r.second, r.first)
    }
}