Число как сумма ряда или элемент последовательности

[wrest]

slavav в сообщении #1354101 писал(а):

Кто будет чаще выигрывать, если $N$ растёт неограниченно?

Выиграет zip. Или rar. Ну или, на худой конец, tar

[slavav]

wrest в сообщении #1354123 писал(а):

slavav в сообщении #1354101 писал(а):

Кто будет чаще выигрывать, если $N$ растёт неограниченно?

Выиграет zip. Или rar. Ну или, на худой конец, tar

Нет, не выиграет. Архиваторы сжимают лишь малое число текстов. Большинство текстов несжимаемо. Об этом в статье "Колмогоровская сложность".

[pogopogo]

mihaild в сообщении #1354117 писал(а):

А что это значит? Например берете число $100$, следующим пишете число $0$ - это подходит или нет?

Например, я хочу получить число $143093...23223$ в итоге (число, для записи которого, надо очень много знаков).
Представляю его как сумму двух предыдущих. Предыдущие, тоже, как сумму предыдущих и так до нуля или около того. Считаю количество шагов, которое затратил.

Теперь это длинное число я могу записать, положим, как $-5$,$15$,$20$....[Условно 6000 элемент этой последовательности]. Так и напишу - искомое число - 6000ый элемент последовательности выше.

А может, буду считать сумму членов такой последовательности и представлю это число, как 3000ый член последовательности + 9999.

[slavav]

pogopogo, вы придумываете нотацию для записи больших чисел. Но никакая нотация не будет (намного) компактнее десятичной записи чисел.

[arseniiv]

Плюс в любом случае надо или общий вид требований написать, или остановиться на одном конкретном варианте. А так вопрос недоопределён, и выписывать ответы на всевозможные его конкретизации — нужны время и мотивация.

[Ioda]

slavav
в сообщении #1354133 писал(а):

Но никакая нотация не будет (намного) компактнее десятичной записи чисел.

Стрелочная нотация Кнута поспорит.

[arseniiv]

С чем конкретно она поспорит? То, что достаточно коротким записям в ней будут соответствовать громадные числа в позиционной — это ведь только половина дела. Надо представить все числа.

[mihaild]

Никакя нотация не будет компактнее в среднем. Понятно, что есть нотации, которые позволяют записывать некоторые числа сильно короче десятичной записи.

[wrest]

arseniiv в сообщении #1354144 писал(а):

Надо представить все числа.

Никто не обнимет необъятное.

[Student2018]

pogopogo в сообщении #1354127 писал(а):

Например, я хочу получить число $143093...23223$ в итоге (число, для записи которого, надо очень много знаков). Считаю количество шагов, которое затратил. Теперь это длинное число я могу записать, положим, как $-5$,$15$,$20$....[Условно 6000 элемент этой последовательности]. Так и напишу - искомое число - 6000ый элемент последовательности выше. А может, буду считать сумму членов такой последовательности и представлю это число, как 3000ый член последовательности + 9999.

Тогда для каких-то чисел номер элемента в последовательности будет намного короче самого числа, для каких-то немного короче самого числа, а для каких-то намного длиннее самого числа. То есть где-то вы выиграете, а где-то обязательно проиграете. В среднем же, из-за энтропии вы все равно немного проиграете, и записать число короче чем оно есть, даже на самую малость - не получится. Выиграть тут можно только если будут записываться не все числа из какого-то диапазона, а только некоторые из них. Только тогда появляется возможность представить их в более компактном виде.

Допустим, вы хотите придумать такой алгоритм, который позволит записать все натуральные числа от 1 до 2^{100} в более компактном виде. В процессе работы этот суперадаптивный, подстраивающийся под конкретное число, алгоритм, будет генерировать запись этого числа в своем собственном формате. На запись любого числа в исходном формате потребуется 100 bit памяти. Этого достаточно чтобы описать 2^{100} различных элементов. Допустим, что алгоритм найдет способ записать любое число из заданного диапазона, затратив на запись 99 bit памяти. Но этого достаточно лишь для описания 2^{99} элементов, что значительно меньше количества элементов исходного диапазона. Таким образом, в общем случае, сэкономить даже 1 bit информации - не получится.

[wrest]

Student2018 в сообщении #1354420 писал(а):

Допустим, вы хотите придумать такой алгоритм, который позволит записать все натуральные числа от $1$ до $2^{100}$ в более компактном виде.

$2^{100}$ число очень большое, с ним трудно натурно поэксперементировать.
Вот что я сделал. Создал текстовый файл, в котором в каждой строчке выписал числа от $0$ до $2^{16}-1=65535$
Сохранил файл под именем dd.txt, размер его составил $382 106$ байт.
Затем заархивировал его rar-ом, и размер, получился как вы думаете какой? По вашему, на каждое число надо $16$ бит, чисел $2^{16}$ итого $128$ кибибайт. Но нет, rar ужал этот файл до размера $8165$ байт, т.е. в $1/16$ примерно от размера который вы предсказываете.

[mihaild]

Student2018 в сообщении #1354420 писал(а):

а для каких-то намного длиннее самого числа

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

wrest, вы тут проверяете, что можно сделать с записью всех чисел от $0$ до $n$ (одной строчкой). Понятно, что строчки такого вида можно описывать очень компактно.
А речь про то, чтобы записать каждое число компактно. Попробуйте сделать несколько файлов, в которых записано только одно число, и посмотреть на их длину.

[wrest]

mihaild в сообщении #1354484 писал(а):

вы тут проверяете, что можно сделать с записью всех чисел от $0$ до $n$ (одной строчкой).

Ну да, в соответствии с:

Student2018 в сообщении #1354420 писал(а):

Допустим, вы хотите придумать такой алгоритм, который позволит записать все натуральные числа от $1$ до $2^{100}$ в более компактном виде

-- 16.11.2018, 15:19 --

mihaild в сообщении #1354484 писал(а):

А речь про то, чтобы записать каждое число компактно. Попробуйте сделать несколько файлов, в которых записано только одно число, и посмотреть на их длину.

Сделать 65536 файлов, в каждом по одному числу, и сложить в один архив?
Ну это муторно, и очень много оверхеда надо хранить (имя каждого файла, например).

-- 16.11.2018, 15:23 --

mihaild
Я понимаю о чем речь, просто примеры тут приводят не те, кмк

Уже выше сказано, что нужен какой-то баланс между мощностью алфавита и сообщением.
Архиваторы, типа того же rar-а, как раз этого баланса и достигают (почти), делая новый алфавит под каждое сообщение.

[mihaild]

Тут конфликт обозначений. Правильное утверждение (скорее всего Student2018 его и имел в виду): пусть у нас есть некоторый способ записи чисел в алфавите $\{0, 1\}$, и $f(n)$ - длина записи числа $n$ относительно этого способа. Тогда $\forall N \exists n \leqslant N: f(n) \geqslant \log_2(N + 1)$.

-- 16.11.2018, 15:29 --

wrest в сообщении #1354487 писал(а):

Сделать 65536 файлов, в каждом по одному числу, и сложить в один архив?
Ну это муторно, и очень много оверхеда надо хранить (имя каждого файла, например).

Можно взять нормальный компрессор, который умеет сжимать блобы данных, а не только файлы.

wrest в сообщении #1354487 писал(а):

Архиваторы, типа того же rar-а, как раз этого баланса и достигают (почти), делая новый алфавит под каждое сообщение.

Алфавит тут как раз один и тот же: $\{0, 1\}$.
Существуют компрессоры, которые могут сжать некоторые данные. Не существует компрессора, который сжимает любые (или хотя бы "многие") данные.

[wrest]

mihaild в сообщении #1354493 писал(а):

Существуют компрессоры, которые могут сжать некоторые данные.

Ну да, мы же про числа.
Вот например мы говорим "на листе записаны подряд все натуральные числа до $2^{100}$" - мы сжали этот гигантский лист до менее чем 60 символов. Конечно, мы использовали при этом определения "натуральное число" и т.п., которые если разворачивать получится много.