Generate Conway's Atomic Elements

Question

Background

The look-and-say sequence begins with \$1\$, each following term is generated by looking at the previous and reading each group of the same digit (eg. \$111\$ is three ones, so \$111 \rightarrow 31\$). The first few terms are $$ 1, 11, 21, 1211, 111221, 312211, \dots $$ Conway's cosmological theorem says that from any starting point, the sequence eventually becomes a sequence of "atomic elements", which are finite subsequences that never again interact with their neighbors. There are 92 such elements.

See also: Wikipedia, OEIS

The Challenge

In this challenge you will take no input and you must output all 92 of Conway's atomic elements. The output may be in any order, and of any reasonable form for a list of numbers.

This is code-golf, so the shortest answer wins.

Sample Output:

22
13112221133211322112211213322112
312211322212221121123222112
111312211312113221133211322112211213322112
1321132122211322212221121123222112
3113112211322112211213322112
111312212221121123222112
132112211213322112
31121123222112
111213322112
123222112
3113322112
1113222112
1322112
311311222112
1113122112
132112
3112
1112
12
3113112221133112
11131221131112
13211312
31132
111311222112
13122112
32112
11133112
131112
312
13221133122211332
31131122211311122113222
11131221131211322113322112
13211321222113222112
3113112211322112
11131221222112
1321122112
3112112
1112133
12322211331222113112211
1113122113322113111221131221
13211322211312113211
311322113212221
132211331222113112211
311311222113111221131221
111312211312113211
132113212221
3113112211
11131221
13211
3112221
1322113312211
311311222113111221
11131221131211
13211321
311311
11131
1321133112
31131112
111312
132
311332
1113222
13221133112
3113112221131112
111312211312
1321132
311311222
11131221133112
1321131112
311312
11132
13112221133211322112211213322113
312211322212221121123222113
111312211312113221133211322112211213322113
1321132122211322212221121123222113
3113112211322112211213322113
111312212221121123222113
132112211213322113
31121123222113
111213322113
123222113
3113322113
1113222113
1322113
311311222113
1113122113
132113
3113
1113
13
3

Answer 1

Charcoal, 174 bytes

Ｆ⪪⪪”}∧Ｉ*₂φ,.i\`β↷Ht≧'θvυＱ=^ι←ºρ²≡O✂⟦Ｆ!n^φ⁰γ↨ΣP@g,Ｃ[¦⟦“↥⁼>∕νＤＩwO4(fO↓;⧴�i⁷·P↨]]ＷＷＵＢ⎚Rcρw∕✳Iⅉ}⟲⊘&:'▶≕…7»↗→➙…⁶⪪✳‖↨FＭ＆⦄Ｊs/″⁷mβ⊗⊞4W⟲Ｌ.”0²«≔⊟ιθＦＩ⊟ι«⟦θ⟧≔⟦⟧ηＦθ⊞⊞Ｏη⊕∧⁼↨η⁰Ｉλ∧⊟η⊟ηＩλ≔⪫ηωθ

Try it online! Link is to verbose version of code. Explanation:

Ｆ⪪⪪”...”0²«

Split and loop over a compressed string of elements that aren't the result of a look-and-say of another element and the number of elements in that element's group of look-and-say derivatives.

≔⊟ιθ

Get the element.

ＦＩ⊟ι«

Loop over it and each derivative.

⟦θ⟧

Output the element.

≔⟦⟧η

Collect the look-and-say results in an array.

Ｆθ

Loop over the digits of this element.

⊞⊞Ｏη⊕∧⁼↨η⁰Ｉλ∧⊟η⊟ηＩλ

If this digit equals the last digit so far then the previous digit is removed and incremented otherwise 0 is incremented and that and the current digit is then pushed (back).

≔⪫ηωθ

Join the array to create the next element. (Note that the "last" element is never output.)

Answer 2

Jelly, 47 bytes

ŒrF
J‘œṖ€⁸Ç9¡€F⁼ɗƇÇ9¡Ḣ)Ẏḟ®
3WWḷ;ɼÑWÇÐLƊ€ẎƲÐLḊɼU

Try it online!

A full program that runs with no input and outputs the 92 Conway elements. Broadly, this works by starting with [3], iteratively generating the next look say sequence member and then attempting to iteratively split this into irreducible elements. Each irreducible element thus found is then passed onto the next iteration after filtering out any previously seen ones. Testing for irreducibility is done by splitting a sequence into every possible pairwise split and finding the first where nine generations of look say algorithm produces the same result as running 9 generations on the unsplit sequence. (Nine was found empirically.) Full explanation to follow.

Note the order is determined by the first time a sequence is seen with this approach, so is not the same as the order in Conway’s paper.

Explanation

ŒrF                     # ‎⁡Helper link 1: takes a sequence of integers and returns the look say encoding (reversed)
Œr                      # ‎⁢Run-length encode
  F                     # ‎⁣Flatten

J‘œṖ€⁸Ç9¡€F⁼ɗƇÇ9¡Ḣ)Ẏḟ®  # ‎⁤Helper link 2: Takes a list of sequences and returns a list of sequences where each of the original ones have been split, if possible, into two
                  )     # ‎⁢⁡For each sequence in list: 
J                       # ‎⁢⁢- Range from 1 to length of sequence
 ‘                      # ‎⁢⁣- Increment by 1
  œṖ€⁸                  # ‎⁢⁤- Split each of the original sequence just before the index of each of these integers
            ɗƇ          # ‎⁣⁡- Keep only those where:
      Ç9¡€F             # ‎⁣⁢  - The result of running helper link 1 on each half of the split and then flattening
           ⁼            # ‎⁣⁣  - Is equal to:
              Ç9¡       # ‎⁣⁤    - The result of running helper link 1 on the unsplit sequence
                 Ḣ      # ‎⁤⁡- Take the first valid split (which will be the original sequence and an empty list if there is no split possible)
                   Ẏ    # ‎⁤⁢Join outer lists together
                    ḟ®  # ‎⁤⁣Filter out any sequences already held in the register
   

3WWḷ;ɼÑWÇÐLƊ€ẎƲÐLḊɼU    # ‎⁤⁤Main link: takes no arguments and returns a list of all 92 elements
3WW                     # ‎⁢⁡⁡Start with 3 wrapped in a list and wrapped again (i.e. [[3]])
              ƲÐL       # ‎⁢⁡⁢Repeat the following until no change between iterations:
    ;ɼÑ                 # ‎⁢⁡⁣- Concatenate the current list of elements to the register
   ḷ                    # ‎⁢⁡⁤- But then revert to the current list of elements
           Ɗ€           # ‎⁢⁢⁡- For each element in the list:
      Ñ                 # ‎⁢⁢⁢  - Use helper link 1 to generate the next look say sequence from this
       W                # ‎⁢⁢⁣  - Wrap this in a list
        ÇÐL             # ‎⁢⁢⁤  - Then use helper link 2 to iteratively split the sequence into irreducible elements
             Ẏ          # ‎⁢⁣⁡- Join outer lists
                 Ḋɼ     # ‎⁢⁣⁢Remove the first member of the list in the register (will be a 0 that started off there originally)
                   U    # ‎⁢⁣⁣Finally, reverse each element (since helper link 1 generates them reversed)
💎

Created with the help of Luminespire.

Alternative without use of the register, 49 bytes

ŒrF
J‘œṖ€⁸Ç9¡€F⁼ɗƇÇ9¡Ḣ
3WW,⁸ÑWÇ€ẎḟɗƬṪʋ€Ẏ,ɗ;¥/ÐLṪU

Try it online!

Answer 3

05AB1E, 104 103 bytes

3 90FDÅγs.ιJ•KтË:äþÒ¶Æ₁Ž“cì¥%ât5)§65g-Aér)тθñ.µBηâε;Ü∍ï¨ZÀи}â*5ü”7₃Lƒ-ñh5!•43вNè•"[¯₁Šä•₂в.¥Nåi£ë.£]22)

Outputs Conway's atomic elements in reversed order as list.

Try it online.

Explanation:

If we look at the Element name and Decays into of the Wikipedia table, we can see that a lot of the Decays into are just a single element. The others are either at the start or end, with the exceptions of Ho.Pa.H.Ca.Co to Ca (Atomic Number 21) and Hf.Pa.H.Ca.Li to H (Atomic Number 2), although those still work fine if we take a portion of another element at the start/end instead.

I basically generate all Conway's atomic elements in reversed order, starting at 3, taking either the leading or trailing portion of the correct output-length. I'll take the leading portion if the (0-based) index is one of [19,23,24,28,30,34,52,53,59,67], and the trailing portion (or full^† look-and-say number) otherwise. And because this would end with 12, I drop that value (by looping one iteration less) and add a hard-coded 22 instead.

3             # Start with a 3
90F           # Loop `N` in the range [0,90):
   D          #  Duplicate the current value
   Åγs.ιJ     #  Convert it to its look-and-say number:
   Åγ         #   Run-length encode the number into two separated lists of values and lengths
     s        #   Swap so the list of values is at the top of the stack
      .ι      #   Interleave the lists of lengths and values together
        J     #   Join this list together to a single string
   •KтË:äþÒ¶Æ₁Ž“cì¥%ât5)§65g-Aér)тθñ.µBηâε;Ü∍ï¨ZÀи}â*5ü”7₃Lƒ-ñh5!•
              #  Push compressed integer 50110820926426684400408736251820828634922551372994851769669719792848756768639391390052494466780374103702329447321431509239639153836796651173069320
    43в       #  Convert it to base-43 as list: [2,4,4,6,10,12,7,10,10,9,12,14,18,24,28,34,42,27,32,5,6,10,14,9,7,12,16,11,7,6,3,6,8,10,5,6,8,14,18,13,7,5,8,10,12,18,24,21,15,20,28,23,7,7,10,14,16,20,26,23,17,3,6,8,5,8,12,5,8,14,16,2,4,4,6,10,12,7,10,10,9,12,14,18,24,28,34,42,27,32]
       Nè     #  Index the current loop-index `N` into this list
              #  (let's call this value, which are the lengths of the outputs, `L`)
   •"[¯₁Šä•  "#  Push compressed integer 104005171539992
    ₂в        #  Convert it to base-26 as list: [19,4,1,4,2,4,18,1,6,8]
      .¥      #  Undelta it with leading 0: [0,19,23,24,28,30,34,52,53,59,67]
        Nåi   #  If the current loop-index `N` is in this list:
           £  #   Keep the first `L` amount of digits from the current string
          ë   #  Else:
           .£ #   Keep the last `L` amount of digits from the current string
  ]           # Close both the if-statement and loop
   22         # Push the final edge-case value 22
     )        # Wrap everything on the stack into a list
              # (which is output implicitly as result)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand how the compressed integers(-lists) work.

†: For the full numbers it doesn't matter if we take the leading or trailing portion. So the additional 0 in the undelta-list [0,19,23,24,28,30,34,52,53,59,67] loopup list, won't make any difference in the output for this first (length 2) value 13.

Answer 4

Retina 0.8.2, 396 bytes

221¶3122113222122211211232221122¶1232221128¶13221123¶126¶311324¶321123¶3123¶132211331222113321¶311311222113111221132221¶31121126¶11121331¶123222113312221131122111¶3113221132122213¶1322113312221131122111¶132116¶31122211¶13221133122111¶111315¶1324¶11132222¶132211331121¶13211323¶3113112221¶111324¶3122113222122211211232221132¶1232221138¶13221133¶37
%`.$
$*#
{%`#$

#+
$&¶$%`
(?=(\d).*#)(\1)+
$#2$1

Try it online! Explanation: Port of my Charcoal answer.

221¶3122113222122211211232221122¶1232221128¶13221123¶126¶311324¶321123¶3123¶132211331222113321¶311311222113111221132221¶31121126¶11121331¶123222113312221131122111¶3113221132122213¶1322113312221131122111¶132116¶31122211¶13221133122111¶111315¶1324¶11132222¶132211331121¶13211323¶3113112221¶111324¶3122113222122211211232221132¶1232221138¶13221133¶37

Insert the base elements each with the count of derived elements appended to them.

%`.$
$*#

Convert the element counts to unary.

{`

Repeat until all elements have been derived.

%`#$

Decrement the remaining count by 1 for each element.

#+
$&¶$%`

Duplicate each unfinished element, but without the count.

(?=(\d).*#)(\1)+
$#2$1

Perform the look-and-say to derive the next element.

Answer 5

Ruby, 256 201 bytes

z=?3;"7773398pr20540910737b10720340557d19713567l19f39r10710760n17h1h33353054b26773398pr272100".scan(/.../){|x|a,b,c=x.chars.map{|r|r.to_i 36};a.times{z=p(z).gsub(/(.)\1*/){|a|"#{a.size}#$1"}};z=z[b,c]}

Try it online!

Use the sequence from the linked page starting with '3'.

Answer 6

JavaScript (Node.js), 211 bytes

Uses the construction described on this page (linked from OEIS and pointed out by Level River St).

B=Buffer;for(i in[...q=B(s="(3(d   3   38(499  !4M( =3(d2")])for(v=q[i]*96+B(".:oyKhZXY;LhXMH:xX]x(ZJKU:oyp")[i]-3104,k=0;k<=v%8;console.log(k++?s:s=s.substr(v>>8,v/8&31)))s=s.replace(/(.)\1*/g,s=>s.length+s[0])

Try it online!

Answer 7

Ruby, 222 bytes

A full program printing output in reverse order to the question. Longer than I had hoped for with this approach, but will be golfed when I have time.

w="\2[IGBeECQwggWOUEGMecgKgie[IG"
s=?3
j=0
q=0xa02411270730708b3140480
92.times{|k|p s
c=0
(s+t=b=?X).chars{|i|i!=b ? t+=c.to_s+b*c=1:c+=1;b=i} 
s=t[3,99]                 
(0<1&q/=2)&&(v=w[j-=1].ord;s=s[(v/32-3)*v%=32,v])}

Try it online!

Starting with 3 we work through the look and say sequence as shown on http://www.se16.info/js/lands2.htm . At the branch points it is only necessary to carry on with exactly one branch. These are binary encoded in magic number q.

The sequence on the linked page actually uses a branch at the beginning or the end of the current string (even in the case 21Sc -> 20Ca although it is not explained that way.) The only exception is 1H where the required substring 22 is found at position -6 (six from the right) in the output of the previous step (amongst other positions.)

The magic string encodes (from right to left) in each character the number of characters in the branch, as well as the number 3 or 2 for the index (in the format index code * 32 + length). When 3 is subtracted from the code, we get (3-3)*l=0 for substrings that appear at the beginning, and (2-3)*l=-l for substrings that appear at the end. Ruby interprets -l as l characters from the righthand end of the string and extracts the correct characters.

For 2H an escape sequence gives ASCII 2 which gives l=2 and (0-3)*2=-6 giving the correct characters for 2H.