Назовём число N влюблённым по основанию m в цифру 'k', если в символьном представлении по основанию m всех чисел от 0 до N цифра 'k' встречается N раз. Найти все влюблённые числа для 2 < m < 15, 0 < k < m-1, 0 < N < 2^63-1.
Пример вывода:
--------------------------
m = 2, k = '0'
1
10
100
101
110
--------------------------
m = 2, k = '1'
0
1
10
--------------------------
...
--------------------------
m = 10, k = '0'
1
100559404365
--------------------------
...
Здравствуйте, alo, Вы писали:
alo>Назовём число N влюблённым по основанию m в цифру 'k', если в символьном представлении по основанию m всех чисел от 0 до N цифра 'k' встречается N раз. Найти все влюблённые числа для 2 < m < 15, 0 < k < m-1, 0 < N < 2^63-1. alo>Пример вывода: alo>-------------------------- alo>m = 2, k = '0' alo>1 alo>10 alo>100 alo>101 alo>110 alo>-------------------------- alo>m = 2, k = '1' alo>0 alo>1 alo>10 alo>-------------------------- alo>... alo>-------------------------- alo>m = 10, k = '0' alo>1 alo>100559404365 alo>-------------------------- alo>...
У Вас в условии k>0, и мне показалось это правильным, т.к. при k=0 я могу понаписать нулей слева для любого числа. В примерах же два из них для k=0.
Здравствуйте, vadimcher, Вы писали:
V>У Вас в условии k>0, и мне показалось это правильным, т.к. при k=0 я могу понаписать нулей слева для любого числа. В примерах же два из них для k=0.
Писал по памяти — ошибся.
Оригинальное условие звучит так:
"Ведущие нули подавляются.
Найти все влюблённые числа в диапазоне от 0 до 2^63-1
для m = (2..15), k = ('0'..'m-1')"
т.е. 'k' из набора {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E'}
Есть функция times(m,k,n) — количество цифр k в числах [0..n], записанных по основанию m.
Функция неубывающая, как несложно догадаться.
Нужно найти все корни times(m,k,n)=n.
Если представить times(n) как ломаную (и получить уравнения каждого отрезка), то можно довольно резво попрыгать по этим отрезкам и отыскать все их пересечения с n.
Здравствуйте, alo, Вы писали:
alo>Назовём число N влюблённым по основанию m в цифру 'k', если в символьном представлении по основанию m всех чисел от 0 до N цифра 'k' встречается N раз. Найти все влюблённые числа для 2 < m < 15, 0 < k < m-1, 0 < N < 2^63-1.
Множество подобных N ограничено сверху. К сожалению, подобная граница может существенно помочь только при не очень больших N.
Я начну, пожалуй, со случая m=10. Так легче думается.
Рассмотрим некий "порог" 10^s.
Сколько всего цифр до этого числа? s*10^s-(10^s-10)/9
Сколько из них 0-й? s*10^(s-1)-(10^s-10)/9
Сколько каждой из цифр от 1 до 9? s*10^(s-1)
Теперь заметим:
I. Число 0 до s-го порога мы встретили s*10^(s-1)-(10^s-10)/9 раз, а до s+1 порога (s+1)*10^s-(10^(s+1)-10)/9 раз.
а) Если число нулей, которые мы встретили до s-го порога больше, чем s+1 порог, т.е. больше, чем 10^(s+1), то среди чисел от 10^s до 10^(s+1) искать N нет смысла. Когда это так? (910-9s)*10^(s-2) < 1. s>101.
б) Если число нулей, которые мы встретили до s+1-го порога меньше, чем s порог, т.е. меньше, чем 10^s, то опять-таки искать N диапазоне между 10^s и 10^(s+1) нет смысла. (9s-10)*10^s < -10. Т.е. никогда.
В общем, здесь результат пока не очень впечатляющий. Числа надо искать до 10^101.
II. Число k>0 до s-го порога мы встретили s*10^(s-1) > 10^(s+1) при s>100. До s+1 порога (s+1)*10^s < 10^s никогда.
Таким образом для чисел k больше 0 и m=10 нет смысла искать числа длиннее чем 100 знаков.
Результат получился скорее математический. Мы показали, что множество таких N ограничено сверху для всех k.
Однако для меньших оснований m аналогичные рассуждения приводят к границе в m^2 знаков в m-ичной системе счисления, например, при m=3, надо искать числа до 3^9 (19683), может быть 3^10 (59049), что намного меньше, чем 2^64 (18446744073709551616). Для m=4 4^17=17179869184, тоже подъемно, как никак.
Здравствуйте, Кодт, Вы писали: К>Есть функция times(m,k,n) — количество цифр k в числах [0..n], записанных по основанию m. К>Функция неубывающая, как несложно догадаться.
К>Нужно найти все корни times(m,k,n)=n.
К>Если представить times(n) как ломаную (и получить уравнения каждого отрезка), то можно довольно резво попрыгать по этим отрезкам и отыскать все их пересечения с n.
Задача разбивается на две подзадачи:
1. Найти эффективный алгоритм функции times. В оригинальном условии стояло ограничение на время решения для заданных m и k в одну секунду. Эта подзадача вроде как решена.
2. Найти эффективный алгоритм нахождения границ отрезков в районе точек пересечения. Пока не решена.
Здравствуйте, vadimcher, Вы писали:
V> А что за алгоритм, который находит, но не все N?
Имеется функция, вычисляющая N для заданных n,m и k. Имеется функция, вычисляющая количество знаков i для заданных N и m, т.е. некое число N(n) имеет по основанию m в символьном представлении i знаков. В числе N(n+1) могут измениться не более i знаков. Вычисляем d = abs((n-N)/i). Если d==0 и N!=n, то d=1. Выбираем следующее значение n=n+d.
Подобный алгоритм довольно быстро сходится в окрестностях точек пересечения. Если же принять i фиксированным и достаточно большим (например 128), время поиска увеличивается (не укладывается в установленный лимит), но находятся новые значения N.
Здравствуйте, vadimcher, Вы писали:
V>Однако для меньших оснований m аналогичные рассуждения приводят к границе в m^2 знаков в m-ичной системе счисления, например, при m=3, надо искать числа до 3^9 (19683), может быть 3^10 (59049), что намного меньше, чем 2^64 (18446744073709551616). Для m=4 4^17=17179869184, тоже подъемно, как никак.
Странно.
m = 4, k = 1
2103333333333333333333333333321 — 31 знак
2103333333333333333333333333322
2103333333333333333333333333323
2103333333333333333333333333330
m = 5, k = 1
232104311403333244400141322 — 27 знаков
Здравствуйте, alo, Вы писали:
alo>1. Найти эффективный алгоритм функции times. В оригинальном условии стояло ограничение на время решения для заданных m и k в одну секунду. Эта подзадача вроде как решена. alo>2. Найти эффективный алгоритм нахождения границ отрезков в районе точек пересечения. Пока не решена.
Функция выглядит фрактально.
пусть i-я средняя скорость
speed(p) = (times(2*m^p)-times(m^p))/(m^p)
весь исходный интервал [0..m*m^p) можно разбить на [0..k*m^p), [k*m^p..(k+1)*m^p), [(k+1)*m^p..m*m^p)
и скорости на нём будут speed(p), speed(p)+1, speed(p).
А поскольку мы ищем пересечение с y(n)=n, dy/dn = 1, то очевидно, что
— если times(n1)>n1 | n1=k*m^p, то в области n>=n1 искать не нужно;
— аналогично, если times(n2)<n2, то не нужно искать в области n<=n2;
— если times(n1)<n1 && times(n2)>n2, то получаем ровно один корень на [n1..n2) и m-1 новых целей — интервалы [i*m^p..(i+1)*m^p) | i!=k
В худшем случае получается 1 + (m-1)*(1 + (m-1)*(....)) {p раз} целей, где m^p — верхняя граница диапазона.
Здравствуйте, alo, Вы писали:
alo>Здравствуйте, vadimcher, Вы писали:
V>>Однако для меньших оснований m аналогичные рассуждения приводят к границе в m^2 знаков в m-ичной системе счисления, например, при m=3, надо искать числа до 3^9 (19683), может быть 3^10 (59049), что намного меньше, чем 2^64 (18446744073709551616). Для m=4 4^17=17179869184, тоже подъемно, как никак.
alo>Странно. alo>m = 4, k = 1 alo>2103333333333333333333333333321 — 31 знак alo>2103333333333333333333333333322 alo>2103333333333333333333333333323 alo>2103333333333333333333333333330
alo>m = 5, k = 1 alo>232104311403333244400141322 — 27 знаков
Может для других m надо аккуратнее расписать? Может там 2*m^2 -- число знаков, или что-то вроде этого, надо проверить, короче.
Здравствуйте, alo, Вы писали:
К>>А поскольку мы ищем пересечение с y(n)=n, dy/dn = 1,
alo>Не понял, почему 1?
Почему производная y(n) равна 1? А чему она равна?
Напоминаю: нужно найти все корни уравнения times(n) == n.
Слева — затейливая ломаная, а справа — прямая линия.
Ломаную можно аппроксимировать тремя отрезками: (n0,t0) — (n1,t1) — (n2,t2) — (n3,t3), где t_i = times(n_i)
Причём известно, что на [n1..n2) — из-за наличия цифры k в старшем разряде — ломаная везде идёт круче, чем y(n). Поэтому если t1>n1 и t2>n2, то пересечений с y(n) на всём этом интервале нет.
Ещё можно сообразить, что для n<m^p производная не превосходит p (для n = <kkk...k>)
Здравствуйте, Кодт, Вы писали:
К>>>А поскольку мы ищем пересечение с y(n)=n, dy/dn = 1,
alo>>Не понял, почему 1? К>Почему производная y(n) равна 1? А чему она равна?
Стормозил, в голове застряло times(n). Конечно 1.
К>Напоминаю: нужно найти все корни уравнения times(n) == n. К>Слева — затейливая ломаная, а справа — прямая линия.
Times(n) затейливо виляет вокруг y(n) на отрезке [0..k*m^k]. При этом для k>1 количество корней не менее k. К>Ломаную можно аппроксимировать тремя отрезками: (n0,t0) — (n1,t1) — (n2,t2) — (n3,t3), где t_i = times(n_i) К>Причём известно, что на [n1..n2) — из-за наличия цифры k в старшем разряде — ломаная везде идёт круче, чем y(n).
Если цифра k стоит только в одном старшем разряде, times(n) и y(n) параллельны, а в отдельных случаях просто совпадают. K> Поэтому если t1>n1 и t2>n2, то пересечений с y(n) на всём этом интервале нет.
Или количество пересечений чётно?
Здравствуйте, alo, Вы писали:
К>>Причём известно, что на [n1..n2) — из-за наличия цифры k в старшем разряде — ломаная везде идёт круче, чем y(n). alo>Если цифра k стоит только в одном старшем разряде, times(n) и y(n) параллельны, а в отдельных случаях просто совпадают. K>> Поэтому если t1>n1 и t2>n2, то пересечений с y(n) на всём этом интервале нет. alo>Или количество пересечений чётно?
Оно не может быть чётно, потому что на [n1,n2) dt/dn >= 1.
Вот если t(n1) < n1, t(n2) < n2 — то возможно, что мы горбом где-то пересекли.
Перекуём баги на фичи!
