2014 dxdy logo

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

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




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


11/01/06
5660
Свежие находки:
A173443(13) $\leqslant 3000811,$
A173443(16) $\leqslant 5165039,$
A173443(20) $\leqslant 12344321,$
A173443(21) $= 243309,$
A173443(24) $\leqslant 33333333.$

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


11/01/06
5660
Для 13, 16 и 20 указанные оценки оказались точными значениями:

A173443(13) = 3000811,
A173443(16) = 5165039.
A173443(20) = 12344321.

 Профиль  
                  
 
 Re: Сумма цифр у кратного числа
Сообщение28.11.2010, 11:07 


04/05/10
57
Ответ: для простого $p$ $10^{p-1} = 1 \mod p$ (малая теорема Ферма)
Поэтому $10^{(p-1)/2} = -1  \mod p$.

$10^{(p-1)/2} + 1  = 0\mod p$.
Т.е. число из двух единиц и многих нулей, делящееся на $p$, это $10^{(p-1)/2}+1$.
Для p=17 это $10^8+1$.

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


09/02/06
4382
Москва
$10^{(p-1)/2}=(\frac{10}{p})\mod p$ не обязательно -1.

 Профиль  
                  
 
 Re: Сумма цифр у кратного числа
Сообщение28.11.2010, 17:33 


04/05/10
57
$10^{(p-1)/2} = x \mod p$
$x^2 = 10^{p-1}=1 \mod p$
т.е. $x = 1$ или $x=-1 \mod p$.

$10^{(p-1)/2}=1 \mod p$ в двух случаях:
1. $10 = 1 \mod p$, отсюда p = 3
2. $(p-1)/2 = p-1$, отсюда p = 1
Согласен, в совсем общем случае мое утверждение неверно, но в рамках задачи - вполне.

-- Вс ноя 28, 2010 18:41:39 --

Кстати, отсюда для числа, делящегося на три, минимальная сумма цифр равна 3, а не 2, как для других простых

-- Вс ноя 28, 2010 18:42:49 --

по mod 5, да, $10^{n} = 0$, для других простых вроде верно

-- Вс ноя 28, 2010 18:44:38 --

В общем, важно, чтобы
1. $10 \ne 1 \mod p$
2. $10 \ne 0 \mod p$

Простые p, которые удовлетворяют данному условию - это все, кроме 2, 3, 5

-- Вс ноя 28, 2010 18:50:54 --

Вот полный ответ:
1. мин. сумма цифр числа, которое делится на 2, равна 1: например 10
2. мин. сумма цифр числа, которое делится на 3, равна 3: например 3
3. мин. сумма цифр числа, которое делится на 5, равна 1: например 10
4. для остальных простых p мин. сумма цифр числа, которое делится на p, равна 2: например $10^{(p-1)/2}+1$

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


11/01/06
5660
AlexandreII в сообщении #381434 писал(а):
4. для остальных простых p мин. сумма цифр числа, которое делится на p, равна 2: например $10^{(p-1)/2}+1$

Это неверно. Контрпример: $p=31$, для которого A077196(31)=3.

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

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



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

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


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

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