Постоянная Чемпернауна

Постоянная Чемпернауна — трансцендентная действительная константа, чьё разложение на десятичные дроби обладает определёнными важными свойствами. Названа в честь английского экономиста и математика Дэвида Чемпернауна (англ. D. G. Champernowne), который опубликовал о ней работу в 1933 году будучи студентом^[1].

Для десятичной системы счисления, данное число, обозначаемое обычно как $C_{10}$ , определяется как конкатенация следующих друг за другом положительных целых чисел^[2]:

0{,}12345678910111213141516\dots

Постоянная Чемпернауна также может быть сконструирована в других системах счисления похожим способом. К примеру:

C_{2}=0{,}11011100101110111\dots _{2}

C_{3}=0{,}12101112202122\dots _{3}

Постоянные Чемпернауна могут быть выражены в точности как бесконечный ряд:

C_{m}=\sum _{n=1}^{\infty }{\frac {n}{10_{b}^{{\big (}{\sum }_{k=1}^{n}\left\lceil \log _{10_{b}}(k+1)\right\rceil {\big )}}}}

где $\lceil {x}\rceil$ — округление $x$ вверх, $10_{b}^{~x}=b^{x}$ в десятичной системе счисления, $\log _{10_{b}}(x)=\log _{b_{10}}(x)$ и $b$ — система счисления для постоянной.

Примечания

↑ Чемпернаун, 1933.
↑ последовательность A033307 в OEIS

Литература

D. G. Champernowne. The construction of decimals normal in the scale of ten (англ.) // J. London Math. Soc. — 1933. — Vol. 8, iss. 4. — P. 254–260. — doi:10.1112/jlms/s1-8.4.254.

Похожие исследовательские статьи

Систе́ма счисле́ния — символический метод записи чисел, представление чисел с помощью письменных знаков.

<span class="mw-page-title-main">Сложение</span> математическая операция

Сложе́ние (прибавле́ние) — одна из основных бинарных математических операций двух аргументов (слагаемых), результатом которой является новое число (сумма), получаемое увеличением значения первого аргумента на значение второго аргумента. То есть каждой паре элементов $\text{[math]}$ из множества $\text{[math]}$ ставится в соответствие элемент $\text{[math]}$ , называемый суммой $\text{[math]}$ и $\text{[math]}$ . Это одна из четырёх элементарных математических операций арифметики. Приоритет её в обычном порядке операций равен приоритету вычитания, но ниже, чем у возведения в степень, извлечения корня, умножения и деления. На письме сложение обычно обозначается с помощью знака «плюс»: $\text{[math]}$ .
Сложение возможно, только если оба аргумента принадлежат одному множеству элементов. Так, на картинке справа запись $\text{[math]}$ обозначает три яблока и два яблока вместе, что в сумме даёт пять яблок. Но нельзя сложить, например, 3 яблока и 2 груши.

Двои́чная систе́ма счисле́ния — позиционная система счисления с основанием 2. Благодаря непосредственной реализации в цифровых электронных схемах на логических вентилях, двоичная система используется практически во всех современных компьютерах и прочих вычислительных электронных устройствах.

В математике, целая часть вещественного числа $\text{[math]}$ — округление $\text{[math]}$ до ближайшего целого в меньшую сторону. Целая часть числа также называется антье, или пол. Наряду с полом существует парная функция — потолок — округление $\text{[math]}$ до ближайшего целого в большую сторону.

Десяти́чная систе́ма счисле́ния — позиционная система счисления по целочисленному основанию 10. Одна из наиболее распространённых систем. В ней используются цифры 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, называемые арабскими цифрами. Предполагается, что основание 10 связано с количеством пальцев на руках у человека.

Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Леонардом Максом Адлеманом в 1979 году. Леонард Макс Адлеман — американский учёный-теоретик в области компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии. Он известен как соавтор системы шифрования RSA и ДНК-вычислений. RSA широко используется в приложениях компьютерной безопасности, включая протокол HTTPS.

Нормальное число — всякое действительное число, в записи которого в заданной $\text{[math]}$ -ричной системе счисления произвольная группа из $\text{[math]}$ последовательных цифр встречается с одной и той же асимптотической частотой, равной $\text{[math]}$ для каждого $\text{[math]}$ .

Позиционная систе́ма счисле́ния — система счисления, в которой значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда) относительно десятичного разделителя. Позиционные системы по сравнению с другими позволяют существенно упростить алгоритмы выполнения арифметических операций и ускорить вычисления. Их создание и распространение сыграли большую роль в развитии точных наук — математики, астрономии и физики.

Не́га-позицио́нная систе́ма счисле́ния — позиционная система счисления с отрицательным основанием. Особенностью таких систем является отсутствие знака перед отрицательными числами и, следовательно, отсутствие правил знаков. Всякое число любой из нега-позиционных систем, отличное от $\text{[math]}$ , с нечётным числом цифр — положительно, а с чётным числом цифр — отрицательно. Часто число в нега-позиционной системе требует для записи на одну цифру больше, чем то же число в системе с положительным основанием. Обычно название нега-позиционной системы состоит из приставки нега- и названия соответствующей системы счисления с положительным основанием; например, нега-десятичная (b = −10), нега-троичная (b = −3), нега-двоичная (b = −2) и другие.

Алгоритм Чена — алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов. Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени $\text{[math]}$ . Заворачивание по Джарвису требует перебора всех точек для каждой из $\text{[math]}$ точек выпуклой оболочки, что в худшем случае занимает $\text{[math]}$ . Назван по имени Тимоти М. Чана.

Метод факторизации Ферма — алгоритм факторизации нечётного целого числа $\text{[math]}$ , предложенный Пьером Ферма (1601—1665) в 1643 году.

Умножение Карацубы — метод быстрого умножения, позволяющий перемножать два $\text{[math]}$ -значных числа с битовой вычислительной сложностью $\text{[math]}$ .

Длинная арифметика — выполняемые с помощью вычислительной машины арифметические операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, с использованием базовых аппаратных средств работы с числами меньших порядков. Частный случай — арифметика произвольной точности — относится к арифметике, в которой длина чисел ограничена только объёмом доступной памяти.

ECDLP (Elliptic Curve Discrete Logarithm Problem) — задача дискретного логарифмирования в группе точек эллиптической кривой.

Разложение Энгеля положительного вещественного числа x — это единственная неубывающая последовательность положительных натуральных чисел $\text{[math]}$ , таких что

\text{[math]}

Алгори́тм Ка́ргера — в информатике и теории графов является вероятностным алгоритмом, позволяющим найти минимальный разрез связного графа. Алгоритм изобретен Девидом Каргером и опубликован в 1993 году.

Постоянная Коупленда — Эрдёша — вещественное число, строящееся как конкатенация «0,» со сцепленной последовательностью возрастающих простых чисел в десятичной записи:

0,235711131719232931374143…

Тест ассоциативности — проверка бинарной операции на ассоциативность. Наивная процедура проверки, заключающаяся в переборе всех возможных троек аргументов операции, требует $\text{[math]}$ времени, где $\text{[math]}$ — размер множества, над которым определена операция. Ранние тесты ассоциативности не давали асимптотических улучшений по сравнению с наивным алгоритмом, однако позволяли улучшить время работы в некоторых частных случаях. Например, Роберт Тарьян в 1972 году обнаружил, что предложенный в 1949 году тест Лайта позволяет выполнить проверку за $\text{[math]}$ , если исследуемая бинарная операция обратима. Первый вероятностный тест, улучшающий время работы с $\text{[math]}$ до $\text{[math]}$ , был предложен в 1996 году Шридхаром Раджагопаланом и Леонардом Шульманом. В 2015 году был предложен квантовый алгоритм, проверяющий операцию на ассоциативность за время $\text{[math]}$ , что является улучшением по сравнению с поиском Гровера, работающим за $\text{[math]}$ .

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

Алгоритм Тоома — Кука, иногда упоминаемый как Tоом-3 — это алгоритм умножения больших чисел, названный именами Андрея Леоновича Тоома, предложившего новый алгоритм с низкой сложностью и Стивена Кука, более ясно его описавшего.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.