2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Трудная задача. Теория чисел, комбинаторика.
Сообщение28.04.2009, 22:35 


28/04/09
4
Существует двоичное разложение чисел, в котором коэффициенты при степенях двойки могут быть как 0,1, так и -1, т.е.
$n=\sum\limits_{i=0}^{v}c_i2^i$, $c_i\in\{0,-1,+1\}$.
Как видно, разложение не однозначно. Например, число 3 записывается как $\overline{11}$ и как $\overline{10-1}$.
Определим кратчайшую форму записи, как ту, в которой количество ненулевых коэффициентов минимально.
Кратчайшая форма легко получается из обычного двоичного разложения. Ее коэффициенты считаются по формуле $\delta_i=\gamma_{i+1}-a_{i+1}$, где $a_i$ и $\gamma_i$ - коэффициенты обычного двоичного разложения соответственно чисел $a$и $3a$.
Весом разложения назовем количество ненулевых цифр.

Вопрос: каких чисел больше? Тех, у которых вес минимального разложения - четное число, или тех, у которых - нечетное?

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

Ответ известен - асимптотически поровну. Хотелось бы строго доказать.
А.О. Гельфонд в статье "Sur les nombres qui ont des properties additives et multiplicatives donnees" дает доказательство для обычного двоичного разложения. А мне нужно для $\{\pm1,0\}$, причем для кратчайшей формы. Используется разрывный множитель $\frac{1}{p}\sum\limits_{z=0}^{p-1}e^{2\pi i\frac{S(n)}{p}z$, равный 1, если $S(n)=0(mod p)$ и 0 в противном случае. $p=2$

 Профиль  
                  
 
 
Сообщение29.04.2009, 06:30 
Модератор
Аватара пользователя


11/01/06
5710
Начните с формулировки явного описания кратчайших форм (типа того, что +1 не может стоять рядом с -1 и т.п.), а там глядишь и нечто подобное фиббоначиевой с.с. вылезет.
На первый взгляд задача не кажется особо сложной.

 Профиль  
                  
 
 
Сообщение29.04.2009, 18:24 


28/04/09
4
Спасибо, maxal. Но задача действительно трудная.
Всю теорию о кратчайших формах я разобрал. О них хорошо написано у Гашкова http://inf.1september.ru/articlef.php?ID=200600507. Параграф 17 (там опечатка после 28 задачи - не $\alpha_n=\alpha_{n+1}=0$, а $\delta_i=\gamma_{i+1}-\alpha_{i+1}$).
А как поможет система Фибоначчи?

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

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



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

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


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

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