Sequence of programs that prints the next one with length growth being equal to π

Question

Challenge

• You must produce an infinite sequence of programs \$P_0, P_1, P_2,\$ ... such that each program \$P_n\$, when run, prints the exact source code of \$P_{n+1}\$ and then halts.

• Each program \$P_n\$ must take no input (no stdin, no command-line arguments) and may not inspect or read its own source code at runtime.

• Let \$l_n\$ be the length in characters of \$P_n\$. Define \$R_n = \frac{l_{n+1}}{l_n}\$. You must have

  a. $$\lim_{n\to\infty} R_n = \pi$$

  b. Convergence is linear with a constant factor \$\rho\$, where \0ドル < \rho < 1\$. That is, $$ \lim_{n\to\infty} \frac{|R_{n+1} − \pi|}{|R_n − \pi|} = \rho $$

• Scoring: Your score \$S = l_0\rho\$. Lower \$S\$ is better.

• Exactness is mandatory: all proofs must be fully exact. Floating-point approximations of pi are not allowed.

• Bryle Morga: @Rhaixer the ratio, in the limit, should exactly converge to π. So using floating points approximations of π wouldn't work
• Rhaixer: does the rate of convergence have to be constant?
• Kevin Cruijssen: @l4m2 Second bullet-point mentions "Each program should take no input", though. And unless I misunderstood something, it's all about the lengths of the programs outputting each other. Actually outputting \$\pi\$ therefore isn't necessary. It's the ratio of consecutive lengths of the programs that should converge into \$\pi\$.
• Bryle Morga: @JonathanAllan Yes. It is the ratio I forgot to mention. And no there's no difference
• Arnauld: Please include the clarifications in the challenge (we're not supposed to get them from the comments) and you should be good to go! Nice idea, BTW.

Answer 1

Python 3, Sympy, \86ドル\cdot\frac{1}{\pi}\approx27.37465\$

p='from sympy import*;p=%r;s=int(pi*len("%s"))*"3";print(p%%(p+"#",s))';print(p%(p,3))

Try it online!

Maybe a boring answer but it is an answer.

Explanation

We need some code that writes code so I started with the standard python quine

p='p=%r;print(p%%p)';print(p%p)

To this I then added a sympy import and a dummy string. Every iteration of the program then takes the length of this dummy string, multiplies it by \$\pi\$, rounds down to the nearest integer, and replaces the dummy string with a new string of that length. In this way, we are essentially multplying the entire program length by \$\pi\$ since the dummy string grows geometrically. Sympy is important here as it will compute as many digits of pi as are necessary to get an exact length.

The only other piece of code here then is this p+"#". This essentially extends the length of the surrounding code by 2 every iteration. Why exactly this is needed will be demonstrated below, but suffice to say that the linear convergence factor does not converge otherwise.

Proof

The first couple of iterations of this code are oddballs since they sort of set up the proper program, but for sufficiently large \$n\$ our program lengths follow the following relation $$l_n=m+c+2n$$ Where \$m\in\mathbb{N}\$ is the length of our dummy string, thus \$m\sim\pi^n\$, and \$c\in\mathbb{N}\$ is a constant (something like \$c=134\$ in reality). And so precisely, the next term is then $$l_{n+1}=\lfloor\pi m\rfloor+c+2n+2$$ For our purposes it will be more useful to write this as $$l_{n+1}=\pi m-f_1+c+2n+2$$ Where \$f_1=\pi m-\lfloor\pi m\rfloor\$, giving us also that \0ドル<f_1<1\$. Looking one more term ahead, $$l_{n+2}=\lfloor\pi(\pi m-f_1)\rfloor+c+2n+4$$ which we will give the same treatment to obtain $$l_{n+2}=\pi^2 m-\pi f_1-f_2+c+2n+4$$ With this in mind, we first see that \begin{align} \lim_{n\to\infty} R_n &= \lim_{n\to\infty} \frac{l_{n+1}}{l_n}\\ &= \lim_{n\to\infty} \frac{\pi m-f_1+c+2n+2}{m+c+2n}\\ &= \lim_{n\to\infty} \frac{\pi^{n+1}-f_1+c+2n+2}{\pi^n+c+2n}\\ &= \pi \end{align} And finally (with possibly a bit of hand waving) \begin{align} \rho &= \lim_{n\to\infty} \frac{|R_{n+1} − \pi|}{|R_n − \pi|}\\ &= \lim_{n\to\infty} \frac{|\frac{l_{n+2}}{l_{n+1}} − \pi|}{|\frac{l_{n+1}}{l_n} − \pi|}\\ &= \lim_{n\to\infty} \frac{|\frac{\pi^2 m-\pi f_1-f_2+c+2n+4}{\pi m-f_1+c+2n+2} − \pi|}{|\frac{\pi m-f_1+c+2n+2}{m+c+2n} − \pi|}\\ &= \lim_{n\to\infty} \frac{|\frac{-f_2+(1-\pi)(c+2n)+4-2\pi}{\pi m-f_1+c+2n+2}|}{|\frac{-f_1+(1-\pi)(c+2n)+2}{m+c+2n}|}\\ &= \lim_{n\to\infty} \frac{\frac{f_2+(\pi-1)(c+2n)-4+2\pi}{\pi m-f_1+c+2n+2}}{\frac{f_1+(\pi-1)(c+2n)-2}{m+c+2n}}\\ &= \lim_{n\to\infty} \frac{(f_2+(\pi-1)(c+2n)-4+2\pi)\cdot(m+c+2n)}{(f_1+(\pi-1)(c+2n)-2)\cdot(\pi m-f_1+c+2n+2)}\\ &= \lim_{n\to\infty} \frac{(f_2+(\pi-1)(c+2n)-4+2\pi)\cdot(\pi^n+c+2n)}{(f_1+(\pi-1)(c+2n)-2)\cdot(\pi^{n+1}-f_1+c+2n+2)}\\ &= \lim_{n\to\infty} \frac{1}{\pi}\cdot\frac{f_2+(\pi-1)(c+2n)-4+2\pi}{f_1+(\pi-1)(c+2n)-2}\\ &= \frac{1}{\pi}\\ \end{align}

Note that in the final two lines here we see the need for our extra four bytes of code +"#", if \$c+2n\$ were replaced simply with \$c\$ the limit would not converge, since \$f_1,f_2\$ are bounded but not constant, and indeed are essentially random each iteration.