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
3046
Уфа
По-моему, во всех 3-х задачах ответ 2.
Нужно рассмотреть числа вида $10^n+1$, дальше очевидно.

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

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

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


18/05/06
13435
с Территории
Ох, непросто! Просто только у 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
4382
Москва
Алгоритм простой. Надо выяснить порядок числа 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
4382
Москва
Руст писал(а):
$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
5654
Руст в сообщении #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
4382
Москва
Эта действительно глупая гипотеза (об этом я давно уже догадался), так как очевидно $S(10^n-1)=9n$.

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


01/08/06
3046
Уфа
Кстати, последовательность $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
5654
worm2 писал(а):
Кстати, последовательность $S(n)$ имеется в OEIS (разумеется, кто бы сомневался!). Однако там мало членов, и в комментсах чушь написана.

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

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


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

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


11/01/06
5654
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  След.

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



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

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


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

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