Как придумал себе (проблему) задачу и вспомнил школьный курс алгебры

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

Первое, что должно прийти в голову — это преобразовывать число в строку без изменений. То есть, например, 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())) } 

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