Неоднозначность представления чисел

[Alik]

Пусть имеется разложение натурального числа по базису \beta, для простоты ограничимся третьей степенью:
\textit{n}=a_3\beta^3-$a_2\beta^2\pm$a_1\beta\pm$a_0, где $a_i\in [0;\beta-1]$. Например в случае двоичного разложения ($a_i=0,1$) имеем:
\textit{n}=a_38-$a_2$4\pm$a_1$2\pm$a_0. Очевидно, что для числа $5 (как и для $3) имеется пять вариантов представления:

$ \left\{ \begin{array}{l} 8-4+2-1=5\\8-4+1=5\\8-2-1=5\\4+2-1=5\\4+1=5 \end{array} \right. $

Обратим внимание на одно интересное свойство. Если дополнить этот ряд следующим образом:

$ \left\{ \begin{array}{l} 8-4+1\\8-2-1\\4+1 \end{array} \right. $

то плюсы и минусы при коэффициентах (исключая $a_3) будут встречаться одинаковое число раз.
Учитывая свойство "самодополнения", количество неднозначностей в данном случае равно двум (числа $5 и $3)
Требуется найти такой базис \beta, в котором количество подобных неднозначностей максимальное.

P.S. извиняюсь за долгое редактирование

[незваный гость]

А в чем вопрос? И Что такое $ в формуле?

[maxal]

Alik писал(а):

Учитывая свойство "самодополнения", количество неднозначностей в данном случае равно двум (числа $5 и $3)

Непонятно при чем тут свойство "самодополнения" и вообще, что это такое (четкое определение).
Сформулируйте задачу в общем виде не аппелируя к примеру, а то непонятно, что именно вы хотите найти.

[Alik]

Ещё раз: есть набор чисел \textit{n_k}\in N, полученных с помощью \textit{n_k}=a_3\beta^3\pm$a_2\beta^2\pm$a_1\beta\pm$a_0
Найти такой базис \beta при котором \textit{k} масимальное. Исходя из того, что количество
положительных и отрицательных $a_i (кроме $a_3) одинаково в каждом разложении.

[maxal]

Alik писал(а):

Ещё раз: есть набор чисел \textit{n_k}\in N, полученных с помощью \textit{n_k}=a_3\beta^3\pm$a_2\beta^2\pm$a_1\beta\pm$a_0
Найти такой базис \beta при котором \textit{k} масимальное.

Подозреваю, что количество различных представимых чисел будет расти с ростом $\beta.$ Поэтому искомый максимум равен $+\infty$ и не достигается ни при каком $\beta.$

[PAV]

Это действительно так хотя бы потому, что только за счет $a_0$ мы всегда сможем получить все числа от $-\beta$ до $\beta$. Поэтому количество представимых чисел уж точно не меньше величины $\beta$.

Только по-моему автор имел в виду не это, а то, каково максимальное число чисел, которые можно представить неоднозначно. Пусть еще уточнит.

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

Вообще-то даже в примере автора неоднозначно представимы не только числа 5 и 3, но и 1:

1 = 1 = 2-1 = 4-2-1

и 2:

2 = 2 = 4-2 = 8-4-2

и 4

4 = 4 = 8-4

[Alik]

На самом деле и первое и второе, т.е. для \beta=2 таких чисел два, сколько их будет для \beta=3;4;5... соответственно 3; 4; 5 и т.д?
Может быть мне так и не удалось удачно объяснить, что обязательное условие для таких чисел - дополнимость. Более того
в случае $5 и $3 очевидно, что общее количество вариантов равно старшему разряду $2^3=8
Как быть с избыточными системами счисления?

[PAV]

Alik писал(а):

На самом деле и первое и второе, т.е. для \beta=2 таких чисел два,

Так и не понял, почему два. Чем не устраивают примеры других неоднозначностей, которые я привел?

Что такое "избыточные системы счисления"?

[Alik]

Всё правильно, но где же дополняющие выражения?
Я в своем примере показал как они выглядят для $5 могу привести для $3

$ \left\{ \begin{array}{l} 8-4-2+1=3\\8-4-1=3\\4-2+1=3\\4-1=3\\2+1=3 \end{array} \right. $

Сопряженные суммы:

$ \left\{ \begin{array}{l} 8-4-1\\4-1\\2+1 \end{array} \right. $

Требуется показать, что такое дополнение для любого \textit{n_k} существует в базисе \beta.

Цитата:

Что такое "избыточные системы счисления"?

Избыточными являются, в частности, система счисления Бергмана (1) и зеркально-троичная (2)

\textit{x}=$p_{-2}\tau^{-2}+p_{-1}\tau^{-1}+p_0+p_1\tau^1+p_2\tau^2 (1)

\textit{y}=$q_{-2}\tau^{-4}+q_{-1}\tau^{-2}+q_0+q_1\tau^2+q_2\tau^4 (2)

где \tau=\frac {1+\sqrt{5}} {2} - золотое сечение

В принципе, даже не важно, что будет в старшем разряде (8 или другое число), главное чтобы проявлялась неоднозначность.
Полиномиальная система счисления выбрана как наиболее привычная, не исключено, что подобная операция возможна
и в других позиционных системах. Например в представлении Цекендорфа или разложении на сумму простых чисел.

[maxal]

Попробую переформулировать еще раз. Нужно найти такое целое $\beta>1$ и некоторое множество целочисленных наборов $A = \{ (a_3, a_2, a_1, a_0) : -\beta < a_i <\beta \}$ такое, что

1) (свойство дополнения) для каждого $a,$ $1\leq a<\beta$ число наборов вида $(\star,a,\star,\star)$ в $A$ равно числу наборов вида $(\star,-a,\star,\star);$ число наборов вида $(\star,\star,a,\star)$ равно числу наборов вида $(\star,\star,-a,\star);$ и наконец число наборов вида $(\star,\star,\star,a)$ равно числу наборов вида $(\star,\star,\star,-a).$

2) (требование максимальности) множество $B = \{ a_3 \beta^3 + a_2 \beta^2 + a_1 \beta + a_0 : (a_3, a_2, a_1, a_0)\in A\}$ имеет максимальную мощность.

3) (неоднозначность представления) для каждого набора $(a_3, a_2, a_1, a_0)\in A$ существует другой набор $(a'_3, a'_2, a'_1, a'_0)\in A$ такой, что $a_3 \beta^3 + a_2 \beta^2 + a_1 \beta + a_0 = a'_3 \beta^3 + a'_2 \beta^2 + a'_1 \beta + a'_0.$

ТАК?

[Alik]

Неа. "Формулировка возвращается" - дубль не последний.
Найти систему счисления по основанию \beta для которой
существует набор чисел \textit{n_S}=a_3\beta^3+{(-1)^i}a_2\beta^2+{(-1)^j}a_1\beta+{(-1)^k}a_0
где ($a_2, a_1, a_0)\in [0;\beta-1] максимальное $S должно быть четным.
Для каждого $S есть свои ($i, j, k, a_3)=0,1 так, что каждая из сумм
\sum i,\ \sum j,\ \sum k - четная и больше либо равна единице.

[maxal]

S - это индекс у чисел $n_S$. В каких пределах он изменяется?

Далее "есть свои" - сколько? Надо ли понимать под "своими" здесь понимается множество $N_S = \{ (i, j, k, a_3) : a_3\beta^3+{(-1)^i}a_2\beta^2+{(-1)^j}a_1\beta+{(-1)^k}a_0 = n_S \}$ ?
И что для каждого S, сумма элементов $N_S$ равна вектору $(0,0,0,\star)$ по модулю 2?

[Alik]

Чем дальше в лес, тем ближе вылез

Из вышеприведенного вытекает нижеследующее:
1) коэффициент $a_0 в любом из вариантов не изменяется
2) сумма коэффициентов $a_3+a_2+a_1 всегда больше нуля
3) количество различных представлений не превышает 8 (доказать)
4) для 5 в середине $a_3, a_2, a_1 получаются инверсией значений для 3
5) в остальных случаях $a_2, a_1 для 5 получены сдвигом по кольцу вверх
Есть также связь между коэффициентами $a_3, a_2, a_1, a_0 и значениями $i, j, k

[Alik]

О неоднозначности в разложении Цекендорфа здесь
http://www.trinitas.ru/rus/doc/0232/100a/02320049.htm
Статья Бергмана "A number system with an irrational base"
http://www.ee.bgu.ac.il/~kushnero/Bergman/tau.pdf
Про интересные свойства простых чисел по ссылкам ниже
http://kvant.mccme.ru/1977/03/mnogo_bit ... ichego.htm
http://mathworld.wolfram.com/GoldbachConjecture.html