Clandestine Endorsement

Clandestine Endorsement

Paradigm(s)	Declarative
Designed by	User:Hakerh400
Appeared in	2023
Computational class	Not applicable
Major implementations	Implemented
File extension(s)	.txt

Clandestine Endorsement is an esolang invented by User:Hakerh400 in 2023.

Overview

This language outputs the first $n$ digits of a specific infinite binary sequence $L$ define below.

Informally, the sequence $L$ is built up iteratively by trying to keep the equal distribution of all possible sublists. We start with the empty sequence and then we iteratively append bits so that the distribution of any possible sublist of length $n$ (for any $n$ smaller than the current length of the sequence) is as close to $2^{-n}$ as possible. When in doubt, we append $0$.

We start with the empty sequence and we append bit $0$. Now, if we append $0$, then $0$ will appear two times, while $1$ will not appear at all. On the other hand, if we append $1$, then both $0$ and $1$ will appear once, which is exactly the distribution we want. Therefore we append $1$ and now we have $01$. The next bit is $0$, because both $0$ and $1$ would give the same distribution "cost", so we choose $0$. How exactly the distribution cost is calculated is explained below (the function $R(l)$).

The real number $0.L$ in base $2$ (sequence $L$ treated as binary digits) is probably a normal number, since the construction of $L$ literally tries to keep the distribution of every possible sublist as close to $2^{-n}$ as possible.

Definitions

A sequence of type $T$ is a function $\alpha \mapsto T$ where $\alpha \leq \omega$ is an ordinal that represents the length of the sequence and $\omega$ is the smallest transfinite ordinal. Sequence is finite iff $\alpha <\omega$.

A list is a finite sequence. Empty list is denoted by $\epsilon$. Length of a list $l$ is denoted by $|l|$. List concatenation is represented by $+$.

Every list is a sublist of itself. If list $l_{1}$ is a sublist of $l$, then $l_{1}$ is also a sublist of any list obtained by inserting one element to the beginning or end of $l$.

The set of all sequences of bits of length $\alpha$ is represented as $\{0,1\}^{\alpha }$.

Function $C:\{0,1\}^{m}\times \{0,1\}^{n}\mapsto \mathbb {N}$ for $m,n\in \mathbb {N}$, denoted as $C(l_{1},l)$, represents the number of sublists $l_{1}$ in $l$. For any list $l$, $C(\epsilon ,l)=|l|+1$ and $C(l,l)=1$.

Function $R_{i}:\{0,1\}^{n}\mapsto \mathbb {R}$ is defined for all $i,n\in \mathbb {N}$ as

$R_{i}(l)=\sum _{l_{1}\in \{0,1\}^{i}}\left|C(l_{1},l)-{\frac {n-i+1}{2^{i}}}\right|$

Function $R:\{0,1\}^{n}\mapsto \mathbb {R}$ is defined for all $n\in \mathbb {N}$ as

$R(l)=\sum _{i=1}^{n-1}R_{i}(l)$

Sequence $L$ is the infinite sequence of bits whose every finite prefix $l+b$, where $b$ is a single bit, has the property that

$b=\displaystyle {\begin{cases}0,&R(l+0)\leq R(l+1)\\1,&{\text{otherwise}}\end{cases}}$

Syntax

Source code consists of number $n\in \mathbb {N}$. There is no input. The output is the prefix $l$ of $L$ such that $|l|=n$.

Example

Input: 1000

Output:

0101100111000101000011110101101110000100110100100011111001011101000001101100101011111000001011001100
0111011010011110001000101010011111101110010000001101010110000110010010111101101111000000100101001101
1111100110001001001110101000110101110111100000010101011010001110011111010000100011001101100011101001
0110110000011111110101000010111001001000011101100101001110001101110101111001000001011010100101011000
1000000011111111011001100111001010001011110100110000110111000100111101110100010000101011100001101001
1011010110010011111000110000000010111111010101001001100111100110101010100011101111100001000100101101
1011100111011000000111000101100011001011111010000010010001010010111111100110100001100011110110101110
1001000000011001010111101110011001000111100101010110110100010011101111111100001010000011000101101001
1000010011101110101001101100001111000111001000101110110101000000001000110111101011111011001001010100
0111110011100001011001101001010000111110111100100110001010110101100000111001111010001000110110111110

This represents the first thousand elements of sequence $L$.

Implementation

Implementation in Haskell