Step by Step solution about How to resolve the algorithm Minimum positive multiple in base 10 using only 0 and 1 step by step in the Kotlin programming language

Overview: This Kotlin program computes and prints values of A004290, a mathematical sequence defined as the smallest positive integer (r) such that (r - 10^m \equiv 0) (modulo (n)), where (m) is a positive integer. The sequence starts from (n = 2).

Test Cases: The program covers a range of test cases, including numbers from 1 to 10, 95 to 105, and several specific numbers (297, 576, etc.).

Function getA004290: This function takes an integer (n) and computes the corresponding value of A004290.

• Base Case: If (n = 1), it returns 1.
• Matrix Construction: It constructs an array, arr, where arr[i][j] represents the value of A004290 for (n) and (m = i + 1) at the (j)th value of (10^m).
• Matrix Filling: It fills the matrix row-by-row, starting with row 0, where arr[0][0] = 1 and arr[0][1] = 1.
  • Subsequent rows are filled based on the previous row, using a recursive pattern.
• Looping for (m): It iterates through positive integer values of (m) until it finds a row in the matrix where the value at (10^m) matches the value at (0).
• R Calculation: It calculates the value of (r) based on the found (m), starting from (10^m) and adjusting it with the smaller values of (10^j) where the corresponding matrix values are 0.
• Adjustment for (k): It adjusts (k) to ensure that (r - 10^m \equiv 0) (modulo (n)).
• Final Adjustment: If (k) is equal to 1, it increments (r) by 1.
• Return: It returns the computed value of (r).

Helper Functions:

• mod(m, n): Computes the modular arithmetic operation (m \equiv n \pmod{n}) for BigInteger objects.
• testCases: Provides a list of test cases for various values of (n).

Usage: The program runs a loop over the test cases, printing the computed values of A004290 and the factorization (A004290(n) = n * (A004290(n) / n)) for each test case.

import java.math.BigInteger

fun main() {
    for (n in testCases) {
        val result = getA004290(n)
        println("A004290($n) = $result = $n * ${result / n.toBigInteger()}")
    }
}

private val testCases: List<Int>
    get() {
        val testCases: MutableList<Int> = ArrayList()
        for (i in 1..10) {
            testCases.add(i)
        }
        for (i in 95..105) {
            testCases.add(i)
        }
        for (i in intArrayOf(297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878)) {
            testCases.add(i)
        }
        return testCases
    }

private fun getA004290(n: Int): BigInteger {
    if (n == 1) {
        return BigInteger.ONE
    }
    val arr = Array(n) { IntArray(n) }
    for (i in 2 until n) {
        arr[0][i] = 0
    }
    arr[0][0] = 1
    arr[0][1] = 1
    var m = 0
    val ten = BigInteger.TEN
    val nBi = n.toBigInteger()
    while (true) {
        m++
        if (arr[m - 1][mod(-ten.pow(m), nBi).toInt()] == 1) {
            break
        }
        arr[m][0] = 1
        for (k in 1 until n) {
            arr[m][k] = arr[m - 1][k].coerceAtLeast(arr[m - 1][mod(k.toBigInteger() - ten.pow(m), nBi).toInt()])
        }
    }
    var r = ten.pow(m)
    var k = mod(-r, nBi)
    for (j in m - 1 downTo 1) {
        if (arr[j - 1][k.toInt()] == 0) {
            r += ten.pow(j)
            k = mod(k - ten.pow(j), nBi)
        }
    }
    if (k.compareTo(BigInteger.ONE) == 0) {
        r += BigInteger.ONE
    }
    return r
}

private fun mod(m: BigInteger, n: BigInteger): BigInteger {
    var result = m.mod(n)
    if (result < BigInteger.ZERO) {
        result += n
    }
    return result
}