Kolakoski Sequence

[Blanchefle Strycker]

Accordinglyone can say that each term of the Kolakoski sequence generates a run of one or two future terms. The first 1 of the sequence generates a run of "1", i.e. itself; the first 2 generates a run of "22", which includes itself; the second 2 generates a run of "11"; and so on. Each number in the sequence is the length of the next run to be generated, and the element to be generated alternates between 1 and 2:

It seems plausible that the density of 1s in the Kolakoski 1,2-sequence is 1/2, but this conjecture remains unproved.[6] Vclav Chvtal has proved that the upper density of 1s is less than 0.50084.[7] Nilsson has used the same method with far greater computational power to obtain the bound 0.500080.[8]

Although calculations of the first 3108 values of the sequence appeared to show its density converging to a value slightly different from 1/2,[5] later calculations that extended the sequence to its first 1013 values show the deviation from a density of 1/2 growing smaller, as one would expect if the limiting density actually is 1/2.[9]

The Kolakoski sequence can also be described as the result of a simple cyclic tag system. However, as this system is a 2-tag system rather than a 1-tag system (that is, it replaces pairs of symbols by other sequences of symbols, rather than operating on a single symbol at a time) it lies in the region of parameters for which tag systems are Turing complete, making it difficult to use this representation to reason about the sequence.[10]

This algorithm takes linear time, but because it needs to refer back to earlier positions in the sequence it needs to store the whole sequence, taking linear space. An alternative algorithm that generates multiple copies of the sequence at different speeds, with each copy of the sequence using the output of the previous copy to determine what to do at each step, can be used to generate the sequence in linear time and only logarithmic space.[9]

This is a repost of an old challenge, in order to adjust the I/O requirements to our recent standards. This is done in an effort to allow more languages to participate in a challenge about this popular sequence. See this meta post for a discussion of the repost.

Full disclosure - I didn't find the solution myself. I let my brute forcer do the heavy lifting for me and just watched the results roll in. At first, I didn't even try to understand the solution. I just assumed it was too complicated for me to wrap my head around. But then I realized that It's actually pretty simple.

The basic idea is to keep the sequence on the stack and repeatedly use the bottom-most element to generate another run and then print it. We're effectively abusing the stack as a queue here. We can also save a couple of bytes by working 0 and 1 (incrementing only for output) instead of 1 and 2, because this way we don't need to explicitly initialise the stack with a 1 and we can use logical negation to toggle between the two values.

I. is a verb which takes an array of numbers and spits out a list of indices, so that if the k-th item in the array is n, then the index k appears n times. We'll use it to bootstrap the Kolakowski sequence up from an initial seed. Each step will proceed as follows:

Notice how we get more and more correct terms each time, and after a while the first n terms are fixed. The number of iterations it takes to settle down is hard to describe precisely, but it looks to be roughly logarithmic in n, so if we just run it n times (^:]) it should be fine. (Check out these other OEIS sequences for more info: generation lengths, partial sums.)

This is a port of my Wumpus answer. Gol> is basically the language that has all the necessary features to port the Wumpus answer (specifically, implicit zeros at the bottom of stack, "duplicate" implemented "pop, push, push", and a stack rotation command), but:

This is one of those rare occasions when we can declare some variables outside the scope of our function, modify them within the function and still be able to reuse them on subsequent calls of the function.

Fueue is a queue-based esolang in which the running program and its data are both in the same queue, the execution goes around the queue in cycles, and programming requires lots of synchronizing to keep anything from executing at the wrong time.

I had a lot of fun messing around with different x86 instructions, as this is my first "non-trivial" x86 answer. I actually learned x86-64 first, and I saved many bytes just by converting my program to 32-bit.

Currently the program takes N values as input in ecx and returns an address in ebp of an array with the nth element representing the nth value in the sequence. I assume returning on the stack and computing extra values is valid (we consider what's beyond the array as garbage anyway).

In the hotly contested SPL category, this would beat Jo King's current entry (583 bytes), except that it is defective: First, it does not run in the TIO version (implementing the SPL website) -- but it does run in the Perl version, so maybe that is not a serious defect. Second, though, it does not print the first two digits. If we allowed that defect in Jo King's solution, then that defective solution would be 553 bytes, beating my defective solution.

My solution fails on TIO for two reasons: we try to rely on an empty stack returning zero when popped; and we goto the first scene, with "[Enter Ford and Puck]" even though nobody has left the stage. These are merely warnings in the Perl version. If I fix these errors and put in the first two digits, I reach 653 bytes:

However, I would point out that this solution is fast compared to many other solutions, and uses logarithmic amounts of memory rather than storing the whole list. (This is similar to vazt's C solution, to which it is distantly related.) This makes no difference for golf, but I'm pleased with it even so. You can generate a million digits in about a minute in Perl (for example if you pipe to sed and wc to get a digit count), where the other solution might give you a few thousand digits.

We store a sequence of variables in order: Puck's stack (bottom to top), Puck's value, Ford's value, Ford's stack (top to bottom). Apart from zero values at the ends (with the zero on the left maybe from popping an empty stack), each value is the digit generated next at that generation, with 2 added if the next generation needs to have another child from that parent. When we have N non-zero values in the sequence, we generate all the children up to and including the N-th generation, in a kind of depth-first tree traversal. We print values only from the N-th generation. When the N-th generation has been completely generated, the stored values are in fact the starting values for generations 2 to (N+1), so we append a 2 at the left and start again, this time generating the (N+1)-th generation.

So, an outline:Scene X: When we reach here, this the start of a new traversal. Puck==0. We optionally push that zero onto Puck's stack, and set Puck=2.Scene L: If Ford==0, we have reached the printing generation. If not, goto V. For printing, if the value in Puck has had 2 added, remove the 2 and print it twice; if not, print it once.Scene M: This is a loop where we repeatedly toggle the value of Puck and go back through the sequence. We repeat until either we reach the end (Puck==0), in which case goto X, or we reach a value that needs another child (Puck>2), in which case subtract the extra 2 and go forwards in V.Scene V: Here we go forwards. If Puck is 2 or 4, the next generation will contain two children from the current parent, so Ford+=2. Step forwards through the sequence. Goto L to check for termination.

The self-describing sequence consisting of "blocks" of single and double 1s and 2s, where a "block" is a single digit or pair of digits that is different from the digit (or pair of digits) in the preceding block. To construct the sequence, start with the single digit 1 (the first "block"). Here, the single 1 means that block of length one follows the first block. Therefore, require that the next block is 2, giving the sequence 12.

The question of whether the number of 1s is "asymptotically" equal to the number of 2s is unsettled, although the above plot (which shows the fraction of 1s as a function of number of digits) is certainly consistent with 1 and 2 being equidistributed.

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

In this work, we present a new family of Zone Plates (ZPs) designed using the self-generating Kolakoski sequence. The focusing and imaging properties of these aperiodic diffractive lenses coined Kolakoski Zone Plates (KZPs) are extensively studied. It is shown that under monochromatic plane-wave illumination, a KZP produces two main foci of the same intensity along the axial axis. Moreover, one of the corresponding focal lengths is double the other, property correlated with the involved aperiodic sequence. This distinctive optical characteristic is experimentally confirmed. We have also obtained the first images provided by these bifocal new diffractive lenses.

Diffractive lenses are essential components in image-forming setups at visible wavelengths but also at other spectral ranges in the electromagnetic spectrum. For instance, this kind of lenses offers excellent performance with submillimeter wavelengths (THz frequencies)1 and with extreme-ultraviolet and X-rays2 for the observation of nanostructures. A Zone Plate (ZP)3,4 is the simplest diffractive lens characterized by a series of alternating concentric transparent and opaque annular rings distributed periodically along the square of the radial coordinate, so the area of each annular zone is a constant. Under the paraxial approximation, this zone configuration produces a series of convergent and divergent spherical waves by diffraction when the lens is illuminated by a monochromatic plane wave, hence generating a series of real and virtual foci along the optical axis. To improve diffraction efficiency, ZPs with a binary phase distribution of zones5,6 and ZPs with a sawtooth profile (known as kinoform lenses)7,8 were proposed. It was theoretically demonstrated that the latter configuration allows concentrating all the energy in a single focus for the design wavelength. Photon Sieves9,10,11 have been proposed to improve the spatial resolution of ZPs. In this application, the transparent annular zones of the amplitude ZPs are replaced by a disjoint set of holes, apodizing in this way the higher order diffraction foci. The combination of Photon Sieves with intracorneal inlays generates a novel alternative for presbyopia treatment12,13.

3a8082e126