Подсчет количества цифр в записи числа

[Alik]

Здравствуйте!
У меня такой вопрос: имеется ли общая формула для подсчета количества одинаковых цифр в записи целого числа представленного в позиционной системе счисления?
Допустим число 23412 в десятичном виде имеет две двойки, все остальные цифры встречаются один раз, тоже самое число в двоичной записи это 101101101110100, где количество единиц - 9, а количество нулей - 6.
Таким образом число переменных на выходе функции определяется числом позиций в представлении, не проблема написать программу для ее вычисления, но очевидных закономерностей в результатах не наблюдается.

[maxal]

Ну, наример, вот так выражается количество $b$-ичных цифр $d\ne 0$ в числе $n$:

$$\sum_{k=0}^{\infty} \delta_{d,\left( \left\lfloor \frac{n}{b^k}\right\rfloor \bmod b\right)},$$

где $\delta_{i,j}$ - дельта Кронекера.

[Alik]

насколько я понял d - это основание системы счисления, тогда зачем индексы i,j
можно пожалуйста ссылку на источник, наверное в нем я и найду название проблемы на английском

[maxal]

Нет. Основание системы - это $b$, а $d$ - это цифра количество вхождений которой в запись $n$ в $b$-ичной системе счисления мы подсчитываем.
$i,j$ - это вообще говоря абстрактные числа, для наших слагаемых мы имеем $i=d$ и $j=\left\lfloor \frac{n}{b^k}\right\rfloor \bmod b$.

[Alik]

OK, тогда почему k от 0 до бесконечности, ведь число позиций заданно?
Eще вопрос - а имеется ли действительно ограничение на основание системы счисления, скажем если оно будет -2 или 3, но (-1,0,1)?
Учитывает ли формула знак входящей в представление цифры?
Имеется ли обобщение формулы для случая когда требуется узнать "суммарное число вхождений" на некотором интервале, скажем от [1, N]?
Напомните пожалуйста что такое mod B ? (уж не остаток ли от деления)
P.S. Хочется все таки ссылочку на применение дельты Кронекера для таких целей.

[maxal]

Верхний индекс можно заменить на конечное число равное длине записи числа $n$, но формально это не играет роли, так как даже при суммировании до бесконечности все, за исключением конечного числа, слагаемые равны нулю.
Основание здесь предполагается положительным, хотя можно обобщить и до отрицательного. Для положительного основания, но нестандартного набора цифр достаточно просто переопределить функцию mod (да, это взятие остатка от деления), чтобы она возращала остаток из множества цифр.

Посчет суммарного числа вхождений цифры $d\ne 0$ для интервала $[1,N]$ (обозначим эту функцию $F_{b,d}(N)$) проще осуществить рекурсивно с глубиной рекурсии пропорциональной логарифму $N$, не привлекая даже посчет вхождений для одиночного числа (хотя неявно он, конечно, присутствует). А именно, для $N=u\cdot b^m + v$, где $0<u<b$ и $0\leq v<b^m$, или другими словами $u$ - это старшая $b$-ичная цифра числа $N$, а $v$ - все остальные. Тогда

$$F_{b,d}(N) = u\cdot m\cdot b^{m-1} + F_{b,d}(v) + C,$$

где довесок $C$ определяется в зависимости от соотношения $u$ и $d$:
если $u<d$, то $C=0$;
если $u=d$, то $C=v+1$;
если $u>d$, то $C=b^m$.

[Архипов]

Простейшая задача программирования. Ничего не нужно вычислять.
Число записано цифрами, то есть символами "2436547665433234589"
В какой форме выдать результат сортировки?Столбиком или строкой?
Нужен фрагмент программы сортировки или готовая программа?
Если для практических целей, то можно воспользоваться электронной таблицей MsExcel из пакета MsOffise - там есть в меню "сортировка".
Если программа нужна, то алгоритм прост.
1.Дана строка символов
2. Вычисляется длина строки Н (функция есть такая)
3. Задаем десять строковых переменных "0", "1", ...."9"
4 Цикл от 1 до Н
5.цикл от 0 до 9
проверяем поочередно каждый символ строки и сцепляем его с одной из строковых переменных, с которой совпадет очередной символ.
Конец цикла 5
Конец цикла 4
Вывод на печать десяти переменных. их длину (функция есть такая) )
Всё.

Добавлено спустя 8 минут 48 секунд:

Как видим, программа годится для систем счисления при основаниях от 2 до 10. Если, например, сортируем двоичную запись, то иметь в виду только количества нолей и единиц, остальные переменные покажут ноль.
Если нужно сортировать 16-ричное число, то в начале программы добавить еще 6 переменных от "А" до "F".

Добавлено спустя 15 минут 18 секунд:

Еще проще это делать в MsWord. копируем запись числа на лист, вызываем пункт меню "Поиск" , там вводим в окошко "3", щелкаем "искать все" - выдаст количество троек в записи числа.
Подобным образом считаем все остальные цифры.

[PAV]

Архипов,
Вы лишь подтвердили, что

Alik писал(а):

не проблема написать программу для ее вычисления

Написать программу - банально, небанально получить какой-либо теоретический результат. Допустим, не переводя число в другую систему счисления, по некоторой формуле ответить на вопрос. Автор спрашивал именно об этом.

[Alik]

PAV, спасибо за понимание
Сейчас меня интересует частный случай:
подсчет числа вхождений "1" и "-1" (знаки не различаются) в троичной сбалансированной записи {-1, 0, 1} числа n.
Вернее даже суммарный взвешенный показатель определяемый для интервала [1, N] как

$$\sum_{i}\\floor(\( \left\frac{x[i]}{[i+1]}\right\right)})$$

, где x - найденное число вхождений, i - количество позиций, floor - округление до наименьшего целого.
Для примера: имеются числа от 1 до N, записанные в троичной системе, для простоты ограничимся тремя позициями (p=3).
Такая запись представляет собой таблицу 3 столбика на 3^3 (27) строчек, для каждой строчки мы считаем ненулевые элементы.
Ниже представлены результаты

1   2   3  
6   12   8 

как видно полных строчек в таком разложении 8, теперь это число нужно разделить на (3+1) и взять наименьшее целое.
Тоже самое для 6/(1+1) и 12/(2+1), в результате получим 3+4+2=9.
Почему я спрашиваю про формулу - мне надо показать, что вне зависимости от p эта сумма всегда больше чем 2^p

[Alik]

Появилась следующая идея - если записать числа от 1 до 27 в троичной системе (1, 2, 3), а потом вычесть из разрядов 2,
то получим сбалансированную "перепутанную" запись (-1, 0, 1), где количество нулей будет равно количеству двоек в исходной.
Таким образом задачу можно свести к последовательности
A081603 "Number of 2's in ternary representation of n."
http://www.research.att.com/~njas/sequences/A081603
Но это не очень поможет, поскольку не указана общая формула и мы пойдем другим путем
A005836: Numbers n such that base 3 representation contains no 2.
a(2n)=3a(n), a(2n+1)=a(2n)+1
http://www.research.att.com/~njas/sequences/A005836
пока размышляю что это может дать

[maxal]

Alik писал(а):

Появилась следующая идея - если записать числа от 1 до 27 в троичной системе (1, 2, 3), а потом вычесть из разрядов 2,
то получим сбалансированную "перепутанную" запись (-1, 0, 1), где количество нулей будет равно количеству двоек в исходной.
Таким образом задачу можно свести к последовательности
A081603 "Number of 2's in ternary representation of n."

А также к тому рекурсивному алгоритму/формуле вычисления $F_{3,d}$, что я указал выше. Чем она вас не устраивает?

[Alik]

У меня давно все посчитанно, может быть не оптимально, но вполне устраивает. Единственная проблема - это то, что MATLAB отказывается считать для матриц больше чем 13 х (3^13), памяти говорит не хватает, ну и ладно. Для этих расчетов мое предположение работает, вопрос: а верно ли оно всегда?

[maxal]

Alik писал(а):

У меня давно все посчитанно, может быть не оптимально, но вполне устраивает. Единственная проблема - это то, что MATLAB отказывается считать для матриц больше чем 13 х (3^13), памяти говорит не хватает, ну и ладно. Для этих расчетов мое предположение работает, вопрос: а верно ли оно всегда?

О каких матрицах и о каком предположении идет речь?

[Alik]

Предположение о том, что суммарный взвешенный показатель (см. три поста вверх) всегда больше чем 2^p

[Gafield]

Требуемая величина равна

$$ \sum_{k=1}^p\left[\frac{2^k C_p^k}{k+1}\right]. $$

Она не меньше, чем

$$ \sum_{k=0}^p\left \frac{2^k C_p^k}{k+1}\right -(p+1)=\int_0^1(1+2x)^p dx-(p+1)= \frac{3^{p+1}-1}{2(p+1)}-(p+1). $$

Для очень маленьких $p$ ты уже проверил , а для $p>10$ очевидно, что последнее выражение больше, чем $2^p$.

Вот только интересно, эта задача имеет какой-либо смысл, или она типа олимпиадной?