# Non-Uniform Shuffling

2020-01-25, post № 224

C, Haskell, mathematics, programming, #algorithms, #false implementation, #probability theory

A shuffle of a finite sequence of length 𝑛 of distinguishable elements refers to an algorithmic process which — modulo pseudo-randomness — can be modeled as a random variable uniformly distributed on the permutations $\mathbb{S}_n$.
However, most pseudo-random entropy sources provide only a pseudo-uniformly distributed realization of $\mathbb{F}_2^\mathbb{N}$, leading to the necessity of finding an algorithmic transformation process if one wishes to achieve a shuffle.
In the following, I will assume that a transforming process to a family of independent and uniformly on $\{1..n\}$ distributed random variables is already present for any $n\in\mathbb{N}$.

One naive and seemingly correct (it is not) approach is to traverse the given sequence, uniformly swapping the current entry with another one, i. e.

void falseShuffle(uint64_t *arr, size_t len) {
for (size_t j = 0; j < len; j++)
swap(arr, j, unif(len)); }

as an exemplary C implementation where $\texttt{unif}(n)$ is independent and uniformly distributed on $\{0..n-1\}$.

Yet, even though sensible on first sight, the above defined random variable is only in the most trivial cases uniformly distributed and — as empirical evidence suggests, see below — horrendously non-uniformly distributed otherwise.
To prove the non-uniformity postulated above, I first present the following number-theoretic result.
Claim. In only three trivial cases does the factorial of a natural number divide its tetration; formally Proof. Let $n\in\mathbb{N}_{>2}$ be a natural number larger than two. By the definition of the factorial, $\prod_{p is evident. Assume $n!\mid n^n$. Adhering to the uniqueness of prime factorizations, $\prod_{p follows. Observe that $n-1>1$ has to be prime since $\forall\,p, implying $n-1\mid\prod_{p which cannot hold for 𝑛 > 𝟤.
Proof. Now suppose, falseShuffle was indeed non-trivially distributed uniformly. Without loss of generality, all involved probability spaces were finite. Then there had to exist a surjection from this algorithm’s entropic state to $\mathbb{S}_n$ with fibers of the same finite cardinality, implying $n!\mid n^n$. By the above proven claim, 𝑛 < 𝟥 followed, making the distribution trivial.

One possible reason for the surprising nature of this non-uniformity is the striking source code resemblance to a correct implementation, i. e.

void shuffle(uint64_t *arr, size_t len) {
for (size_t j = 0; j < len; j++)
swap(arr, j, j + unif(len - j)); }

as an exemplary C implementation which can be inductively shown to resemble the same structure as $\mathbb{S}_n$, in each step sprinkling in some uniform randomness and thus being itself uniformly distributed.

To see just how non-uniform falseShuffle is, I have calculated its discrete density for 𝑛 = 𝟦:

[       |                ]
[   |   |||              ]
[   |   |||              ]
[   |   |||              ]
[   ||  ||||||| ||       ]
[||||| |||||||| |||    ||]
[|||||||||||||||||| || ||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
[||||||||||||||||||||||||]
n = 4

If it was uniformly distributed, the discrete density would look like a rectangle; [||||| ... |||||]. Further plots for 𝟢 ≤ 𝑛 ≤ 𝟨 are shown in non-uniform-shuffling.txt (Unlanguaged).

Source code for the analysis and plotting: non-uniform-shuffling.hs (Unlanguaged). Empirical evidence of non-uniformity: non-uniform-shuffling.c (Unlanguaged).

# Generating the Prouhet-Thue-Morse sequence in brainfuck

2019-12-28, post № 223

brainfuck, mathematics, programming, #recursive, #Thue-Morse sequence

[-]<<<[-]<<<[-]<<<[-]<<<[-]<<<[-]>>>>>>>>>>>>>>>>>[-]++++++++++++++++++++++++++++++++++++++++++++++++.[-]<[-]>>[-]<[-<+>>+<]>[-<+>]<<<<<[-]>>>[<<<+>>>-]<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>>[-]+[>[-]+[<<[-]<<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[-]>>>>>>>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>>[>>>>>>>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>>]<<[>>>+<<<-]>>>>>>[-]<<<[->>>+<<<][-]>>>>[-]<[-<<<+>>>>+<]>[-<+>]<<<<<<<<<<[-]>>>>>>[<<<<<<+>>>>>>-]<<<<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>>>>>>>>[-]+<[->[-]<]>[-<+>]<<<<[-]>>>>[-]<[-<<<+>>>>+<]>[-<+>]<<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>>>>>>>[-]<<<<<<<<<<<<[-]>>[<<+>>>>>>>>>>>>+<<<<<<<<<<-]<<[>>+<<-]>>>>>>>>>>>>>>[-]<<[->>+<<]>>][-]+[<<[-]<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[-]>>>>>>>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>>[>>>>>>>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>>]<<[>>>>>>+<<<<<<-]>>>>>>>>>[-]<<<[->>>+<<<][-]>>>>[-]<[-<<<+>>>>+<]>[-<+>]<<<<<<<[-]>>>[<<<+>>>-]<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>[-]<<<<<<<<<<<<<<<[-]>>[<<+>>>>>>>>>>>>>>>+<<<<<<<<<<<<<-]<<[>>+<<-]>>>>>>>>>>>>>>>>>[-]<<[->>+<<]>>][-]+[<<[-]<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[-]>>>>>>>[-]<<<<<<<<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>>[>>>>>>>[-]<<<<<<<<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>>]<<[>>>>>>>>>+<<<<<<<<<-]>>>>>>>>>>>>[-]<<<[->>>+<<<]>>>>[-]++++++++++++++++++++++++++++++++++++++++++++++++>[-]<<[->+>+<<]>>[-<<+>>]<.<<<<[-]>>>>[-]<[-<<<+>>>>+<]>[-<+>]<<<<<<<[-]>>>[<<<+>>>-]<<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<[<<<<<<<<<<<[-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<<<]<[-]<[>+<-]>>+<<<<<<<<<[-][-]>>>>>>>>>[>>>>>>>>>]>[-]<<<<<<<<<<<<<<<<<<[-]>>[<<+>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<-]<<[>>+<<-]>>>>>>>>>>>>>>>>>>>>[-]<<[->>+<<]>>]<]

Try it online.

# Factoids #1

2019-11-30, post № 222

mathematics, #F2, #OEIS

## IV) Commutative, non-associative operations

For any natural number 𝑛, let $\mathrm{Op}_n:=\left\{\star:\mathbb{Z}^2_n\to\mathbb{Z}_n\right\}$ denote the set of all operations on a set of that order. An operation shall be called commutative iff $\mathrm{commut}(\star):\Leftrightarrow\forall\,x,y\in\mathbb{Z}_n:x\star y=y\star x$ and be called associative iff $\mathrm{assoc}(\star):\Leftrightarrow\forall\,x,y,z\in\mathbb{Z}_n:x\star(y\star z)=(x\star y)\star z$ holds.

With the above defined, one may study $\mathrm{CnA}_n:=\{\star\in\mathrm{Op}_n:\mathrm{commut}(\star)\land\lnot\mathrm{assoc}(\star)\}$. For 𝑛 = 𝟤, this set is nonempty for the first time, containing a manageable two elements, by name However, based on the superexponential nature of $\#\mathrm{Op}_n=\#\mathbb{Z}_n^{\mathbb{Z}_n^2}=\#\mathbb{Z}_n^{{\#\mathbb{Z}_n}^2}=n^{n^2}$, the sequence $\mathrm{A079195}_n:=\#\mathrm{CnA}_n$ likely also grows rather quickly, OEIS only listing four members; Based on this limited numerical evidence, I would suspect the commutative yet non-associative operations to be rather sparse, i. e. Analysis source: factoids-1_operations.hs

(Non-)commutative and (non-)associative operations have also been studied nearly twenty years ago by Christian van den Bosch, author of OEIS sequence A079195. Unfortunately, their site appears to be down, which is where they hosted Closed binary operations on small sets (resource found on web.archive.org).

## V) Arbitrary polynomial extremum difference

Let 𝜀 > 𝟢 be an arbitrary distance, define $g:=-4x^4-x^3+8x^2+3x-4$. Then $f:=\epsilon\cdot 4^{-1}\cdot g$ has two local maxima at - 𝟣 and 𝟣, whose vertical distance is 𝜀.

## V) Digit sum roots

It holds that $\mathrm{ds}_{10}(108^{12})=108$.

# Extending A056154

2019-11-02, post № 221

mathematics, #discovery, #OEIS, #paper, #ternary

Five weeks of work including over six days of dedicated number crunching come to fruition as the thirteenth member of OEIS sequence A056154 is published, Sequence A056154 is defined as binary exponents which have a ternary representation invariant under endomorphic addition modulo permutation, more formally Due to the exponentially defined property, testing a given $p\in\mathbb{N}$ for membership quickly becomes non-trivial, as the trits of $2^p$ enter the billions.
As an example, $2^{49\,094\,174}$ requires 30’974’976 trits. Assuming three thousand trits per page and two hundred pages per book, a ternary print-out of said number would require fifty-two books, filling a few book shelves.

For a discussion of the methodology I used to perform the search which lead to the discovery of $\mathrm{A056154}(13)$, I refer to my paper Extending A056154.

# A325902

2019-10-05, post № 220

mathematics, #factorization, #integer, #OEIS, #sequence

Fifty is a peculiar integer.
When looking at its neighbors — the largest integer strictly beneath and the smallest strictly above —, more specifically their prime factorization, one finds Notably, there exists a partition of the neighbor’s factors into two multisets such that both parts’ sums equal another.

Positive integers with the above described property can be found in my most recent addition to the OEIS: sequence A325902.

# Digit Sums

2019-09-07, post № 219

mathematics, #base ten, #factorid, #Jack Reacher

Interessant war es auch, drei aufeinanderfolgende Zahlen zu nehmen, von denen die größte durch drei teilbar sein musste, sie zu addieren und aus dem Ergebnis so lange die Quersumme zu bilden, bis eine einstellige Zahl übrig blieb. Diese Zahl war immer sechs.
— Child, Lee: Der Anhalter. München: Blanvalet, 2015; p. 73

Jack Reacher’s at most tangentially to interpreting the sergeant’s reply related base ten factoid’s formal form is where $\mathrm{fds}_{10}$ represents the final digit sum in base ten.

A proof of the above claim together with the underlying digit sum results is presented in digit-sums.pdf (source: digit-sums.tex).

# Short brainfuck Primes

2019-08-10, post № 218

brainfuck, programming,

>[-]+>>[-]++>[-]<<<[>[-]+>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-][-]+[>>>>[-]<[-]<<<<<[>>>>>>+<+<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<[-]+>[<->[-]]<[<<<->>>[-]]<<<<->>>>>[-]<[-]<<<<<<[>>>>>>>+<+<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]>[-]<[-]<<<<<<[>>>>>>>+<+<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-][-]>[-]>[-]>>[-]<[-]<[>>+<+<-]>>[<<+>>-]>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]>[-]<[-]<<<<<<<<<<<[>>>>>>>>>>>>+<+<<<<<<<<<<<-]>>>>>>>>>>>>[<<<<<<<<<<<<+>>>>>>>>>>>>-]>[-]<[-]<<<<<<<<[>>>>>>>>>+<+<<<<<<<<-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<[-]>>>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<<<[-]+>>>>>[-]]<-<-]>[-]<[-]<<<<<<<<<<<[>>>>>>>>>>>>+<+<<<<<<<<<<<-]>>>>>>>>>>>>[<<<<<<<<<<<<+>>>>>>>>>>>>-]>[-]<[-]<<<<<<<<[>>>>>>>>>+<+<<<<<<<<-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<[-]+>>[>-<-]>>>[-]<[-]<[>>+<+<-]>>[<<+>>-]<[<<<<->>>>[-]]<[-]<[-]<<<<<<<<<<<<[>>>>>>>>>>>>>+<+<<<<<<<<<<<<-]>>>>>>>>>>>>>[<<<<<<<<<<<<<+>>>>>>>>>>>>>-]>[-]<[-]<<<<<<<<<[>>>>>>>>>>+<+<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-][-]+<[<<<<+>>>>>-<[-]]>[>>[-]<[-]<<<<[>>>>>+<+<<<<-]>>>>>[<<<<<+>>>>>-]<[<<<[<<<+>>>-]>>>[-]]<-]<<<<[-]+<[>-<[-]]>[<+>-]<[>>[-]<[-]<<<<<<<<<[>>>>>>>>>>+<+<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<[>>>[-]<[-]<<<<<<<[>>>>>>>>+<+<<<<<<<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<<[-]+>[<->[-]]<[<<<<<->>>>>[-]]<<<<<<->>>>>-]>[-]<[-]<<<<<<<<[>>>>>>>>>+<+<<<<<<<<-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<[<<<<->>>>-]<<<+>>>>>[-]<[-]<<<<[>>>>>+<+<<<<-]>>>>>[<<<<<+>>>>>-]<<[-]+>[<->[-]]<[<<+>>[-]]<[-]>>[-]<[-]<[>>+<+<-]>>[<<+>>-]>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]>[-]<[-]<<<<<<<<<<<[>>>>>>>>>>>>+<+<<<<<<<<<<<-]>>>>>>>>>>>>[<<<<<<<<<<<<+>>>>>>>>>>>>-]>[-]<[-]<<<<<<<<[>>>>>>>>>+<+<<<<<<<<-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<<[-]>>>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<<<[-]+>>>>>[-]]<-<-]>[-]<[-]<<<<<<<<<<<[>>>>>>>>>>>>+<+<<<<<<<<<<<-]>>>>>>>>>>>>[<<<<<<<<<<<<+>>>>>>>>>>>>-]>[-]<[-]<<<<<<<<[>>>>>>>>>+<+<<<<<<<<-]>>>>>>>>>[<<<<<<<<<+>>>>>>>>>-]<<<<[-]+>>[>-<-]>>>[-]<[-]<[>>+<+<-]>>[<<+>>-]<[<<<<->>>>[-]]<[-]<[-]<<<<<<<<<<<<[>>>>>>>>>>>>>+<+<<<<<<<<<<<<-]>>>>>>>>>>>>>[<<<<<<<<<<<<<+>>>>>>>>>>>>>-]>[-]<[-]<<<<<<<<<[>>>>>>>>>>+<+<<<<<<<<<-]>>>>>>>>>>[<<<<<<<<<<+>>>>>>>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-][-]+<[<<<<+>>>>>-<[-]]>[>>[-]<[-]<<<<[>>>>>+<+<<<<-]>>>>>[<<<<<+>>>>>-]<[<<<[<<<+>>>-]>>>[-]]<-]<<<<[-]+<[>-<[-]]>[<+>-]<]<<<<<[-]+>>>>>>[-]<[-]<<<<[>>>>>+<+<<<<-]>>>>>[<<<<<+>>>>>-]<[<<<<<[-]>>>>>[-]]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<[<<<<<[-]>>>>>[-]]<<<<<<[-]+>>>>[-]<[-]<<<<<[>>>>>>+<+<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<[-]+>[<->[-]]<[>>>[-]<[-]<<<<<[>>>>>>+<+<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<[-]+>[<->[-]]<[<<<[-]>>>[-]]<[-]]>[-]<[-]<[>>+<+<-]>>[<<+>>-]<[<<->>[-]]<<]<<->>[-]+<<[<<<->>>>>-<<[-]]>>[<[<<<<->>>>[-]]>-]<[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<[>>>[-]++++++++++++++++>>[-]<[-]<<<<<[>>>>>>+<+<<<<<-]>>>>>>[<<<<<<+>>>>>>-]<<<<[-]>>>>>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-][-]+<[>-<[-]]>[<+>-]<[>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<[<<->>-]<<<<<+>>>>>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-][-]+<[>-<[-]]>[<+>-]<]<<<[-]>>[<<+>>-]<[-]++++++++++++++++++++++++++++++++++++++++++++++++>[-]+++++++++>>>[-]<[-]<<<<<[>>>>>>+<+<<<<<-]>>>>>>[<<<<<<+>>>>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-]>[-]<[-]<[>>+<+<-]>>[<<+>>-]<[<<<+++++++>>>[-]]<[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<[<+>-]<.[-]++++++++++++++++++++++++++++++++++++++++++++++++>[-]+++++++++>>>[-]<[-]<<<<[>>>>>+<+<<<<-]>>>>>[<<<<<+>>>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-]>[-]<[-]<[>>+<+<-]>>[<<+>>-]<[<<<+++++++>>>[-]]<[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<[<+>-]<.[-]++++++++++++++++>>[-]<[-]<<<<<<[>>>>>>>+<+<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<<<<[-]>>>>>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-][-]+<[>-<[-]]>[<+>-]<[>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<[<<->>-]<<<<<+>>>>>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-][-]+<[>-<[-]]>[<+>-]<]<<<[-]>>[<<+>>-]<[-]++++++++++++++++++++++++++++++++++++++++++++++++>[-]+++++++++>>>[-]<[-]<<<<<[>>>>>>+<+<<<<<-]>>>>>>[<<<<<<+>>>>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-]>[-]<[-]<[>>+<+<-]>>[<<+>>-]<[<<<+++++++>>>[-]]<[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<[<+>-]<.[-]++++++++++++++++++++++++++++++++++++++++++++++++>[-]+++++++++>>>[-]<[-]<<<<[>>>>>+<+<<<<-]>>>>>[<<<<<+>>>>>-]>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<<[-]>[>>>>[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<<[-]+>[<->[-]]<[<<<[-]+>>>[-]]<-<-]>[-]<[-]<[>>+<+<-]>>[<<+>>-]<[<<<+++++++>>>[-]]<[-]<[-]<<[>>>+<+<<-]>>>[<<<+>>>-]<[<+>-]<.<<[-]++++++++++.<[-]]<<+>>>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<[-]+>[<->[-]]<[<+>[-]]<<<<[-]+>>>>>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<[-]+>[<->[-]]<[>>>[-]<[-]<<<[>>>>+<+<<<-]>>>>[<<<<+>>>>-]<<[-]+>[<->[-]]<[<<<<<[-]>>>>>[-]]<[-]]<<<<]

Try it online.

# Mandelbrot set sketch in Scratch

2019-07-13, post № 217

art, mathematics, programming, #fractal

Despite my personal disbelieve in and dislike of the colored blocks dragging simulator 3, I nevertheless wanted to extract functionality other than the hardcoded cat mascot path tracing from the aforementioned software; one of the most efficient visual result to build effort ratio yields a simple plot of the Mandelbrot set, formally known as where the iterator is defined as The render resolution is kept at a recognizable minimum as not to overburden the machine tasked with creating it.
Source: mandelbrot-set-sketch-in-scratch.sb3 (Unlanguaged) # Factoids #0

2019-06-15, post № 216

mathematics, #algebra, #rings

## I) Unit polynomials with non-vanishing degree $2t+1\in\mathbb{Z}_4[t]$ is its own multiplicative inverse, showing that $R[t]^*=R^*$ does not hold in a general commutative Ring with one.

This phenomenon is uniquely characterized by the following equivalence: Proof. Negated replication. Let $R\not\owns f=\sum_{i=0}^n\alpha_it^i\in R[t]^*,\alpha_n\neq 0$ be a unit polynomial of non-vanishing degree $n\geq 1$. Let $g=\sum_{j=0}^m\beta_jt^j\in R[t]^*,\beta_m\neq 0$ denote its multiplicative inverse, i. e. $f\cdot g=1$.
Claim. The polynomial $g$ has non-vanishing degree $m\geq 1$.
Proof. Suppose $g\in R$. Since $f\cdot g=\sum_{i=0}^n(\alpha_i\cdot g)t^i$, it follows from $\alpha_n\cdot g=0$ that $g$ is a zero divisor. However, at the same time $a_0\cdot g=1$ implies that $g$ is a unit, arriving at a contradiction.
Since both $n,m\geq 1$, one concludes $\exists 1\leq k\leq m$ as well as $\alpha_n\cdot\beta_m=0$.
Existence of the desired ring elements $a,b$ is assured by the following construction.
• Let $k=1\nearrow m$ rise discretely.
• If $a:=\alpha_n\beta_{m-k}\neq 0$, implying $b:=\sum_{i=1}^k\alpha_{n-i}\beta_{m-k+i}\neq 0$, holds, since the construction arrived at this point, one finds • The above condition is met for at least one $1\leq k\leq m$, since otherwise $k=m$ would imply $\alpha_n\beta_{m-m}=0$, which is impossible since $\alpha_n\neq 0$ and $\beta_0$ is a unit element.
By construction, $0\neq a,b$ as well as $a+b=0$ are given.
Negated implication. Setting $f:=at+1$, $g:=bt+1$, one calculates showing $R\not\owns f,g\in R[t]^*$.

# Mostly Misaligned Mirrors

2019-05-18, post № 215

mathematics, PIL, programming, Python, #paths, #random, #simulation, #stochastic

Recently, my stochastic professor introduced me to a problem he has been pondering for over two decades: on the two-dimensional integer lattice $\mathbb{Z}^2$ one shall flip a three-sided coin for each point and uniformly place one of three mirrors, $\{\diagup,\,\cdot\,,\diagdown\}$, where $\,\cdot\,$ denotes not placing a mirror. After having populated the world, one picks their favorite integer tuple and points a beam of light in one of the four cardinal directions. With what probability does the light fall into a loop, never fully escaping? A cycle which includes the origin.

# krrp

2019-04-20, post № 214

C, krrp, programming, #2018

A project of epic proportions has come to a close. Yesterday, the 19th of April 2019, saw the first public release of my new programming language, krrp.

As of the 24th of April 2019, krrp is kindly included in the TIO language collection, making krrp interpretation available from within the web. Great thanks go out to TIO for providing this service.

krrp is a functional, dynamic, interpreted and (theoretically) Turing-complete esolang implemented only using standard C. As such, on top of designing the actual language, any data structures, memory management and general auxiliary functionality deviating from the lacking capabilities offered by C had to be home-brewed and hand-crafted. A time-consuming task — I have been working on this language for the past year. However, it gives the language a certain purity, as its high-level functional approach rests firmly and closely on the state-changing, mutable and segmentation-faulting depths that are the C language.