2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение28.02.2009, 01:00 
Модератор
Аватара пользователя


11/01/06
5654
General
Отправьте в OEIS новую последовательность:
a(n) = minimal positive integer m such that A077196(m)=n
12 членов у ваc, как я понял, уже есть

 Профиль  
                  
 
 
Сообщение28.02.2009, 07:21 


21/06/06
1721
Насчет 17 все очень даже тривиально
Ответ 2
Число 100000001.

 Профиль  
                  
 
 
Сообщение28.02.2009, 17:27 
Аватара пользователя


17/05/08
358
Анк-Морпорк
maxal писал(а):
General
Отправьте в OEIS новую последовательность:
a(n) = minimal positive integer m such that A077196(m)=n
12 членов у ваc, как я понял, уже есть


Действительно, хорошая идея, спасибо. Попробую, может, до понедельника a(13) всё-таки найдётся, а если нет - то 12 отошлю.
Сейчас последоватлеьность такая:
1, 7, 3, 79, 41, 33, 239, 2629, 9, 2981, 21649, 813, ?, 51139, 13947, ?, ?, 99,
и ещё а(27)=999, а(36)=9999

Задача очень интересная, написал о ней у себя на сайте:
О сумме цифр, обобщённом признаке делимости и одной нерешённой задаче

 Профиль  
                  
 
 
Сообщение03.03.2009, 07:27 
Модератор
Аватара пользователя


11/01/06
5654
General
Кстати, по какому алгоритму вы вычисляли значения A077196?
И сколько суммарно потребовалось времени, чтобы вычислить 56000 значений?

 Профиль  
                  
 
 
Сообщение04.03.2009, 15:15 
Заслуженный участник


09/02/06
4382
Москва
Найти число n для которого $a(n)=m$ можно таким образом. Пусть $N=\frac{10^m-1}{9}$. Ясно, что $S(N)=m$. Пусть $n|N$. Тогда m является периодом числа 10 по модулю n. Допустим, что это минимальный период. Пусть число R делится на n. Тогда существует делитель b числа N для которого $n|b|N, s(b)\le S(R)$. Доказательство простое, если $R\ge 10^m$ заменяем степени меньшими, группируем цифры если есть переполнение, повторяя процедуру несколько раз получим искомое число b. Поэтому просматривая делители числа N находим (пусть не минимальное) число n, для которого $a(n)=m$.
Например для m=13 надо факторизовать число N из 13 единиц и если для некоторого минимального делителя n все делители b $n|b|N$ имеют $s(b)\ge 13$, то n нам подходит.

 Профиль  
                  
 
 
Сообщение04.03.2009, 21:58 
Заслуженный участник


09/02/06
4382
Москва
Обозначим через $m(n), b(n)$ функции, для которых $m(n)$ минимальная сумма цифр для чисел делящихся на n, b(n) минимальное число с суммой цифр $m(n)$, делящиеся на n. Пусть $a(m)$ минимальное число $n$, такое, что $m(n)=m$ (я раньше другое обозначал, не совпадающее с обозначениями автора).
Приведу алгоритм вычисления функции $a(m)$ для любого основания исчисления r. В соответствии с этим придётся разделит простые числа на нулевой класс, состоящий из делителей основания r (2,5 для r=10), первый класс, состоящий из простых делителей числа r-1 (3, для r=10) и общий класс - остальные простые. Каждое число $n=n_0n_1n_2$ разлагается на множители с простыми делителями из нулевого класса, первого класса и общего класса, например $n=108=4*27*1$ для $r=10$. Очевидно $m(n)=m(n_1*n_2),b(n)=b(n_1*n_2)r^k$, где k легко вычисляется по разложениям $n_0,r$.
Пусть $n=n_2$ (без простых делителе нулевого и первого класса). Вычислим для такого числа $$n=n_2=\prod_i p_i^{k_i}$$ минимальный период для основания r по модулю n как $T(n)=gcd(T(p_i^{k_i})$. При этом вначале вычисляется $T(p_i)$ факторизацией числа $p_i-1$ и делением на простые числа $q|p_i-1$ периода, первоначально взятого как $p_i-1$ и сокращённого на q, пока остается периодом. Далее вычисляется на какую степень делится $v_{p_i}(r^{T(p_i)}-1)$, что дает $T(p_i^{k_i})=T(p_i)*p_i^c, c=max(0,k_i-v_{p_i}(r^{T(p_i)}-1))$. Тогда число из T(n) единиц делится на n, т.е. $m(n)\le T(n),b(n)\le N(T(n))$, где $N(k)$ число из k единиц $N(k)=\frac{r^k-1}{r-1}$. Для произвольного n минимальное число состоящее только из цифр 1 и возможно из нулей в конце находится из $N(l(n))*r^k, l(n)=\frac{n_1T(n)}{(n_1,T(n))}$.
Пусть $l_1=l(b(n))$. Тогда число из $l_1$ единиц и число из $l(n)$ единиц делятся на $n_1n_2$, так как $l(n)$ минимальное число из одних 1 делящихся на $n_1n_2$, получаем $l(n)|l_1$ (иначе найдётся число с меньшим количеством 1, делящийся на n). Была идея, как отсюда получит, что $m(n)|l(n)$ и в качестве числа $b$ (пусть не минимального из $s(b)=m(n)$ можно взять $n|b|N(l(n))$. Идею потерял. Соответственно возможно не минимальное можно искать так $a(m)=p_1^{k_1}q$, где $p_1$ простое число первого класса, q простой делитель $N(m)$ числа из m единиц, точнее даже как $q|\Phi_m(r)$ - делитель значения кругового многочлена.
Похоже, что это даст минимальное $a(m)$. Соответственно $a(13)$ надо искать как минимальный простой делитель $\Phi_{13}(10)=\frac{10^{13}-1}{9}$. Наверно из-за простоты этого числа $a(13)$ большое и вы GENTRAl не могли найти.

 Профиль  
                  
 
 
Сообщение05.03.2009, 04:49 
Модератор
Аватара пользователя


11/01/06
5654
Руст
Суммы 13 и 16 по твоему рецепту нашлись:
A077196(265371653)=13
A077196(477076475359)=16
Правда, я не мудрствуя лукаво, просто перебрал делители $\frac{10^n-1}{9}$, и для каждого вычислил значения A077196.

Добавлено спустя 1 час 49 минут 30 секунд:

Руст в сообщении #191758 писал(а):
В соответствии с этим придётся разделит простые числа на нулевой класс, состоящий из делителей основания r (2,5 для r=10), первый класс, состоящий из простых делителей числа r-1 (3, для r=10) и общий класс - остальные простые. Каждое число $n=n_0n_1n_2$ разлагается на множители с простыми делителями из нулевого класса, первого класса и общего класса, например $n=108=4*27*1$ для $r=10$. Очевидно $m(n)=m(n_1*n_2),b(n)=b(n_1*n_2)r^k$, где k легко вычисляется по разложениям $n_0,r$.

Последнее равенство неверно. Например для $n=6$, $r=10$:
$$b(6)=12\ne b(3)\cdot 10=30.$$

 Профиль  
                  
 
 
Сообщение05.03.2009, 08:32 
Заслуженный участник


09/02/06
4382
Москва
Да $b(n)$ как минимальный не обязательно так представляется. Дальше я избегал от нахождения минимального, а просто искал хотя бы одно из значений специального вида, среди делителей числа $N(l(n))*r^k$.

 Профиль  
                  
 
 
Сообщение05.03.2009, 15:25 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Здорово!
Написал большой пост про алгоритм, но что-то проглючило, пока напишу, что
A077196(2071723)=17
А собственно кратное - 1100203001211
Времени затрачено чекунды 3

 Профиль  
                  
 
 
Сообщение05.03.2009, 18:40 
Модератор
Аватара пользователя


11/01/06
5654
General
Ну собственно большой пост писать необязательно - скорее всего используется вариация на тему динамического программирования. Сложность пропорциональна произведению $n$ и показателя $10$ по модулю $n$. Угадал? :lol:

 Профиль  
                  
 
 
Сообщение07.03.2009, 13:50 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Да-да, именно так.
За первый час нашлись значения A077196 где-то для первых 20-30 тысяч чисел, ну а после 50000 - где-то по 1000 значения за час (разумеется, перебирались только нечётные и не делящиеся на 5 числа)

 Профиль  
                  
 
 Re: Сумма цифр у кратного числа
Сообщение26.09.2010, 17:46 
Модератор
Аватара пользователя


11/01/06
5654
Рассмотрим репьюнит $R_n=\frac{10^n-1}9=\underbrace{11\dots1}_{n}$. Как мы уже выяснили A077196$(R_n)=n$, а вот усиление этого утверждения:

Докажите, что всякое кратное числа $R_n$ содержит не менее $n$ ненулевых цифр.

(моё решение)

 Профиль  
                  
 
 Re: Сумма цифр у кратного числа
Сообщение26.09.2010, 18:20 
Заслуженный участник


03/12/07
343
http://kvant.mirror1.mccme.ru/1971/06/r ... nta_ma.htm

 Профиль  
                  
 
 Re: Сумма цифр у кратного числа
Сообщение26.09.2010, 18:40 
Модератор
Аватара пользователя


11/01/06
5654
Edward_Tur в сообщении #356433 писал(а):
http://kvant.mirror1.mccme.ru/1971/06/resheniya_zadachnika_kvanta_ma.htm

Если обобщить, то можно утверждать, что натуральные кратные числа $\frac{10^{mn}-1}{10^m-1}$ содержат не менее $n$ ненулевых цифр.
Для репьюнитов имеем $m=1$, в задаче из Кванта - $(m,n)=(2,6)$.

 Профиль  
                  
 
 Re: Сумма цифр у кратного числа
Сообщение27.09.2010, 01:30 
Модератор
Аватара пользователя


11/01/06
5654
General в сообщении #191992 писал(а):
Написал большой пост про алгоритм, но что-то проглючило, пока напишу, что
A077196(2071723)=17
А собственно кратное - 1100203001211

Только сейчас заметил несостыковку. В вашем кратном сумма цифр равна 12, и поэтому A077196(2071723)=12, что я также подтверждаю своими вычислениями.

А вот A077196(5363222357)=17, и поэтому A173443(17) $\leq 5363222357$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 36 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group