2014 dxdy logo

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

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




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


11/01/06
5702
Свежие находки:
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
5702
Для 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
4397
Москва
$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
5702
AlexandreII в сообщении #381434 писал(а):
4. для остальных простых p мин. сумма цифр числа, которое делится на p, равна 2: например $10^{(p-1)/2}+1$

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

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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