Одной из функций приложения, над которым я работал, было показывать набор случайных цифр. Стало интересно получится ли найти правило по которому можно соотнести каждый такой набор с целым числом. Так я смогу получать число из ГПСЧ, а все итоговые строки будут получаться с одинаковой долей вероятности.

Первое, что должно прийти в голову - это преобразовывать число в строку без изменений. То есть, например, 123 в "123". Сразу бросится в глаза, что нужно как-то разделять "42" и "042", и подобные. Поэтому вариант без изменений числа не может подойти.

Для демо версии приложения я использовал алгоритм с использованием условного оператора. Допустим ожидается что итоговая строка будет не больше двух символов. Значит двузначные числа можно преобразовывать в строку без изменений. Ведь 42 преобразуется в "42" и никак иначе. А если генерировать числа не от 0, а от -10, то можно вручную разделить их на числа с нулём в начале и без.
Пример кода на Kotlin:

/**
 * -10 ->  "0"
 *  -9 ->  "1"
 *  -1 ->  "9"
 *   0 -> "00"
 *   9 -> "09"
 *  99 -> "99"
 */
fun getFormattedString(number: Int): String {
    require(number in -10..99)
    return if (number < 0) {
        (number + 10).toString()
    } else {
        "%02d".format(number)
    }
}

То есть, например, 42 преобразуется в "42", 9 в "09", а -9 в "1".

Очевидно такая реализация слишком неповоротлива для модернизации под решение задачи в общем случае. Во время экстраполяции этой идеи на числа больших разрядов я обратил внимание на закономерность - строки состоящие из нулей соотносятся с числом которое из себя представляет сумму десяток в степени.

10^n + 10^(n-1) + ... + 10^2 + 10^1

То есть, например для трёхзначных чисел будет справедливо что -100 преобразится в "00", или -110 в "0". Эти частные случаи суммы ряда можно вычислить и использовать как точку опоры вместо строгих условий вроде number < 0. Это должно работать с разными длинами строк, а значит и разными разрядами чисел.

Я взял число, которое находится между суммами ряда. Прибавил к нему сумму ряда и получил число которое я ожидаю увидеть в строке. Теперь не надо выделять часть чисел в положительную сторону, одно правило должно работать в общем случае. А степень ряда равна длине итоговой строки (слева добавляются нули если не хватает).

Допустим ожидаемая длина равна 3. Тогда будет справедливо следующее:

-1110 -> "  0" -> -1110 + 10^3 + 10^2 + 10^1
-1106 -> "  4" -> -1106 + 10^3 + 10^2 + 10^1
-1100 -> " 00" -> -1100 + 10^3 + 10^2
-1058 -> " 42" -> -1058 + 10^3 + 10^2
-1000 -> "000" -> -1000 + 10^3
 -958 -> "042" ->  -958 + 10^3
   -1 -> "999" ->    -1 + 10^3

Как я говорил ранее мы имеем частный случай суммы ряда вроде a * r + a * r^2 + ... + a * r^(n-1) + a * r^n. Где коэффициент a равен 1, r равен 10, а n равен заданной длине искомой строки. Допустим у нас есть функция getSumOfSeries, которая вычисляет такую сумму. При ближайшем рассмотрении видно что дело придётся иметь не просто с суммами рядов, а с разностью сумм рядов. То есть, например 1100 - это результат разности суммы ряда где n равно 3 и суммы ряда где n равно 1. А разность 1110 - 110 (тут n равны 3 и 2 соответственно), полученная по такому же принципу, будет равна 1000.

1100 = 1110 -  10 = (10^3 + 10^2 + 10^1) -         10^1
1000 = 1110 - 110 = (10^3 + 10^2 + 10^1) - (10^2 + 10^1)

Так я придумал функцию, которая в цикле проверяет к какой разности сумм рядов относится сгенерированное число. И формирует из него строку, используя полученные в результате поиска значения коэффициентов:

fun getFormattedString(number: Int, length: Int): String {
    val sum = getSumOfSeries(n = length)
    for (i in 1..length) {
        if (number < getSumOfSeries(n = i) - sum) {
            val formatted = number + sum - getSumOfSeries(n = i - 1)
            return "%${length}s".format("%0${i}d".format(formatted.toInt()))
        }
    }
    error("Impossible!")
}

Сразу в голову не пришло что раз мы работаем с разностью сумм, то ту самую разность можно получать сразу. Но сейчас мы вычисляем сумму ряда в одном месте, а затем получаем ещё в двух местах результат разности с другими суммами рядов. Ведь мы знаем формулу по которой вычисляется сумма ряда. Теперь можно представить ряд a*r^n + a*r^(n - 1) + ... + a*r^(m + 1) + a*r^m как разность суммы ряда со степенью n и ряда со степенью m.

gSOS = getSumOfSeries
10^n + 10^(n-1) + ... + 10^(m+1) + 10^m + 10^(m-1) + ... + 10^1 = gSOS(n)
                                   |                       |
                                   10^m + 10^(m-1) + ... + 10^1 = gSOS(m)
                                   |
10^n + 10^(n-1) + ... + 10^(m+1)   |                            = gSOS(n) - gSOS(m)

Функция вычисляющая частный случай суммы ряда от 1 до n теперь вычисляет общий случай суммы ряда от n до m:

fun getSumOfSeries(
    a: Int = 1,
    r: Double = 10.0,
    m: Int = 0,
    n: Int,
): Double {
    require(m >= 0)
    require(n >= m)
    return r * a * (r.pow(m) - r.pow(n)) / (1.0 - r)
}

А функцию формирующую строку можно сократить избавившись от получения разности сумм вручную:

fun getFormattedString(number: Int, length: Int): String {
    for (i in 1..length) {
        if (number < -getSumOfSeries(n = length, m = i)) {
            val formatted = number + getSumOfSeries(n = length, m = i - 1)
            return "%${length}s".format("%0${i}d".format(formatted.toInt()))
        }
    }
    error("Impossible!")
}

Ещё лучше, но для вычисления всё ещё используются управляющие конструкции вроде цикла и условия. Я обратил внимание на то, что коэффициент, который мы ищем в цикле, есть степень суммы ряда, на которую мы опираемся.

10^n + 10^(n-1) + ... + 10^2 + 10^1 = (1 - 10^n) / (1 - 10) = Sn
n = log10(1 - Sn * (1 - 10) / 10)

Зная сумму ряда, мы можем вычислить степень ряда:

fun getPowerOfSeries(
    a: Int = 1,
    r: Double = 10.0,
    sum: Double
): Double {
    return kotlin.math.log(1 - sum * (1.0 - r) / (a * r), r)
}

Если рассматривать числа между суммами ряда как значения суммы некоторого ряда десяток в степенях, то, вычисляя степень такого ряда, мы будем получать нецелое число как раз между теми которые нам нужны.

-1110 -> "  0" -> m = log10(1 - (1110 - 1110) * (-9) / 10) = 0
-1106 -> "  4" -> m = log10(1 - (1110 - 1106) * (-9) / 10) = 0
-1100 -> " 00" -> m = log10(1 - (1110 - 1100) * (-9) / 10) = 1
-1058 -> " 42" -> m = log10(1 - (1110 - 1058) * (-9) / 10) = 1
-1000 -> "000" -> m = log10(1 - (1110 - 1000) * (-9) / 10) = 2
 -958 -> "042" -> m = log10(1 - (1110 -  958) * (-9) / 10) = 2
   -1 -> "999" -> m = log10(1 - (1110 -    1) * (-9) / 10) = 2

Используя только целую часть мы будем получать как раз необходимый нам коэффициент:

fun getFormattedString(number: Int, length: Int): String {
    val m = getPowerOfSeries(sum = getSumOfSeries(n = length) + number).toInt()
    val formatted = getSumOfGeometricSeries(n = length, m = m) + number
    return "%${length}s".format("%0${m + 1}d".format(formatted.toInt()))
}

Теперь мы избавились от управляющих конструкций. Но теперь кажется что мы получаем случайные числа отрицательными только по историческим причинам. Оказалось что с положительными числами предложенный алгоритм работает ещё лучше. Получать степень ряда можно просто из заданного числа без предварительной обработки (ранее мы складывали его с суммой ряда). И если вычесть этого числа сумму ряда по полученной степени то мы получим искомое число, которое остаётся отформатировать по той же полученной степени.

gSOS = getSumOfSeries
gPOS = getPowerOfSeries
   0 ->    0 - gSOS(gPOS(   0)) ->    0 - gSOS(0) ->    0 -   0 -> "  0"
   4 ->    4 - gSOS(gPOS(   4)) ->    4 - gSOS(0) ->    4 -   0 -> "  4"
  10 ->   10 - gSOS(gPOS(  10)) ->   10 - gSOS(1) ->   10 -  10 -> " 00"
  58 ->   58 - gSOS(gPOS(  58)) ->   58 - gSOS(1) ->   58 -  10 -> " 42"
 110 ->  110 - gSOS(gPOS( 110)) ->  110 - gSOS(2) ->  110 - 110 -> "000"
 168 ->  168 - gSOS(gPOS( 168)) ->  168 - gSOS(2) ->  168 - 110 -> "042"
1109 -> 1109 - gSOS(gPOS(1109)) -> 1109 - gSOS(1) -> 1109 - 110 -> "999"

Главное не забыть проверить данные на входе. Заданное число должно быть в диапазоне от 0 (включительно) до суммы ряда по степени равной длине целевой строки (не включительно). Так же можно ограничить ожидаемую длину от 1 до 9. Таким образом заданное число ожидается минимум 0, а максимум 1_111_111_109. Что впритык влезает в положительный диапазон знаковых целочисленных 32х разрядных (для длины 10 уже не влезет).

fun Int.formatted(length: Int): String {
    require(length in 1..9)
    require(this in 0 until getSumOfSeries(n = length).toInt())
    val n = getPowerOfSeries(sum = toDouble()).toInt()
    val formatted = this - getSumOfSeries(n = n)
    return "%${length}s".format("%0${n + 1}d".format(formatted.toInt()))
}

Строгих требований к приложению не было, как и конкретных сроков сдачи. Смог позволить себе подойти творчески к решению банальных задач. Заодно вспомнил школьный курс алгебры. Теперь на каждое целое число в определённом диапазоне, которые берутся из ГПСЧ с равной долей вероятности, можно получить все необходимые комбинации цифр. Итоговая функция удовлетворяет поставленным требованиям.