2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Сумма цифр у кратного числа
Сообщение21.02.2009, 20:22 
Аватара пользователя


17/05/08
358
Анк-Морпорк
а) Какое наименьшее значение может принимать сумма цифр числа, кратного 17-ти?
б) Числа, кратного 31-му?
в) Числа, кратного 41-му?

 Профиль  
                  
 
 
Сообщение21.02.2009, 21:23 
Заслуженный участник
Аватара пользователя


01/08/06
3136
Уфа
По-моему, во всех 3-х задачах ответ 2.
Нужно рассмотреть числа вида $10^n+1$, дальше очевидно.

Добавлено спустя 3 минуты 7 секунд:

Ан нет, не всё так просто :D

 Профиль  
                  
 
 
Сообщение21.02.2009, 22:19 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Ох, непросто! Просто только у 17 и вообще у первообразных корней, а так прямо непонятно, что делать. Ну, то есть, для частных случаев понятно: выписывать все остатки от степеней 10, сидеть и перебирать, там немного...

 Профиль  
                  
 
 
Сообщение21.02.2009, 22:42 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Вот-вот, я сам так и перебирал (только программой, не вручную).

Особо интересно число 11233 - для него программа со всеми оптимизациями нашла кратное с минимальной суммой цифр минут за 30-40.

Пока (среди чисел, не делящихся на 3) наибольшее значение минимума суммы цифр кратных чисел достигается для числа 2981.
Ещё интересны числа 79, 407 и 239

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


09/02/06
4401
Москва
Алгоритм простой. Надо выяснить порядок числа 10 по модулю числа a=17,31,41,...(взаимно простого с 10, в противном случае к этому сводится с помощью нулей в конце) m чётный или нет. Если он чётен, то $a|10^m-1=(10^{m/2}-1)(10^{m/2}+1)\to a|10^{m/2}+1$ и ответ 2. В случае нечётности ответ больше 2. Необходимым и достаточным условием нечётности является нечётность порядка 10 относительно любого нечётного простого делителя p числа а. Для этого необходимо, чтобы 10 был по крайней мере квадратичным вычетом, что легко проверяется.

 Профиль  
                  
 
 
Сообщение22.02.2009, 00:24 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Условия получения ответа 2 необходимо подкорректировать.

К примеру, для числа 11 или 17 оно срабатывает (среди остатков этих чисел на степени десятки имеется +1 и -1), а вот для числа 11*17=187, хотя последоватлеьность остатков степеней десятки на это число имеет чётный период, равный 16, но среди чисел, кратных 187-ми наименьшая сумма цифр будет равна 4 и достигаться в числе 210001

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


09/02/06
4401
Москва
Руст писал(а):
$a|10^m-1=(10^{m/2}-1)(10^{m/2}+1)\to a|10^{m/2}+1$ и ответ 2.

Вообще то я вначале это писал для нечётного простого а или для степени простого числа. Для составного возможно деление разных сомножителей. Поэтому требуется уточнение. Пусть $$a=\prod_i p_i^{k_i}$$. Определим $m_i$ как минимальное число, для которого $p_i^{k_i}|10^{m_i}-1$. Если хотя бы одно из чисел $m_i$ нечётно то искомая сумма цифр $S>2$. Записывая $m_i=2^{r_i}l_i$ где $l_i$ нечётное получаем, что если $r_i$ разные, то $S>2$. Необходимым и достаточным условием $S=2$ является $r_i=r\ge 1 \forall i$. В частности если есть простые делители вида $p=3\mod 4$ число 10 не должен быть квадратичным вычетом по ним, а по всем делителям (если есть и такие) $p=1\mod 4$ число 10 должен быть квадратичным вычетом.
Интересная гипотеза: $S(a)\le 18$. Легко показать, что $S(99)=18$.

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


11/01/06
5710
Руст в сообщении #188497 писал(а):
Интересная гипотеза: $S(a)\le 18$.

Я думаю, $S(a)$ неограничена. Идея - взять достаточно большой простой $p$ делитель числа $10^k-1$, тогда с большой вероятностью $S(p) > \log_k p.$
Так как существует ровно $k$ различных степеней 10 по модулю $p$, и сумма любых $t$ из них "покроет" не более $k^t$ вычетов по модулю $p$. Поэтому, если $k^t<p$, то становится вероятно, что 0 не покроется, а то есть $S(p)>t$.

Например, для опровержения $S(a)\leq 18$, можно попробовать взять $k=41$ и $p=201763709900322803748657942361$, для которых $\log_k p > 18.1$ Хотя проверить так ли это на самом деле тут будет довольно трудоемко.

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


09/02/06
4401
Москва
Эта действительно глупая гипотеза (об этом я давно уже догадался), так как очевидно $S(10^n-1)=9n$.

 Профиль  
                  
 
 
Сообщение26.02.2009, 17:23 
Заслуженный участник
Аватара пользователя


01/08/06
3136
Уфа
Кстати, последовательность $S(n)$ имеется в OEIS (разумеется, кто бы сомневался!). Однако там мало членов, и в комментсах чушь написана.

 Профиль  
                  
 
 
Сообщение26.02.2009, 22:14 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Ух ты, спасибо, а я, честно говоря, там даже и не искал. Действительно, там материала очень мало и суждения поверхностные

Я нашёл числа, не делящиеся на 9, но у ктоторых S(n)=9. Наименьшее из них - число 717=3*239.

Ещё интересно число $2439=3^2*271$: оно не делится ни на 99, ни на 909, но S(2439)=18.

Среди чисел, не делящихся на 9 наибольшая S(n), равная 15-ти достигается у числа 13947=3*4649

А среди чисел, не делящихся на 3 наибольшее значение S(n), равное 11-ти достигается в порстом числе 21649

Завтра как уйду на работу, оставлю программу работать на весь день.

 Профиль  
                  
 
 
Сообщение27.02.2009, 00:37 
Модератор
Аватара пользователя


11/01/06
5710
worm2 писал(а):
Кстати, последовательность $S(n)$ имеется в OEIS (разумеется, кто бы сомневался!). Однако там мало членов, и в комментсах чушь написана.

Отослал исправления к A077196, а заодно и к смежным A077194 и A077195.

 Профиль  
                  
 
 
Сообщение27.02.2009, 09:18 
Аватара пользователя


17/05/08
358
Анк-Морпорк
А как туда отсылать исправления?

 Профиль  
                  
 
 
Сообщение27.02.2009, 09:32 
Модератор
Аватара пользователя


11/01/06
5710
General
см. http://oeis.org/Submit.html

 Профиль  
                  
 
 
Сообщение27.02.2009, 23:12 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Спасибо, отослал им б-файл для чисел до 56000. Нашёл ещё одно число-рекордсмен, 51139=11*4649. S(51139)=14.

Что интересно, чисел с S=13 пока не нашлось

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

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



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

Сейчас этот форум просматривают: nnosipov


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

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