title: Output the Trinity Hall Prime

text:
# Question
Title: Output the Trinity Hall Prime
Based on this Math.SE question; number copied from this answer. Number originally from a Numberphile video, of course.

Your task is to output the following 1350-digit prime number:

```
888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888111111111111111111111111888888111111111111111111111111888888111111811111111118111111888888111118811111111118811111888888111188811111111118881111888888111188811111111118881111888888111888811111111118888111888888111888881111111188888111888888111888888111111888888111888888111888888888888888888111888888111888888888888888888111888888111888888888888888888111888888811188888888888888881118888188811188888888888888881118881188881118888888888888811188881118888111888888888888111888811111888811118888888811118888111111188881111111111111188881111111118888111111111111888811111111111888811111111118888111111111111188881111111188881111111111111118888811118888811111111111111111888881188888111111111111111111118888888811111111111111111111111888888111111111111111111111111118811111111111111111111111111111111111111111111062100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

```

You may optionally include newlines in the output.

# Rules

* This is , so no input.
* Your program must terminate within one hour on a standard computer - if it is close, I will use mine for testing. If your program runs for more than minute, or does not terminate on TIO, please include the time on your computer.
* This is , so shortest code, in bytes, wins.

# Answer
# Jelly, ~~74~~ ~~71~~ ~~69~~ ~~68~~ 66 bytes

```
“©ạ-3ṗÇñ"ỤḍV8żṢ?ḤsMVE[,Ṃƭ"ḞÇsẇʂ(ụFsẠʂẆŀṣ’ḃ19ĖŒṙị⁾81s30m0Z062 ȷ446‘

```

Try it online!

### How it works

The literal `“©ạ-3ṗÇñ"ỤḍV8żṢ?ḤsMVE[,Ṃƭ"ḞÇsẇʂ(ụFsẠʂẆŀṣ’` replaces all characters with their code points in Jelly's code page and interprets the result as a (bijective) base-250 number, yielding the following integer.

```
103877200905186099028820568168804302565394743652609510039112658230540917082292838565138059974

```

Then, `ḃ19` converts this number to bijective base 19, yielding the following digit array.

```
16,14,18,12,19,11,3,12,5,10,3,14,4,9,3,15,4,8,3,6,6,4,4,7,3,4,10,3,4,6,3,3,12,3,4,5,3,2,14,3,4,4,3,7,9,4,3,4,3,8,9,4,3,3,3,9,8,4,4,2,3,9,8,5,3,2,3,9,8,6,3,1

```

Now, `ĖŒṙ` enumerates the digits and performs run-length decoding, yielding the following array.

```
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,11,11,11,12,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,14,14,14,14,14,14,14,14,14,15,15,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,17,17,17,18,18,18,18,18,18,18,18,19,19,19,20,20,20,20,20,20,21,21,21,21,21,21,22,22,22,22,23,23,23,23,24,24,24,24,24,24,24,25,25,25,26,26,26,26,27,27,27,27,27,27,27,27,27,27,28,28,28,29,29,29,29,30,30,30,30,30,30,31,31,31,32,32,32,33,33,33,33,33,33,33,33,33,33,33,33,34,34,34,35,35,35,35,36,36,36,36,36,37,37,37,38,38,39,39,39,39,39,39,39,39,39,39,39,39,39,39,40,40,40,41,41,41,41,42,42,42,42,43,43,43,44,44,44,44,44,44,44,45,45,45,45,45,45,45,45,45,46,46,46,46,47,47,47,48,48,48,48,49,49,49,50,50,50,50,50,50,50,50,51,51,51,51,51,51,51,51,51,52,52,52,52,53,53,53,54,54,54,55,55,55,56,56,56,56,56,56,56,56,56,57,57,57,57,57,57,57,57,58,58,58,58,59,59,59,59,60,60,61,61,61,62,62,62,62,62,62,62,62,62,63,63,63,63,63,63,63,63,64,64,64,64,64,65,65,65,66,66,67,67,67,68,68,68,68,68,68,68,68,68,69,69,69,69,69,69,69,69,70,70,70,70,70,70,71,71,71,72

```

Then, `ị⁾81` indexes into the string **81**, replacing odd numbers with the character **8**, even number with the character **1**. Afterwards, `s30` splits the result into chunks of length 30. Displaying one chunk per line, the result looks as follows.

```
888888888888888811111111111111
888888888888888888111111111111
888888888888888888811111111111
888111111111111888881111111111
888111111111111118888111111111
888111111111111111888811111111
888111111888888111188881111111
888111188888888881118888111111
888111888888888888111888811111
888118888888888888811188881111
888111111188888888811118881111
888111111118888888881111888111
888111111111888888881111888811
888111111111888888881111188811
888111111111888888881111118881

```

Now, `m0` concatenates the array of chunks with a reversed copy of itself. Afterwards, `Z` zips the result, transposing rows and columns.

```
888888888888888888888888888888
888888888888888888888888888888
888888888888888888888888888888
888111111111111111111111111888
888111111111111111111111111888
888111111811111111118111111888
888111118811111111118811111888
888111188811111111118881111888
888111188811111111118881111888
888111888811111111118888111888
888111888881111111188888111888
888111888888111111888888111888
888111888888888888888888111888
888111888888888888888888111888
888111888888888888888888111888
888811188888888888888881118888
188811188888888888888881118881
188881118888888888888811188881
118888111888888888888111888811
111888811118888888811118888111
111188881111111111111188881111
111118888111111111111888811111
111111888811111111118888111111
111111188881111111188881111111
111111118888811118888811111111
111111111888881188888111111111
111111111118888888811111111111
111111111111888888111111111111
111111111111118811111111111111
111111111111111111111111111111

```

`0` is an unparsable nilad, so the result from before is printed (without line breaks) and the return value is set to **0**.

`62` is another unparsable nilad, so the result from before (**0**) is printed and the return value is set to **62**.

`ȷ446` is yet another unparsable nilad. **62** is printed and the return value is set to **10446**.

Finally,  increments the result. The final result (**10446 \+ 1**) is printed when the program finishes.
> 34 votes

# Answer
# SOGL V0.12, ~~81~~ ~~78~~ ~~75~~ 73 bytes

```
$!╚Qαūπōθ(└↓Υ8Π⁶!√|ΠΚψ░⅜Υ‛⁷>∙↓ts3]δεΧ‰“8«─'½Κ81¹¹I⌡_¹◄ø∑'¹n╬³0621"η“⌡01⁰∑

```

Try it Here!

Explanation:

```
...“                 push a big number of the RLE lengths of the top part
    8«─              convert from base 10 to base 16 (15 was the max length, and making it base 15 wasn't worth it)
       '½Κ           prepend to the array 48
          81¹        push [8, 1]
             ¹       wrap those two in an array
              I      rotate clockwise, resulting in [[8, 48], [1, 2], [8, 9], [1, 12], ...]
               ⌡_¹   flatten (iterate over, splat current items contents on stack, collect the contents in an array)
                  ◄  run-length decode

ø∑                   join as a string
  '¹n                split into lines of length 15
     ╬³              palindromize horizontally with no overlap
       0621          push 0, 6, 2, and 1
           "η“       push 445
              ⌡      that many times do
               0       push 0
                1    push 1
                 ⁰∑  join the stack together in a string

```
> 7 votes

# Answer
# Jelly, 136 bytes

```
“ßṪṭAƭẠvµM⁾ṖOḥ⁻Ɠ×Ṣ~*pṭẒFỵṿ¦4ÇḟọLÑOcKɲ⁶2*Ḣɲ’b45;@€1ẋ/€ø“Œ\⁴rrNỊġ:,xƙŒ#ṠƲQçḷĠ%&⁻ɼiḂŀB<Ȧƈg(Ṇb>TḥḄ|ḃṘƬ#l7ƇØṃ’b94;@€8ẋ/€ðżF;0;6;2;1;0ẋ445¤;1Ḍ

```

Try it online!

# Explanation (numbers shortened)

```
“ßṪṭ...*Ḣɲ’b45;@€1ẋ/€ø“Œ\⁴...ƇØṃ’b94;@€8ẋ/€ðżF;0;6;2;1;0ẋ445¤;1Ḍ  Main link
“ßṪṭ...*Ḣɲ’b45;@€1ẋ/€                                             Run-length encoded 1s
“ßṪṭ...*Ḣɲ’                                                      The base-45 encoding of the list of the run-lengths of 1s
           b45                                                    in base 45
                €                                                 For each element
              ;@                                                  prepend
                 1                                                1
                    €                                             For each sublist
                   /                                              Reduce over
                  ẋ                                               Repeat list (this gets a bunch of lists of 1s)
                     ø“Œ\⁴...ƇØṃ’b94;@€8ẋ/€                       Run-length encoded 8s
                      “Œ\⁴...ƇØṃ’                                 The base-94 encoding of the list of the run-lengths of 8s
                                 b94                              in base 94
                                      €                           For each element
                                    ;@                            prepend
                                       8                          8
                                          €                       For each sublist
                                         /                        Reduce over
                                        ẋ                         Repeat list (this gets a bunch of lists of 8s)
                                           ðżF;0;6;2;1;0ẋ445¤;1Ḍ  With both of the previous lists of lists, construct the final string
                                            ż                     Interleave them
                                             F                    Flatten it
                                              ;0                  Append 0
                                                ;6                Append 6
                                                  ;2              Append 2
                                                    ;1            Append 1
                                                      ;           Append
                                                       0ẋ445¤     (Nilad)
                                                       0          0
                                                        ẋ445      445 times
                                                             ;1   Append 1
                                                               Ḍ  Convert decimal digits to a number

```

-121 bytes thanks to Dennis using `“...’` literals instead of normal numbers
> 6 votes

# Answer
# Jelly,  ~~133 84~~  73 bytes

```
“÷iþṃL7[ḲʂƘⱮ=ƬƤ¬`RẹŀẹY÷n£ị€ıø&ḟ"gPƲ_ÇḊṪ’b⁴48;ĖŒṙḂ×7‘s15m€0F;“¡©£¢‘Ḍ×ȷ446‘

```

**Try it online!** (footer formats the decimal number with the dimensions that yield the coat of arms).

### How?

A run-length encoded form of a binary format of the left-side of the coat of arms' `8`s and `1` up to the row before the one starting `0621` reflected with the `0621` added and then multiplied up by **10446** and incremented.

```
“...’b⁴48;ĖŒṙḂ×7‘s15m€0F;“¡©£¢‘Ḍ×ȷ446‘ - Link: no arguments
“...’                                  - base 250 number
     b⁴                                - to base 16
       48;                             - prepend a 48
          Ė                            - enumerate [[1,48],[2,12],[3,3],[4,12],[5,3],...
           Œṙ                          - run-length decode (48 1s then 12 2s then ...)
             Ḃ                         - modulo by 2 (vectorises) evens->0 odds->1
              ×7                       - multiply by 7 (vectorises)
                ‘                      - increment (vectorises) - now all 8s and 1s
                 s15                   - split into chunks of length 15
                    m€0                - reflect each chunk
                       F               - flatten
                         “¡©£¢‘        - code-page indices = [0,6,2,1]
                        ;              - concatenate
                               Ḍ       - from decimal list to number
                                 ȷ446  - 10^446
                                ×      - multiply
                                     ‘ - increment

```
> 6 votes

# Answer
# Charcoal, ~~107~~ ~~104~~ ~~98~~ ~~96~~ ~~87~~ 79 bytes

```
Ｅ³⁰✂”}∧Pt→8⌕ＬＪε`‽∨↑¬KαfＧⅉKＭκ⎆wp◧⪫⊘^≦#⁸¹"π✂×OγX‹nI”×ι¹⁵×⊕ι¹⁵‖ＣＭ²⁸←621Ｍ²⁵¦¹⁴1ＵＢ0

```

Try it online! Link to verbose code for explanation
> 5 votes

# Answer
# Proton, 368 bytes

```
s=(map("8"&(*),[93,6,6,1,1,6,2,2,6,3,3,6,3,3,6,4,4,6,5,5,6,6,6,6,18,6,18,6,18,7,16,4,3,16,3,4,14,4,4,12,4,4,8,4,4,4,4,4,4,4,4,4,5,5,5,5,8,6,2]),map("1"&(*),[24,24,6,10,6,5,10,5,4,10,4,4,10,4,3,10,3,3,8,3,3,6,3,3,3,3,3,3,3,3,3,1,3,3,2,3,3,3,3,3,5,4,4,7,14,9,12,11,10,13,8,15,4,17,2,20,23,26,44]))
q=''.join(s[0][i]+s[1][i]for i:0..len(s[0]))
print(q+'0621'+'0'*445+'1')

```

Try it online!
> 4 votes

# Answer
# Python 2, ~~760~~ ~~523~~ ~~329~~ ~~205~~ 196 bytes

*-237 bytes thanks to Stephen. -124 bytes thanks to Jonathan Frech.*

```
print''.join((ord(j)-34)*'81'[i%2]for i,j in enumerate(":(:((#,#(('$,$'(&%,%&(&%,%&(%&,&%(%'*'%(%(((%(%4%(%4%(%4%)%2%&#%%2%%$&%0%&%&%.%&'&&*&&)&0&+&.&-&,&/&*&1'&'3'$'6*9(<$N"))+'0621'+'0'*445+'1'

```

Try it online!
> 3 votes

# Answer
# Ruby, 180 bytes

```
s=0;"".unpack('H*')[0].split(?f).map{|a|a.chars.map{|c|s^=2**c.to_i(16)};t=("%015b"%s).gsub ?0,?8;$><<t+t.reverse};puts'0621'+?0*445+?1

```

Try it online!

178 bytes + 2 bytes for `-Kn` (forces ASCII encoding.)

43 mostly unprintable characters in between the first quotes. Hexdump:

```
00000000: 733d 300a 22ff f012 3456 789a bff5 f6f7  s=0."...4Vx.....
00000010: ff8f 4f3f 012f ff8b fef7 af69 df45 8cf0  ..O?./.....i.E..
00000020: 1237 bf6a f59f 48f2 37f1 6f04 5f3f 12f0  .7.j..H.7.o._?..
00000030: 222e 756e 7061 636b 2827 482a 2729 5b30  ".unpack('H*')[0
00000040: 5d2e 7370 6c69 7428 3f66 292e 6d61 707b  ].split(?f).map{
00000050: 7c61 7c61 2e63 6861 7273 2e6d 6170 7b7c  |a|a.chars.map{|
00000060: 637c 735e 3d32 2a2a 632e 746f 5f69 2831  c|s^=2**c.to_i(1
00000070: 3629 7d3b 743d 2822 2530 3135 6222 2573  6)};t=("%015b"%s
00000080: 292e 6773 7562 203f 302c 3f38 3b24 3e3c  ).gsub ?0,?8;$><
00000090: 3c74 2b74 2e72 6576 6572 7365 7d0a 7075  <t+t.reverse}.pu
000000a0: 7473 2730 3632 3127 2b3f 302a 3434 352b  ts'0621'+?0*445+
000000b0: 3f31                                     ?1

```

# How?

Everyone else was doing run length encoding, so I wanted to try something different.

The formatted "picture" version of the prime can be separated into two parts - a 30x30 grid of 8's and 1's, and a second section of mostly zeros which can be hardcoded. Focusing on the first part, we observe that it's symmetrical down the center, so if we can produce the left half then we can just print half of each line with its reverse.

Half of one line is 15 characters long. If we replace the 8's with zeros, each line can be interpreted as a 15-bit binary number. Conveniently, for the most part the edit distance between each consecutive line is small, so I decided to implement my solution by storing the first line `s` (`888888888888888`, which just becomes 0) and applying a series of bit flipping operations on `s`, printing the result each time.

Since each line is 15 bits long, I encoded these operations as hexadecimal digits - for example, if the operation is `b` (or 11), then we flip bit 11. Some lines differ by more than one bit, so they require a string of hexadecimal digits. We have one bit left over (`f`) so we can use it as a delimiter between these strings, and also as a "do nothing" value. Example below (you can see these lines in the post referenced in the question):

```
Line 3: 000000000000000
Line 4: 000111111111111  <-- flip bits 0 through b
Line 5: 000111111111111  <-- do nothing
Line 6: 000111111011111  <-- flip bit 5

```

To put that all together, we would encode `0123456789ab`, then separate with `f`, do nothing with `f`, then `5`. This works because we're going to do `.split(?f)` later to get each set of operations by line, which will yield `["0123456789ab", "", "5"]`, and `""` will be a no-op.

The difference between lines 3 and 4 above is by far the longest set of edits, and the edit distance between any two consecutive lines is usually 0-2, so I would say that this encoding is reasonably inexpensive, although I'm sure it can be improved.

The entire encoded string ends up being `fff0123456789abff5f6f7ff8f4f3f012fff8bfef7af69df458cf01237bf6af59f48f237f16f045f3f12f0` (86 bytes), which will get the entire 30x30 grid. But we're not done yet...

Hexadecimal digits can be represented by 4 bits (`b` -\> `1100`, etc.) That means that if we're willing to encode our string 4 bits at a time rather than using bytes, we can cut the length of the string in half. So that's what I did - the hexdump shows the string represented in 43 bytes. After that, it's just a matter of using Ruby's nifty String#unpack with `H*` (interpret as hex string, high nibble first) to expand the 43-byte string into the 86-byte version we know and love, and looping over each set of operations flipping bits - for our stored string `s` and an operation `c` we do `s ^ 2**c.to_i(16)` to flip the corresponding bit.

After each set of edits is completed, we pad the resulting binary to 15 bits, switch all of the 0's back to 8's, and print the result and its reverse. As noted before, the part of the number after the 30x30 grid can be hardcoded, so we do that as `puts'0621'+?0*445+?1`.

The final encoded string has no possibility of working on TIO, so the TIO version uses escapes, which still works but is longer.
> 3 votes

# Answer
# CJam, ~~532~~ ~~412~~ ~~340~~ ~~231~~ ~~210~~ 209 bytes

```
".$MBZp&8OIoLs7Rv/BEqN#1r~E$O%6^UO=\z:(Iw]l\LQ.g.aWf+{2;on|YP'y$:Lc$i$GMCg&mRs#y0*z`Z,C|Hf6;b/o-0|FNK5R:OIi}{'`CJ}LOXMSA,&vzl5scm5y0{om=A_#/wF"'#fm92bs:A;"6NLkB)h%@{u`hp_v+YK"'#fm92bYb2f+{[A/(\s:A;)]}%e~'0445*1
```

Try it Online

Run-length encoding expanded from base 92 (Base 250 led to multibyte chars so had to adjust). Also, `4341089843357287864910309744850519376` is expanded from base 92 and converted to binary. A 1 means the run-length is two digits, 0 means it's one digit. For example, the first 4 digits of the binary representation are 1101 because the first four runs are `[93,8],[24,1],[6,8],[24,1]` (93 8's, 24 1's, etc...)
> 2 votes

# Answer
# JavaScript, ~~454~~ ~~450~~ ~~332~~ ~~207~~ 204 bytes

*-4 bytes thanks to Stephen. -125 bytes thanks to Shaggy and Dom Hastings.*

```
_=>[...`]

,`].map((j,i)=>'81'[i%2].repeat(j.charCodeAt())).join``+0+621+"0".repeat(445)+1

```

There's a boatload of unprintables in this answer, so here's a hexdump:

```
00000000: 5f3d 3e5b 2e2e 2e60 5d18 0618 0606 010a  _=>[...`].......
00000010: 0106 0605 020a 0205 0604 030a 0304 0604  ................
00000020: 030a 0304 0603 040a 0403 0603 0508 0503  ................
00000030: 0603 0606 0603 0603 1203 0603 1203 0603  ................
00000040: 1203 0703 1003 0401 0303 1003 0302 0403  ................
00000050: 0e03 0403 0403 0c03 0405 0404 0804 0407  ................
00000060: 040e 0409 040c 040b 040a 040a 0408 040f  ................
00000070: 0504 0511 0502 0514 0817 061a 022c 605d  .............,`]
00000080: 2e6d 6170 2828 6a2c 6929 3d3e 2738 3127  .map((j,i)=>'81'
00000090: 5b69 2532 5d2e 7265 7065 6174 286a 2e63  [i%2].repeat(j.c
000000a0: 6861 7243 6f64 6541 7428 2929 292e 6a6f  harCodeAt())).jo
000000b0: 696e 6060 2b30 2b36 3231 2b22 3022 2e72  in``+0+621+"0".r
000000c0: 6570 6561 7428 3434 3529 2b31            epeat(445)+1

```

```
f=
_=>[...`]

,`].map((j,i)=>'81'[i%2].repeat(j.charCodeAt())).join``+0+621+"0".repeat(445)+1

document.write(f())
```
> 2 votes

# Answer
# JavaScript (ES6), ~~206~~ ~~205~~ ~~204~~ ~~203~~ ~~198~~ ~~197~~ 194 bytes

Came up with this while working on i cri everytim's solution, figured it was different enough to warrant posting on it's own.

This includes a load of unprintables between the `]` and the `,` so follow the TIO link below to view it with Unicode escapes (each sequence of `\u` followed by 4 digits counts as 1 byte).

```
_=>`],0621ƽ1`.replace(/\D/g,(x,y)=>"810"[y<122?y&1:2].repeat(x.charCodeAt()))

```

Try it online
> 2 votes

# Answer
# MATLAB/Octave, ~~319~~ 318 bytes

This is my first attempt at this challenge. Still a bit large and there are probably more efficient ways of doing it, but I thought I'd post it anyway as the method was more interesting than just zipping it.

```
for i=reshape('|871%871%8%1 8)1 8%1%8$1!8)1!8$1%8#1"8)1"8#1%8#1"8)1"8#1%8"1#8)1#8"1%8"1$8''1$8"1%8"1%8%1%8"1%8"118"1%8"118"1%8"118"1&8"1/8"1#8 1"8"1/8"1"8!1#8"1-8"1#8"1#8"1+8"1#8$1#8#1''8#1#8&1#8-1#8(1#8+1#8*1#8)1#8,1#8''1#8.1$8#1$801$8!1$831''861%891!8K1 0 6 2 1~0~0~0~0`0 1',2,[]);fprintf(repmat(i(2),1,i(1)-31));end

```

Try it online!

The method used here is to make use of a Run-Length-Encoding scheme of sorts.

We start off with the original number and count the number of consecutive digits. These are written in the result below as the count followed directly by the digit (space separated for clarity).

```
938 241 68 241 68 61 8 101 8 61 68 51 28 101 28 51 68 41 38 101 38 41 68 41 38 101 38 41 68 31 48 101 48 31 68 31 58 81 58 31 68 31 68 61 68 31 68 31 188 31 68 31 188 31 68 31 188 31 78 31 168 31 48 1 38 31 168 31 38 21 48 31 148 31 48 31 48 31 128 31 48 51 48 41 88 41 48 71 48 141 48 91 48 121 48 111 48 101 48 131 48 81 48 151 58 41 58 171 58 21 58 201 88 231 68 261 28 441 0 6 2 1 4450 1

```

If any of the values is larger than 95 we break that up into multiple chunks of 95 or less - this only happens for the 445 0's which instead becomes four sets of 95 0's and a set of 65 0's. We also pad any counts that are less than 10 with a 0 to make all elements three characters long. This yields with the spaces removed:

```
938241068241068061018101018061068051028101028051068041038101038041068041038101038041068031048101048031068031058081058031068031068061068031068031188031068031188031068031188031078031168031048011038031168031038021048031148031048031048031128031048051048041088041048071048141048091048121048111048101048131048081048151058041058171058021058201088231068261028441010016012011950950950950650011

```

In hindsight at this point I could have done this step before merging it all together, but ho hum you live and learn. We do something clever which is to take the count for each group (2 digits) and we add 31. Because all of them are \<96, the resulting number is the ASCII value for a printable character (32 to 126). Giving us counts of:

```
|7%7%% ) %%$!)!$%#")"#%#")"#%"#)#"%"$'$"%"%%%"%"1"%"1"%"1"&"/"# ""/""!#"-"#"#"+"#$##'##&#-#(#+#*#)#,#'#.$#$0$!$3'6%9!K    ~~~~`

```

After a bit of reshaping in MATLAB to make it more favourable for decoding, and then also escaping `'` characters with `''` (otherwise MATLAB splits string literals there), we are left with the clever string:

```
|871%871%8%1 8)1 8%1%8$1!8)1!8$1%8#1"8)1"8#1%8#1"8)1"8#1%8"1#8)1#8"1%8"1$8''1$8"1%8"1%8%1%8"1%8"118"1%8"118"1%8"118"1&8"1/8"1#8 1"8"1/8"1"8!1#8"1-8"1#8"1#8"1+8"1#8$1#8#1''8#1#8&1#8-1#8(1#8+1#8*1#8)1#8,1#8''1#8.1$8#1$801$8!1$831''861%891!8K1 0 6 2 1~0~0~0~0`0 1

```

That is the root of the code. In the code all I then do is reshape the array into a 2D string with 128 pairs of characters. For each pair the first character has 31 subtracted, and then the second character is displayed that many times.

The result is the original prime:

```
888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888111111111111111111111111888888111111111111111111111111888888111111811111111118111111888888111118811111111118811111888888111188811111111118881111888888111188811111111118881111888888111888811111111118888111888888111888881111111188888111888888111888888111111888888111888888111888888888888888888111888888111888888888888888888111888888111888888888888888888111888888811188888888888888881118888188811188888888888888881118881188881118888888888888811188881118888111888888888888111888811111888811118888888811118888111111188881111111111111188881111111118888111111111111888811111111111888811111111118888111111111111188881111111188881111111111111118888811118888811111111111111111888881188888111111111111111111118888888811111111111111111111111888888111111111111111111111111118811111111111111111111111111111111111111111111062100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

```

---

Edits:

* rearranged the magic string so I could get rid of a transpose after the reshape. Saves a byte.
> 2 votes

# Answer
# 05AB1E, 76 bytes

```
•ŒÆÿ¹т£Ƶ‘β\,ä¸γλaXë«Š¸þaγG(žÃÇ…»šKþÈ/?`'•20BS20öDg81s∍Ss×J30ôø.∞0D445×621s1J

```

Try it online!

---

Stole this from Dennis:

```
888888888888888811111111111111
888888888888888888111111111111
888888888888888888811111111111
888111111111111888881111111111
888111111111111118888111111111
888111111111111111888811111111
888111111888888111188881111111
888111188888888881118888111111
888111888888888888111888811111
888118888888888888811188881111
888111111188888888811118881111
888111111118888888881111888111
888111111111888888881111888811
888111111111888888881111188811
888111111111888888881111118881

```

Noticed it always alternates between 8 and 1, so I counted the lengths of each run (Base 20):

```
['G', 'E', 'I', 'C', 'J', 'B', '3', 'C', '5', 'A', '3', 'E', '4', '9', '3', 'F', '4', '8', '3', '6', '6', '4', '4', '7', '3', '4', 'A', '3', '4', '6', '3', '3', 'C', '3', '4', '5', '3', '2', 'E', '3', '4', '4', '3', '7', '9', '4', '3', '4', '3', '8', '9', '4', '3', '3', '3', '9', '8', '4', '4', '2', '3', '9', '8', '5', '3', '2', '3', '9', '8', '6', '3', '1']

```

Joined it all together, and converted it into a base-10 integer:

```
3954184379309026812828704944878416720438306456270310298603957651230861078960874182787979106461

```

Compressed it further into base-255:

```
ŒÆÿ¹т£Ƶ‘β\,ä¸γλaXë«Š¸þaγG(žÃÇ…»šKþÈ/?`'

```

---

Then, after creating the compressed bit... We just have to manipulate it back to the original..

```
20B                                 # Back to base 20.
   S                                # Each char separate...
    20ö                             # As their base 10 values...
       Dg81s∍                       # Extend '81' to the length of the array.
             Ss×J                   # Push that many 8 or 1's as told by the array.
                 30ôø.∞             # Split by the symmetrical pattern, flip it, mirror.
                       0D445×621s1  # Create the part that doesn't fit into a pattern.
                                  J # Join whole stack together.

```

---

# Final output:

```
88888888888888888888888888888
88888888888888888888888888888
88888888888888888888888888888
88811111111111111111111111888
88811111111111111111111111888
88811111181111111118111111888
88811111881111111118811111888
88811118881111111118881111888
88811118881111111118881111888
88811188881111111118888111888
88811188888111111188888111888
88811188888811111888888111888
88811188888888888888888111888
88811188888888888888888111888
88811188888888888888888111888
88881118888888888888881118888
18881118888888888888881118881
18888111888888888888811188881
11888811188888888888111888811
11188881111888888811118888111
11118888111111111111188881111
11111888811111111111888811111
11111188881111111118888111111
11111118888111111188881111111
11111111888881118888811111111
11111111188888188888111111111
11111111111888888811111111111
11111111111188888111111111111
11111111111111811111111111111
11111111111111111111111111111062100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

```
> 2 votes

# Answer
# C (gcc), ~~277~~ ~~250~~ 201 bytes

-27 bytes thanks to ceilingcat

```
n;f(i){for(i=0;n="oApYGYGGBKBGGFCKCFGEDKDEGEDKDEGDEKEDGDFIFDGDGGGDGDSDGDSDGDSDHDQDEBDDQDDCEDODEDEDMDEFEEIEEHEOEJEMELEKENEIEPFEFRFCFUIXG[Cm"[i++]%64;)for(;--n;)putchar(49+i%2*7);printf("0621%0446d",1);}

```

Try it online!
> 2 votes

# Answer
# Perl 5, 307 bytes

```
$d=1;print((map{($d^=9)x$_}(93,24,6,24,6,6,1,10,1,6,6,5,2,10,2,5,6,4,3,10,3,4,6,4,3,10,3,4,6,3,4,10,4,3,6,3,5,8,5,3,6,3,6,6,6,3,6,3,18,3,6,3,18,3,6,3,18,3,7,3,16,3,4,1,3,3,16,3,3,2,4,3,14,3,4,3,4,3,12,3,4,5,4,4,8,4,4,7,4,14,4,9,4,12,4,11,4,10,4,13,4,8,4,15,5,4,5,17,5,2,5,20,8,23,6,26,2,44)),0,621,0 x445,1)

```

Try it online!
> 1 votes

# Answer
## CJam (108 81 bytes)

```
"u{èl>`#ö^½³ó!;kMðSÀËndEyvY3ÉÊÅBà#®"256bFbee{)*~}%"81"f=15/_Wf%zT6Y446,:!1

```

Online demo

In case character encoding borks the above, here it is xxd-encoded:

```
0000000: 2275 1e7b e86c 3e60  8d23 80f6 5ebd b3f3  "u.{.l>`.#..^...
0000010: 213b 968d 6b4d f053  c0cb 6e64 1c45 7976  !;..kM.S..nd.Eyv
0000020: 5933 c9ca 8dc5 42e0  23ae 2232 3536 6246  Y3....B.#."256bF
0000030: 6265 657b 292a 7e7d  2522 3831 2266 3d31  bee{)*~}%"81"f=1
0000040: 352f 5f57 6625 7a54  3659 3434 362c 3a21  5/_Wf%zT6Y446,:!
0000050: 31                                        1

```

The initial run of 8s and 1s is split into just the left half and run-length encoded as just the lengths of alternating runs. Runs of more than 24 are split into runs of at most 24, separated by runs of 0, so that the lengths can be base-25 encoded and then base-256 encoded to pack them down.
> 1 votes

# Answer
## JavaScript (ES2017), 287 bytes

```
_=>"00000000000000000027wr2027wr2027a9ko261b7c23jerc23jerc1yjm0o1y8coo1y2ou01xx5q01xx5q01xx5q00yykxc9ull699d4au9dk75xffo1v2fgptj4fh8jrj3hhwvgfhmlev3hour5rhq24n3hqytj3hr4hdrhr8ykfhra0hr".replace(/.{6}/g,n=>parseInt(n,36).toString(2).replace(/0/g,8).padStart(30,8))+0+621+"0".repeat(445)+1

```

Uses a slightly different approach to @icrieverytim's answer. -10 bytes thanks to @Shaggy's suggestion of using `replace` instead of `match`!

```
f=
_=>"00000000000000000027wr2027wr2027a9ko261b7c23jerc23jerc1yjm0o1y8coo1y2ou01xx5q01xx5q01xx5q00yykxc9ull699d4au9dk75xffo1v2fgptj4fh8jrj3hhwvgfhmlev3hour5rhq24n3hqytj3hr4hdrhr8ykfhra0hr".replace(/.{6}/g,n=>parseInt(n,36).toString(2).replace(/0/g,8).padStart(30,8))+0+621+"0".repeat(445)+1
;
p.innerHTML=f()
```

```
pre{word-wrap:break-word;white-space:normal}
```

```
<pre id=p></pre>
```
> 1 votes

# Answer
## Bubblegum, 88 bytes

```
00000000: edc9 310a 0250 10c4 d02b fdb1 90dc ff64  ..1..P...+.....d
00000010: 96c1 80a2 8885 60aa d97d 7cb3 3de8 75c5  ......`..}|.=.u.
00000020: 37ab 820a 51ee 9537 942a 55c4 aaec 76b4  7...Q..7.*U...v.
00000030: cfb5 1cdc 33dd 908b ac1c 74a0 894e 03c8  ....3.....t..N..
00000040: 11cc 99ab 9c1d c661 32c5 bad6 8aad 96d2  .......a2.......
00000050: b95e 76fe fd6e bb01                      .^v..n..

```

Try it online!
> 1 votes

# Answer
# Ruby, 194 bytes

```
$><<?8+"~:(:((#,#(('$,$'(&%,%&(&%,%&(%&,&%(%'*'%(%(((%(%4%(%4%(%4%)%2%&#%%2%%$&%0%&%&%.%&'&&*&&)&0&+&.&-&,&/&*&1'&'3'$'6*9(<$N".bytes.reduce(""){|s,x|s+(s[-1]==?8??1:?8)*(x-34)}+"0621"+?0*445+?1

```

The upper part is RLE-encoded, the rest is simply hardcoded.

Try it online!
> 1 votes

# Answer
# Kotlin, 339 bytes

```
val s="8J188J1888138<13881887148<14871886158<15861886158<15861885168<16851885178:178518851888188518851D8518851D8518851D8519851B85168315851B85158416851@85168516851>85168716861:861689168@168;168>168=168<168?168:168A1786178C1784178F1:8I188L148^130363231ǯ031"
fun x()=(0..s.length-1 step 2).map{i->(1..(s[i].toInt()-50)).map{print(s[i+1])}}

```

Try it online!
> 1 votes

# Answer
# ///, 260 bytes

```
/;/88%//:/1&13%13"//9/\/\///7/"1#95/!!!!94/%""93/8889-/000009,/11#9'/###9&/#88"9%/"""9#/389"/1119!/-----0/'''''''##8%4#;4&"8%18""&11;188"1::1&#%1#"&#8"",8"&&"&&'&&'&&'&#3"'#"#13"'#"3,"##&#"#"'"#",7#7"7%",%#%"#%,%1#%7"",4#8784,8,8%%,#%%",;411;%%41106215555!0001

```

Try it online!

Nothing terribly interesting, just some compression.
> 1 votes

# Answer
## Mathematica, 192 bytes

```
Uncompress["1:eJxTTMoP8nRjZWCwoCUwxAGIl0VSZIEhi2wEXAgma4Eqa0GCrAW6rAW6rAWyJKYsulPRGGhBRLksNmmYy/HJonkOXStWaeTwgTGQ5JADD4mJTQRdGo2PysUwC1kA0yJDFPdgJjWoKHZJNB/hlMYhaYiaMgkDAzMjQ4NRMHSBIQDgQA6C"]

```

See: http://reference.wolfram.com/language/ref/Compress.html
> 1 votes

# Answer
# Python 2, ~~191~~ ~~190~~ 188 bytes

```
s='0621'+'0'*445+'1'
a=1
for c in'L":&7(4%"%1%$%/$($-$*$+$,$)$.$\'$$($$%$#,#$#$#.#$"##0##!$#0#\'#2#&#2#&#2#&#&&&#&#%(%#&#$*$#&$#*#$&$#*#$&%"*"%&&!*!&&8&8}':s=`a`*(ord(c)-32)+s;a^=9
print s

```

Try it online!

Same principal as my answer over here
> 1 votes

---
Tags: code-golf, kolmogorov-complexity, primes
---


title: On the edges of the hypercube

text:
# Question
Title: On the edges of the hypercube
Your job will be to write a function or a program, that will take an integer `n>0` as input and output a list of the edges of the `n`-dimensional hypercube. In graph theory an edge is defined as a 2-tuple of vertices (or corners, if you prefer), that are connected.

## Example 1

A 1-dimensional hypercube is a line and features two vertices, which we will call `a` and `b`.

Therefore, the output will be:

```
[[a, b]]

```

## Example 2

The 4-dimensional hypercube (or tesseract) consists of 32 edges and its graph looks like this

and the output could look like this

```
[[a, b], [a, c], [a, e], [a, i], [b, d], [b, f], [b, j], [c, d], [c, g], [c, k], [d, h], [d, l], [e, f], [e, g], [e, m], [f, h], [f, n], [g, h], [g, o], [h, p], [i, j], [i, k], [i, m], [j, l], [j, n], [k, l], [k, o], [l, p], [m, n], [m, o], [n, p], [o, p]]

```

## Rules

* You may name the vertices any way you like, as long as the name is unique.
* The edges are undirected, i.e. `[a, b]` and `[b, a]` are considered the same edge.
* Your output must not contain duplicate edges.
* The output may be in any sensible format.
* Standard loopholes are forbidden.

## Scoring

Shortest code wins.

# Answer
# Jelly, 13 bytes

```
ạ/S’
2ṗœc2ÇÐḟ

```

Try it here. For input `3`, the output is:

```
[[[1, 1, 1], [1, 1, 2]],
 [[1, 1, 1], [1, 2, 1]],
 [[1, 1, 1], [2, 1, 1]],
 [[1, 1, 2], [1, 2, 2]],
 [[1, 1, 2], [2, 1, 2]],
 [[1, 2, 1], [1, 2, 2]],
 [[1, 2, 1], [2, 2, 1]],
 [[1, 2, 2], [2, 2, 2]],
 [[2, 1, 1], [2, 1, 2]],
 [[2, 1, 1], [2, 2, 1]],
 [[2, 1, 2], [2, 2, 2]],
 [[2, 2, 1], [2, 2, 2]]]

```

I hope `[1, 1, 1]` etc. is an okay “name”.

### Explanation

The first line is a “predicate” on a pair of edges: `[A, B] ạ/S’` is equal to `sum(abs(A - B)) - 1`, which is zero (false-y) iff `A` and `B` differ in exactly one coordinate.

The second line is the main program:

* Generate all edges with `2ṗ` (Cartesian power of `[1, 2]`).
* Get all possible pairs using `œc2` (combinations of size two without replacement).
* Keep only elements satisfying the predicate defined earlier (`ÐḟÇ`).
> 4 votes

# Answer
## Python 2, 54 56 62 bytes

```
lambda n:{tuple({k/n,k/n^1<<k%n})for k in range(n<<n)}

```

Duplicate edges are removed by making a set of sets, except Python requires that set elements are hashable, so they are converted to a tuples. Note that the sets `{a,b}` and `{b,a}` are equal and convert to the same tuple. xsot saved 2 bytes with `n<<n`.

This can be cut down to 49 bytes if strings of sets are an OK output format

```
lambda n:{`{k/n,k/n^1<<k%n}`for k in range(n<<n)}

```

which gives output like

```
set(['set([1, 3])', 'set([2, 3])', 'set([0, 2])', 'set([0, 1])'])

```

---

```
lambda n:[(k/n,k/n^1<<k%n)for k in range(n*2**n)if k/n&1<<k%n]

```

First, let's look at an older version of the solution.

```
lambda n:[(i,i^2**j)for i in range(2**n)for j in range(n)if i&2**j]

```

Each a number in the interval `[0,2^n)` corresponds to a vertex with coordinates given by its `n`-bit binary strings. To vertices are adjacent if they differ in a single bit, i.e. if one is obtained from the other by xor-ing a power of 2.

This anonymous function generates all possible edges by taking every vertex and every bit position to flip. To avoid duplicating an edge in both directions, only 1's are flipped to 0's.

In the more golfed solution, `k` is used to encode both `i` and `j` via `k=n*i+j`, from which `(i,j)` can be extracted as `(k/n,k%n)`. This saves a loop in the comprehension. The powers of `2` are done as `1<<` to have the right operator precedence.

An alternative approach of generating each pair of vertices and checking if they are a bit flip apart seems longer (70 bytes):

```
lambda n:[(i,x)for i in range(2**n)for x in range(i)if(i^x)&(i^x)-1<1]

```
> 9 votes

# Answer
# Mathematica, ~~48~~ 24 bytes

```
EdgeList@*HypercubeGraph

```

Just an anonymous function that uses built-ins.
> 4 votes

# Answer
## JavaScript (SpiderMonkey 30+), ~~69~~ 64 bytes

```
n=>[for(i of Array(n<<n).keys())if(i/n&(j=1<<i%n))[i/n^j,i/n^0]]

```

This started out as a port of @xnor's Python 2 solution but I was able to save 9 bytes by rewriting the code to use a single loop. Edit: Saved a further 5 bytes by splitting `i` up the other way around, as per @xnor's updated solution, which now also uses a single loop.
> 3 votes

# Answer
# MATL, 20 bytes

```
2i^:qt!Z~Zltk=XR2#fh

```

This works with current version (14.0.0) of the language/compiler.

**Try it online!**

### Explanation

This uses more or less the same idea as @xnor's answer.

```
2i^    % take input n and compute 2^n
:q     % range [0,1,...,2^n-1] (row vector)
t!     % duplicate, transpose into a column vector
Z~     % bitwise XOR with broadcast
Zl     % binary logarithm
tk     % duplicate and round down
=      % true if equal, i.e. for powers of 2
XR     % upper triangular part, above diagonal
2#f    % row and index columns of nonzero values
h      % concatenate vertically

```
> 2 votes

# Answer
# Pyth, 13 bytes

```
fq1.aT.c^U2Q2

```

Output on input 3:

```
[[[0, 0, 0], [0, 0, 1]], [[0, 0, 0], [0, 1, 0]], [[0, 0, 0], [1, 0, 0]], [[0, 0, 1], [0, 1, 1]], [[0, 0, 1], [1, 0, 1]], [[0, 1, 0], [0, 1, 1]], [[0, 1, 0], [1, 1, 0]], [[0, 1, 1], [1, 1, 1]], [[1, 0, 0], [1, 0, 1]], [[1, 0, 0], [1, 1, 0]], [[1, 0, 1], [1, 1, 1]], [[1, 1, 0], [1, 1, 1]]]

```

Explanation:

```
fq1.aT.c^U2Q2
                  Implicit: input = Q
        ^U2Q      All Q entry lists made from [0, 1].
      .c    2     All 2 element combinations of them.
f                 Filter them on
   .aT            The length of the vector
 q1               Equaling 1.

```
> 2 votes

# Answer
# Python 2: 59 bytes

```
lambda n:[(a,a|1<<l)for a in range(2**n)for l in range(n)if~a&1<<l]

```
> 1 votes

---
Tags: code-golf, math, graph-theory
---


title: Golfing the Core

text:
# Question
Title: Golfing the Core
## Note: although this is tagged as Python, other languages are permitted

## Challenge

What you have to do is write the shortest functions to perform the same actions as the following Python 2 built in functions:

### Range

```
>>> range(1, 10, 1)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> range(1, 10, 2)
[1, 3, 5, 7, 9]
>>> range(10, 5, -1)
[10, 9, 8, 7, 6]

range(start, end, step)

```

When run, this produces an ascending list of numbers. Generally used in for loops, this can also be used for golfing when lists of numbers are required.

### Type

```
>>> type(12)
'int'
>>> type(12.0)
'float'
>>> type('12')
'str'
>>> type([13, 45])
'list'

type(var)

```

Returns the data type of a variable. The required types are in the examples.

### Round

```
>>> round(0.5, 0)
1.0
>>> round(0.2, 0)
0.0
>>> round(3.14159, 3)
3.142
>>> round(127.56, -2)
100.0
>>> round(12.5640, 2)
12.56
>>> round(1457, -2)
1500

round(number, ndigits)

```

Given a floating point integer, it rounds it to ndigits. Floor and ceil functions are not allowed. For ties, round away from zero.

### Enumerate

***Note:*** Return a list despite the fact that in Python, **`enumerate`** returns an object.

```
>>> enumerate([1, 2, 3, 4])
[[0, 1], [1, 2], [2, 3], [3, 4]]
>>> enumerate(['spam', 'eggs'])
[[0, 'spam'], [1, 'eggs']]

enumerate(array)

```

Returns a two dimensional list with the index as part of the embedded list.

## Rules

People writing in Python must *not* use the built-in functions listed above (or magic variables). If there are similar built-in functions in your language, you must not use them.

For invalid arguments return 1:

```
>>> enumerate(23)
1
>>> round(56, 'hello')
1
>>> range('hi', 4, 1)
1

```

You may use your own functions (range, type, round and enumerate).

## Winning

Your score is the sum of the byte count for each function (the function declaration should not be counted). The lowest score wins.

# Answer
## Python 2 – ~~309~~ 303

```
t=type=lambda x:["list","string","int","float"][(`x`[0]!="[")*(1+(`x`[0]!="'")*(1+("."in`x`)))]
def T(s,a,i,b=1):
    try:return(1/(t(i)=='int'))*eval(s)
    except:return 1
r=range=lambda a,b,i:T("[a]+r(a+i,b,i)if b*i>a*i else[]",a,i,b)
enumerate=lambda a:T("map(list,zip(r(0,len(a),1),a))",a,1)
def round(a,i):b=T("10.**-i/2*a/abs(a)",a,i);return T("a-(a+b)%(b*2)+b",a,i,b)

```

It’s so long, because it complies with the requirements (if I am not mistaken), in particular returning `1` for invalid input.

Matsjoyce’ answer provided some inspirations.
> 3 votes

# Answer
# MIPS

## Range - 40

Probably can be golfed much more with x86 or some clever instruction.

Input:

```
    .text
    .globl main
main:   # Read inputs
    li      $v0, 5
    syscall
    move    $t0, $v0

    li      $v0, 5
    syscall
    move    $t1, $v0

    li      $v0, 5
    syscall
    move    $t2, $v0

```

Actual program (writes to stack):

```
loop:   bgtz    $t2, pos
        ble     $t0, $t1, exit  # i <= end
        j       l
pos:    bge     $t0, $t1, exit  # i >= end
l:      addi    $sp, $sp, -4
        sw      $t0, 0($sp) # Push $t1
        add     $t0, $t0, $t2
        j       loop

```

## Type - 12 (non-serious)

In MIPS all registers can be used with integer instructions, even the floating point ones.

```
    .text
    .globl main
main:
    li      $v0, 4
    la      $a0, msg
    syscall

    .data
msg:        .asciiz "Integer (probably)"

```
> 5 votes

# Answer
## JavaScript ES 6 - 175 Bytes

I'm counting everything up to the arrow as part of the declaration.

**Range 57:**

```
range=(a,b,c)=>{for(r=[i=0];i<Math.ceil((b-a)/c);r[i]=a+i++*c);return r}

```

**Type 45:**

```
type=a=>a.big?'str':a.map?'list':~~a!=a?'float':'int'

```

**Round 54:**

```
round=(a,b)=>(c=Math.pow(10,b),d=a*c,e=d-~~(d),(e<0.5?d-e:d+1-e)/c)

```

**Enumerate 19:**

```
enumerate=a=>a.map((x,y)=>[y,x])

```
> 4 votes

# Answer
# Ruby, 183

```
range=->a,b,s{r=[a];r<<a while(a+=s)<b;r<<a} # 38 bytes

type=->x{%w[int float str list 1][[1,1.0,'',[]].find_index{|y|x.class===y}||4]} # 74 bytes

round=->n,d{a=10**d;b=n*a;z=b%1;b-=z<0.5?z:(-1+z);b/a} # 48 bytes

enumerate=->l{(0...l.size).zip l} # 23 bytes

```

I've not counted the names of the lambdas and the `=` that follows them. Only `type` handles invalid input. It returns the `String` `"1"` when an object with a class other than `Integer`, `Float`, `String` or `Array` is given. The other functions blow up when, for example, a `Symbol` is passed where a `Numeric` is expected. I suspect Python behaves similarly.
> 4 votes

# Answer
# Python 3 - 199

## Range - 48

```
def range(s,e,g):
 r=[]
 while[s>e,s<e][g>0]:r+=[s];s+=g
 return r

```

## Enumerate - 32

```
enumerate=lambda x:[[i,x[i]]for i in range(len(x))]

```

Or

```
enumerate=lambda x:zip(range(len(x)),x)

```

But this doesn't return a list

## Round - 29

```
def round(x,a):
 a=10**-a
 return(x+a/2)//a*a

```

## Type - 90

```
def type(x):
 x=repr(x)
 if x[0]in"'\"":return str
 if x[0]=="[":return list
 return[int,float]["."in x]

```
> 3 votes

# Answer
# Haskell, 86

```
import Data.Typeable
approx f n=toEnum(fromEnum$10^n*f+0.5)/10^n
getType a=typeOf a
range a b c=[a,a+c..b-c/abs c]
enumerate=zip[0..]

```

In Haskell there is a type system, so I allowed myself to have a `Typeable` type-class restriction in `getType`'s type (`type` is a reserved name in Haskell). to clarify, this is impossible in any other way, as in Haskell you can't cast variables to other types and catch the resulting type exceptions - Haskell simply does not have type errors.

The `enumerate` functions returns a list of two tuples instead of a list of lists, and I figured that if python tuples weren't immutable they would use them instead.

note that there's already a `round` function in Haskell so I called the `round` function `approx`.
> 2 votes

# Answer
# AppleScript, 382

AppleScript is fun to golf but can't compete with other languages. I count the function bodies, but not the declarations of `on handler(arg)` and `end handler`.

```
--range: 82 bytes
on r(i,j,c)
try
set a to{}
repeat while i/c<j/c
set a to a&i
set i to i+c
end
a
on error
1
end
end r

-- type: 131 bytes
on type(x)
try
if x=x as list
"list"
else if x=x as text
"str"
else if x=x as real and"."is in x as text
"float"
else
"int"
end
on error
1
end
end type

-- round: 70 bytes
on round2(x,p)
try
set m to 10^-p
if x<0then set m to-m
(x+m/2)div m*m
on error
1
end
end round2

-- enumerate: 99 bytes
on enumerate(x)
try
set a to{}
repeat with i in r(1,1+count x,1)
set a to a&{{i-1,x's item i}}
end
a
on error
1
end
end enumerate

-- examples: see results in event log
log r(1, 10, 1)
log r(1, 10, 2)
log r(10, 5, -1)
log type(12)
log type(12.0)
log type("12")
log type({13, 45})
log round2(0.5, 0)
log round2(0.2, 0)
log round2(3.14159, 3)
log round2(127.56, -2)
log round2(12.564, 2)
log round2(1457, -2)
log enumerate({1, 2, 3, 4})
log enumerate({"spam", "eggs"})
log enumerate(23)
log round2(56, "hello")
log r("hi", 4, 1)

```

## range

I renamed `range` to `r` because my `enumerate` function calls `r`.

I use AppleScript errors to detect invalid arguments. If AppleScript raises an error, then the `try` structure returns 1. Beware that `range([1], "10", 1)` raises TypeError in Python, but `r({1}, "10", 1)` is valid here, because AppleScript's operators accept single-item lists and strings as numbers.

The `try` body is just this:

```
set a to {}  -- empty list
repeat while i / c < j / c
    set a to a & i  -- append i to list
    set i to i + c
end

```

The condition needs to be `i < j` when c is positive, or `i > j` when c is negative. I golfed it as `i/c<j/c`, because the division reverses the comparison when c is negative. As a bonus, c being zero raises a division by zero error, so I correctly reject c being zero as invalid.

Beware that `set a to a & i` is slow because it copies the whole list `a` every time. The fast way might look like `set r to a reference to a`, then `set end of r to i`, but that is not golf.

## type

AppleScript's type operator is `class of x` (or `x's class`). My own `type` function uses operator `=`, because `1 + "1"` is 2 but `1 = "1"` is false. The `try` body is this:

```
if x = (x as list)
    "list"
else if x = (x as text)
    "str"
else if x = (x as real) and "." is in (x as text)
    "float"
else  -- assume x = (x as integer)
    "int"
end

```

Some arguments are invalid; try calling `type(AppleScript)` or `type(type)`. Then `x as text` or `x as real` raises an error and I return 1. It helps that `x as list` always works and `x as text` works with any number.

Because `12 = 12.0` is true, I need another way to tell floats from ints. I observe that `12 as text` is "12" but `12.0 as text` is "12.0", so I check for "." in string. I have no check for infinities or NaN because trying to compute those would raise errors.

## round

I renamed `round` to `round2` because AppleScript has `round` in its standard additions. The `try` body is this:

```
set m to 10^-p
if x < 0 then set m to -m
((x + m / 2) div m) * m

```

I observe `div` truncating toward zero. For rounding, I must calculate `x + m / 2` when x is positive, or `x - m / 2` when x is negative. For golf, I can negate m. In the `div m*m` part, the negative sign of m cancels itself.

Python's `round` typically returns a float, but this `round2` often returns an integer. AppleScript's operators like to convert floats to integers, perhaps to help 68k Macs with no FPU. (PowerPC Macs emulated a 68LC040 with no FPU.)

## enumerate

My `enumerate` also works with strings. The `try` body is this:

```
set a to {}
repeat with i in r(1, 1 + (count x), 1)
    set a to a & {{i - 1, x's item i}}
end
a

```

I must not use AppleScript's range loop (`repeat with i from 1 to count x`), but I may call my own range function. I tried to golf away the final a, but I need it when enumerating the empty list or string.

Beware that i is a reference to a number, not the number itself. If I looped in `r(0,count x,1)` and collected `{{i,x's item(i+1)}}`, the result might look like `{{item 1 of {0, 1}, "spam"}, {item 2 of {0, 1}, "eggs"}}`. The operations `i-1` and `x's item i` coerce i to a number.
> 2 votes

# Answer
## APL (43+19+18+38=118)

```
type←{''≡0↑⍵:'str'⋄⍬≢⍴⍵:'list'⋄⍵=⌈⍵:'int'⋄'float'}  ⍝ 43
round←{0::1⋄∆÷⍨⍎0⍕⍵×∆←10*⍺}                          ⍝ 19
enumerate←{0::1⋄(¯1+⍳⍴⍵),¨⊂¨⍵}                       ⍝ 18
range←{0::1⋄0<∆←-⍺⍺:⌽∆+⍵(∆∇∇)⍺⋄⍺<⍵:⍺,⍵∇⍨⍺-∆⋄⍬}    ⍝ 38

```

I made the argument order consistent with general APL style.

Ungolfed, with explanation.

Test:

```
      ⍝ range: <start> <step> range <end>
      1 (1 range) 10
1 2 3 4 5 6 7 8 9
      1 (2 range) 10
1 3 5 7 9
      10 (¯1 range) 5
10 9 8 7 6
      ⍝ type: type <obj>.
      ⍝ 1.0 is considered int, because APL itself does not make the distinction
      type 12
int
      type 12.1
float
      type '12'
str
      type (13 45)
list
      ⍝ APL's native type function:
      ⎕DR¨ 12 12.0 12.1
83 83 645
      ⍝ round: <digits> round <value>
      0 round 0.5
1
      0 round 0.2
0
      3 round 3.14159
3.142
      ¯1 round 127.56
130
      ¯2 round 127.56
100
      2 round 12.5640
12.56
      ¯2 round 1457
1500
      ⍝ enumerate: enumerate <list>
      enumerate 1 2 3 4
┌───┬───┬───┬───┐
│0 1│1 2│2 3│3 4│
└───┴───┴───┴───┘
      enumerate 'spam' 'eggs'
┌────────┬────────┐
│┌─┬────┐│┌─┬────┐│
││0│spam│││1│eggs││
│└─┴────┘│└─┴────┘│
└────────┴────────┘

```
> 2 votes

# Answer
# Axiom, ~~438~~ 445 bytes

## The macro used 18 bytes

```
I==>"int";T==>type

```

Two macros named I=="int" and T=="type"

## the type function 124 bytes

```
T a==(y:=(tex domainOf a).1;suffix?("Integer()",y)=>I;y="Float()"=>"float";y="String()"=>"str";prefix?("List ",y)=>"list";y)

```

Function type()\[or T\] that retrun "int" "float" or "list" it depend of the type of its argument. It can not fail, it would return the right string for the type int, float, list of ???, string, or othewise would return one unknow string different, in Tex language that says its type in Axiom. Example:

```
(26) -> q:=set [x**2-1, y**2-1, z**2-1];type(q)
   (26)  "Set \left( {{Polynomial \left( {{Integer()}} \right)}} \right)"
                                                             Type: String

```

## the round function 152 bytes

```
Round(a,c)==(v:=T a;(v~="float"and v~=I)or T c~=I=>%i;a<0=>-Round(-a,c);z:=a*10.^c;x:=truncate(z);w:=0.5+x-z;0<=w and w>10^-digits()=>x/10^c;(x+1)/10^c)

```

It would return the Round() of the number (it is in count the error of float so we impose bheaviour of it is of the kind Round(0.4999999999999999999, 0) is 0.0 but Round(0.499999999999999999999, 0) is 1.0 and so Round(0.49999999999999999999999999999999, 0) is 1 too). if Round(a,c) find one error it return the complex number %i \[the complex costant i\]. I don't know how write it without one call one function equivalent to floor (I'm sorry)

## the range function 95 bytes

```
Range(a,b,c)==(T a~=I or T b~=I or T c~=I=>[];[a+c*i for i in 0..(Round((b-a)/c*1.,0)::INT-1)])

```

It would return the result range as a list of number; if find one error it would return the void list \[\]. It use the above type() and Round(,) function too.

## The enumerate function 56 bytes

```
enumerate a==(T a~="list"=>[];[[i-1,a.i]for i in 1..#a])

```

It would enumerate the element of the list as in the question; in case of error return \[\] void list.

## Result in the session

```
(5) -> [[i,j,Round(i,j)] for i in [0.5,0.2,3.14159,127.56,12.5640,1457] for j in [0,0,3,-2,2,-2]]
   (5)
   [[0.5,0.0,1.0], [0.2,0.0,0.0], [3.14159,3.0,3.142], [127.56,- 2.0,100.0],
    [12.564,2.0,12.56], [1457.0,- 2.0,1500.0]]
                                            Type: List List Complex Float
(6) -> Range(1,10,1)
   (6)  [1,2,3,4,5,6,7,8,9]
                                                       Type: List Integer
(7) -> Range(1,10,2)
   (7)  [1,3,5,7,9]
                                                       Type: List Integer
(8) -> Range(10,5,-1)
   (8)  [10,9,8,7,6]
                                                       Type: List Integer
(9) -> type(12)
   (9)  "int"
                                                             Type: String
(10) -> type(12.0)
   (10)  "float"
                                                             Type: String
(11) -> type([13,45])
   (11)  "list"
                                                             Type: String
(12) -> enumerate([1,2,3,4])
   (12)  [[0,1],[1,2],[2,3],[3,4]]
                                                  Type: List List Integer
(13) -> enumerate(["spam","eggs"])
   (13)  [[0,"spam"],[1,"eggs"]]
                                                      Type: List List Any
(14) -> enumerate(23)     -- error for enumerate
   (14)  []
                                                          Type: List None
(15) -> Round(56,"hello") -- error for Round
   (15)  %i
                                                    Type: Complex Integer
(16) -> Range("hi",4,1)   -- error for range
   (16)  []
                                                          Type: List None

```

In total and in partial too it is a very good question: Thank you very much.
> 0 votes

---
Tags: code-golf, python, multiple-holes
---


title: Make the largest infinity that you can!

text:
# Question
Title: Make the largest infinity that you can!
The ordinal number system is a system with infinite numbers. A lot of infinite numbers. So many infinite numbers that it literally does not have an infinity to represent its own infiniteness. The image above gives a little idea of how they work. An ordinal number (Von Neumann construction) is a set of previous ordinals. For example, 0 is the empty set, 1 is the set {0}, 2 is the set {0, 1} and etc. Then we get to ω, which is {0, 1, 2, 3 ...}. ω+1 is {0, 1, 2, 3 ... ω}, ω times two is {0, 1, 2 ... ω, ω + 1, ω + 2...} and you just keep going like that.

Your program will output a set of ordinals, such {0, 1, 4}. Your **score** will then be the least ordinal more than all the ordinal in your set. For {0, 1, 4} the score would be 5. For {0, 1, 2 ...}, the score would be ω.

How do you output your ordinals you ask. Code of course. Namely, your program will output a potentially infinite list of other programs, in quotes, one on each line (use the literal string "\n" to represent new lines). A program corresponds to its score as indicated above. For example, if you output

```
"A"
"B"
"C"

```

where A, B, and C are themselves valid answers and have scores {0, 1, 4}, the score of your program would be 5. Note that A, B, and C, have to be full programs, not fragments.

Based on the above rules, a program that outputs nothing has a score of 0 (the least ordinal greater than all {} is 0). Also, remember a set cannot contain itself, via the axiom of foundation. Namely, every set (and therefore ordinal) has a path down to zero. This means the a full-quine would be invalid as its not a set.

Also, no program is allowed to access outside resources (its own file, the internet etc...). Also, when you list your score, put the cantor normal form of the score alongside it if it isn't in cantor normal form already, if you can (if not, someone else can).

After taking all the above into account, the actual answer you post must be under 1,000,000 bytes (not counting comments). (This upper bound will likely only come into play for automatically generated code). Also, you get to increment your score for each byte you don't use (since we are dealing with infinities, this will probably only come into account when ordinals are very close or the same). Again, this paragraph only applies to the posted answer, not the generated ones, or the ones the generated ones generate, and so on.

This has the quine tag, because it may be helpful to generate at least part of the sources own code, for use in making large ordinals. It is by no means required though (for example, a submission with score 5 would probably not need its own source code).

For a worked out and annotated example, see here.

# Answer
## Haskell: ψ(ΩΩω) + 999672 points

```
main=print$f++shows f"$iterate(Z:@)Z";f="data N=Z|N:@N deriving Show;r=repeat;s Z=[];s(a:@Z)=r a;s(Z:@b)=($u b)<$>h b;s(a:@b)=do(f,c)<-h b`zip`s a;f<$>[c:@b,a]\nh=scanl(flip(.))id.t;t(Z:@Z)=r(:@Z);t(Z:@b)=((Z:@).)<$>t b;t(a:@b)=flip(:@).(:@b)<$>s a;u Z=Z;u(Z:@b)=u b;u(a:@_)=a;g f=mapM_$print.((f++shows f\"$s$\")++).show;main=g"

```

329 bytes of code with ordinal ψ(ΩΩω) \+ 1. Uses a tree-based representation of ordinals discovered by Jervell (2005). The tree with children *α*, *β*, …, *γ* is denoted `α :@ (β :@ (… :@ (γ :@ Z)…))`. This left-to-right order agrees with Jervell, although note that Madore flips it right-to-left.

## Haskell: Γ0 \+ 999777 points

```
main=print$f++shows f"$iterate((:[]).T)[]";f="data T=T[T]deriving(Eq,Ord,Show);r=reverse;s[]=[];s(T b:c)=(++c)<$>scanl(++)[](b>>cycle[fst(span(>=T b)c)++[T$r d]|d<-s$r b]);g f=mapM_$print.((f++shows f\"$s$\")++).show;main=g"

```

224 bytes of code with ordinal Γ0 \+ 1. This is based on a generalization of Beklemishev’s Worm to ordinal-valued elements, which are themselves recursively represented by worms.

## Haskell: ε0 \+ 999853 points

```
main=print$f++shows f"$map(:[])[0..]";f="s[]=[];s(0:a)=[a];s(a:b)=b:s(a:fst(span(>=a)b)++a-1:b);g f=mapM_$print.((f++shows f\"$s$\")++).show;main=g"

```

148 bytes of code with ordinal ε0 \+ 1. This is based on Beklemishev’s Worm. The list

```
map(+1)α ++ [0] ++ map(+1)β ++ [0] ++ ⋯ ++ [0] ++ map(+1)γ

```

represents the ordinal (ω*γ* \+ ⋯ + ω*β* \+ ω*α*) − 1. So the second-level outputs `[0]`, `[1]`, `[2]`, `[3]`, … represent 1, ω, ωω, ωωω, …, the first-level output represents ε0, and the initial program represents ε0 \+ 1.

## Haskell: ε0 \+ 999807 points

```
main=print$f++shows f"$iterate(:@Z)Z";f="data N=Z|N:@N deriving Show;s Z=[];s(Z:@b)=repeat b;s(a:@Z)=scanl(flip(:@))Z$s a;s(a:@b)=(a:@)<$>s b;g f=mapM_$print.((f++shows f\"$s$\")++).show;main=g"

```

194 bytes of code with ordinal ε0 \+ 1.

`Z` represents 0, and we can prove by transfinite induction on *α*, then on *β*, that `α :@ β` ≥ ω*α* \+ *β*. So there are second-level outputs at least as big as any tower ωωω, which means the first-level output is at least ε0 and the initial program is at least ε0 \+ 1.
> 24 votes

# Answer
# Ruby, ψ0X(ψM+1M+1ΩM+1))(0)) + 999663 points

Assuming I understand my program properly, my score is ψ0X(ψM+1M+1ΩM+1))(0)) + 999663 points where **ψ** is an ordinal collapsing function, **X** is the chi function (Mahlo collapsing function), and **M** is the first Mahlo 'ordinal'.

This program is an extension of the one I wrote on Golf a number bigger than TREE(3) and ***utterly trumps*** all of the other solutions here for now.

```
z=->x,k{f=->a,n,b=a,q=n{c,d,e=a;!c ?q:a==c ?a-1:e==0||e&&d==0?c:e ?[[c,d,f[e,n,b,q]],f[d,n,b,q],c]:n<1?9:!d ?[f[b,n-1],c]:c==0?n:[t=[f[c,n],d],n,d==0?n:[f[d,n,b,t]]]};x==0??p:(w="\\"*k+"\"";y="";(0..1.0/0).map{|g|y+="x=#{f[x,g]};puts x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+";"};y)};h=-1;(0..1.0/0).map{|i|puts "puts \"#{z[[i,h=[h,h,h]],1]}\""}

```

Try it online!

# Ruby, ψ0I(II)) + 999674 points

```
z=->x,k{f=->a,n,b=a{c,d,e,q=a;a==c ?a-1:e==0||d==0?(q ?[c]:c):e ?[[c,d,f[e,n,b],q],f[d,n,b],c,q]:[n<1?9:d&&c==0?[d]:d ?[f[c,n],d]:[f[b,n-1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="";(0..1.0/0).map{|g|y+="x=#{f[x,g]};puts(x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+");"};y)};h=0;(0..1.0/0).map{|i|puts("puts(\"#{z[h=[h,h,h,0],1]}\")")}

```

Try it online! (warning: it won't do much, since clearly `(0..1.0/0).map{...}` cannot terminate. It's how I print infinitely many programs as well.)

# Ruby, ψ0I(0)) + 999697 points

```
z=->x,k{f=->a,n,b=a{c,d,e=a;a==c ?a-1:e==0||d==0?c:e ?[[c,d,f[e,n,b]],d-1,c]:[n<1?9:d&&c==0?[d]:d ?[f[c,n-1],d]:[f[b,n-=1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="";(0..1.0/0).map{|g|y+="x=#{f[x,g]};puts(x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+");"};y)};h=0;(0..1.0/0).map{|i|h=[h];puts|i|puts("puts(\"#{z[hz[h=[h],1]}\")")}

```

Try it online!

A more reasonable test program that implements `(0..5).map{...}` instead:

```
z=->x,k{f=->a,n,b=a{c,d,e=a;a==c ?a-1:e==0||d==0?c:e ?[[c,d,f[e,n,b]],d-1,c]:[n<1?9:d&&c==0?[d]:d ?[f[c,n-1],d]:[f[b,n-=1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="";(0..5).map{|g|y+="x=#{f[x,g]};puts(x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+");"};y)};h=0;(0..5).map{|i|h=[h];puts("puts(\"#{z[h,1]}\")")}

```

Try it online!

Unfortunately, even with `(1..1).map{...}`, you will find this program to be *extremely* memory intensive. I mean, the length of the output exceeds things like SCG(13).

By using the simpler program, we may consider a few values:

```
a = value you want to enter in.
z=->x,k{f=->a,n,b=a{c,d,e=a;a==c ?a-1:e==0||d==0?c:e ?[[c,d,f[e,n,b]],d-1,c]:[n<1?9:d&&c==0?[d]:d ?[f[c,n-1],d]:[f[b,n-=1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="x=#{f[x,k]};puts(x==0??p:"+w+"#{z[f[x,k],k*2+1]}"+w+");";y)};puts("puts(\"#{z[a,1]}\")")

```

Try it online!

It basically prints the same program repeatedly, in the format of:

```
x=...;puts(x==0??p:"...");

```

where the initialized `x` records the ordinal the program is related to, and the `"..."` holds the programs after `x` has been reduced. If `x==0`, then it prints

```
p

```

which is a program that prints nothing with a score of zero, hence

```
x=0;puts(x==0??p:"p");

```

has a score of 1, and

```
x=1;puts(x==0??p:"x=0;puts(x==0??p:\"p\");");

```

has a score of 2, and

```
x=2;puts(x==0??p:"x=1;puts(x==0??p:\"x=0;puts(x==0??p:\\\"p\\\");\");");

```

has a score of 3, etc., and my original program prints these programs in the format

```
puts("...")

```

where `...` are the programs listed above.

My actual program actually prints these programs in the format

```
x=0;puts(x==0??p:"p;p;p;p;p;...");

```

Infinitely many times, and for values such as `ω`, it does something akin to

```
x=ω;puts(x==0??p:"(x=0 program); (x=1 program); (x=2 program); ...")

```

And thus, the score of the program

```
x=(some_ordinal);puts(x==0??p:"...")

```

is `1+some_ordinal`, and the score of

```
puts("x=(some_ordinal);puts(x==0??p:\"...\")")

```

is `1+some_ordinal+1`, and the score of

```
z=->x,k{f=->a,n,b=a{c,d,e=a;a==c ?a-1:e==0||d==0?c:e ?[[c,d,f[e,n,b]],d-1,c]:[n<1?9:d&&c==0?[d]:d ?[f[c,n-1],d]:[f[b,n-=1],f[c,n,b]],n,n]};x==0??p:(w="\\"*k+"\"";y="";(0..1.0/0).map{|g|y+="x=#{f[x,g]};puts(x==0??p:"+w+"#{z[f[x,g],k*2+1]}"+w+");"};y)};puts("puts(\"#{z[some_ordinal,1]}\")")

```

is `1+some_ordinal+2`.

---

# Explanation of ordinals:

`f[a,n,b]` reduces an ordinal `a`.

Every natural number reduces to the natural number below it.

```
f[k,n,b] = k-1

```

`[c,0,e]` is the successor of `c`, and it always reduces down to `c`.

```
f[[c,0,e],n,b] = c

```

`[c,d,e]` is a backwards associative hyperoperation, are reduces as follows:

```
f[[c,d,0],n,b] = c
f[[c,d,e],n,b] = [[c,d,f[e,n,b]],f[d,n,b],c]

```

`[0]` is the first infinite ordinal (equivalent to ω) and reduces as follows:

```
f[[0],0,b] = [9,0,0]
f[[0],n,b] = [n,n,n]

```

`[c]` is the cth omega ordinal and reduces as follows:

```
f[[c],0,b] = [9,0,0]
f[[c],n,b] = [[f[b,n-1,b],f[c,n,b]],n,n]
Note the two-argument array here.

```

`[c,d]` is ψd(c) and reduces as follows:

```
f[[c,d],0,b] = [9,0,0]
f[[0,d],n,b] = [[d],n,n]
f[[c,d],n,b] = [[f[c,n,c],d],n,n]

```

`[c,d,e,0]` is basically the same as `[c,d,e]`, except it enumerates over the operation `[c]` instead of the successor operation.

```
f[[c,0,e,0],n,b] = [c]
f[[c,d,0,0],n,b] = [c]
f[[c,d,e,0],n,b] = [[c,d,f[e,n,b],0],f[d,n,b],c,0]

```
> 8 votes

# Answer
# Java + Brainf\***, ω+999180 points

A java program that produces infinitely many Brainf\*** programs, of which each produces the last as output.

Why? Because I can.

Any improvements to the Brainf\*** generation part are definitely welcome.

```
import java.io.*;import java.util.*;import static java.lang.System.*;
class O{
    static String F(String s){
        String t="++++++++++++++++++++";
        List<Character> c=Arrays.asList('+','-','.','<','>','[',']');
        t+="[->++>++>++>+++>+++>++++>++++<<<<<<<]>+++>+++++>++++++>>++>+++++++++++>+++++++++++++";
        for(int x=0,i=6;x<s.length();x++){
            int d=c.indexOf(s.charAt(x)),k=d;
            while(d>i){d--;t+=">";}
            while(d<i){d++;t+="<";}
            t+=".";i=k;
        }return t;
    };
    static void p(String a){
        int i=48;while(i<a.length()){out.println(a.substring(i-48,i));i+=48;}
        out.println(a.substring(i-48));out.println();
    }
    public static void main(String[]a) throws Exception{setOut(new PrintStream("o.txt"));String b="";while(true)p(b=F(b));}
}

```
> 5 votes

# Answer
## Literate Haskell (GHC 7.10): ω² + 999686 points.

This will serve as an example answer. Since its an example, it only makes sense to use literate programming. It won't score well though. The birdies will decrease my score, but oh well. First, let's make a helper function s. If x is an ordinal, s x = x+1, but we find unexpected uses of s.

```
> s x="main=putStrLn "++show x

```

The show function luckily does all the string sanitization for us. Its also worth making 0. Zero is not the successor of anything, but s"" will equal "main=putStrLn """, which equals 0.

```
> z=s""

```

Now we will make a function that takes n, and returns ω\*n.

```
> o 0=z
> o n=q++"\nmain=putStrLn$unlines$map show$iterate s$o "++show(n-1)

```

It works by making ω\*n by {ω\*(n-1), ω\*(n-1)+1, ω\*(n-1)+2, ...}. What is this q? Why, its the reason we have a tag. q is the above helper functions so far.

```
> h x = x ++ show x
> q = h "s x=\"main=putStrLn \"++show x\nz=s\"\"\no 0=z\no n=q++\"\\nmain=putStrLn$unlines$map show$iterate s$o \"++show(n-1)\nh x = x ++ show x\nq = h "

```

Note that only o n needs q, not any of its successors (s(o(n)), s(s(o(n)))), since they don't need the helper functions (except indirectly from o n.) Now we only have to output all of ω\*n for finite n.

```
> main=mapM(print.o)[0..]

```

There we go. ω^2 Having used only 314 code character, I claim a final bonus of 999686, giving me a final score of ω^2 + 999686, which is already in cantor's normal form.

First four lines of output (0, ω, ω\*2, ω\*3):

```
"main=putStrLn \"\""
"s x=\"main=putStrLn \"++show x\nz=s\"\"\no 0=z\no n=q++\"\\nmain=putStrLn$unlines$map show$iterate s$o \"++show(n-1)\nh x = x ++ show x\nq = h \"s x=\\\"main=putStrLn \\\"++show x\\nz=s\\\"\\\"\\no 0=z\\no n=q++\\\"\\\\nmain=putStrLn$unlines$map show$iterate s$o \\\"++show(n-1)\\nh x = x ++ show x\\nq = h \"\nmain=putStrLn$unlines$map show$iterate s$o 0"
"s x=\"main=putStrLn \"++show x\nz=s\"\"\no 0=z\no n=q++\"\\nmain=putStrLn$unlines$map show$iterate s$o \"++show(n-1)\nh x = x ++ show x\nq = h \"s x=\\\"main=putStrLn \\\"++show x\\nz=s\\\"\\\"\\no 0=z\\no n=q++\\\"\\\\nmain=putStrLn$unlines$map show$iterate s$o \\\"++show(n-1)\\nh x = x ++ show x\\nq = h \"\nmain=putStrLn$unlines$map show$iterate s$o 1"
"s x=\"main=putStrLn \"++show x\nz=s\"\"\no 0=z\no n=q++\"\\nmain=putStrLn$unlines$map show$iterate s$o \"++show(n-1)\nh x = x ++ show x\nq = h \"s x=\\\"main=putStrLn \\\"++show x\\nz=s\\\"\\\"\\no 0=z\\no n=q++\\\"\\\\nmain=putStrLn$unlines$map show$iterate s$o \\\"++show(n-1)\\nh x = x ++ show x\\nq = h \"\nmain=putStrLn$unlines$map show$iterate s$o 2"

```
> 4 votes

# Answer
# GolfScript, ε₀+1 + 999537 points

```
{{
{"{"lib`+"}:lib~~"@++"~"+p}:output;
{{}}:nothing;
{{1{).2$`+output 1}do}}:list;
{{\.(`2$`+" iter"+@`if output}}:iter;
{{1${@`@(2$`{rep~}+++\}{;;}if~}}:rep;
{\`\+}:combine;
{{\@@~}}:swap;
{{1${1$(1$`{rangemap~}+[+@@[\\]]{~}/+}{;;}if}}:rangemap;
{`{}+}:wrap;
}}:lib~~
nothing {iter combine list~} {rep combine} {~swap combine combine} rep combine swap combine combine {~list~} combine rangemap {~~} combine combine swap combine combine swap combine combine list~

```

It can probably be better, but I became too lazy to debug and prove larger ordinals.

### Smaller ordinals

```
#ω^ω^ω
#nothing {iter combine list~} {rep combine swap combine combine list~} {rep combine swap combine combine swap combine combine list~} rep combine swap combine combine swap combine combine swap combine combine list~
#ω^ω^2
#nothing {iter combine list~} { {rep combine swap combine combine list~} rep combine swap combine combine swap combine combine list~} rep combine swap combine combine swap combine combine list~
#ω^nω
#nothing {iter combine list~} 2 { {rep combine swap combine combine list~} rep combine swap combine combine swap combine combine list~} rep~
#ω^ω
#nothing {iter combine list~} {rep combine swap combine combine list~} rep combine swap combine combine swap combine combine list~
#ω^n
#nothing {iter combine list~} 3 {rep combine swap combine combine list~} rep~
#ω^3
#nothing {{iter combine list~} rep combine swap combine combine list~} rep combine swap combine combine list~
#ω^2
#nothing {iter combine list~} rep combine swap combine combine list~
#nω
#nothing 3 {iter combine list~} rep~
#2ω
#nothing iter combine list combine iter combine list~
#ω
#nothing iter combine list~
#finite
#2 nothing iter~

```
> 2 votes

# Answer
# Javascript (Nashorn), ω2+999807 points

**Nashorn** is the Javascript engine which comes built into Java. This may also work in Rhino, but I haven't tested it in that yet.

```
c="(b=function(a){print(a?\"(b=\"+b+\")(\"+(a-1)+\")\":\"c=\\\"(b=function(a){print(a?'(b='+b+')'+'('+(a-1)+')':'')})(\\\";a=0;while(++a)print(c+a+\\\")\\\")\")})(";a=0;while(++a)print(c+a+")")

```
> 1 votes

---
Tags: code-challenge, math, quine, code-generation
---


title: Downgrade to a Palindrome

text:
# Question
Title: Downgrade to a Palindrome
Given a string `s`, return the smallest contiguous substring you can remove to create a palindrome.

---

# Examples:

```
800233008   -> 2
racecarFOOL -> FOOL
abcdedcba   -> (empty string)
ngryL Myrgn -> "L " (or " M")
123456789   -> 12345678 (or 23456789)
aabcdbaa    -> c (or d)
[[]]        -> [[ (or ]])
a           -> (empty string)

```

Test case suggestions from users (if you find an edge case not listed, please post a comment):

```
aabaab      -> b    | Suggested by Zgarb, some returned "aa".

```

---

# Rules

* Only printable ASCII characters will appear in the input (no newlines, keep it simple).
* Not really a rule, but note `<>`, `/\`, `()`, `[]` and `{}` are not palindromes.

This is , smallest byte-count wins.

---

*+100 bounty has been claimed by Adnan*

# Answer
> 8 votes
# Jelly, 16 bytes

```
Ḣ;Ṫµ=Ṛ
0,0jŒṖÇÞṪ

```

Try it online!

### How it works

```
0,0jŒṖÇÞṪ  Main link. Argument: s (string)

0,0j       Join [0, 0], separating by s. This prepends and appends a 0 to s.
    ŒṖ     Build all partitions of the resulting array.
      ÇÞ   Sort the partitions by the helper link.
           As a side effect, this will remove the first and last element of each
           partition. The 0's make sure that not removing any characters from s
           will still remove [0] from both sides.
        Ṫ  Tail; extract the last one.

Ḣ;Ṫµ=Ṛ     Helper link. Argument: A (array/partition)

Ḣ          Head; yield and remove the first chunk of A.
  Ṫ        Tail; yield and remove the last chunk of A.
 ;         Concatenate head and tail.
   µ=Ṛ     Compare the result, character by character, with its reverse.
           A palindrome of length l will yield an array of l 1's, while a
           non-palindrome of length l will yield an array with at least one 0 among
           the first l/2 Booleans. The lexicographically largest result is the one
           with the longest prefix of 1's, which corresponds to the longest
           palindrome among the outfixes.

```

# Answer
> 10 votes
# , 24 bytes

```
(0{::(-:|.)\.#&,<\)~i.@#

```

Try it online!

## Explanation

```
(0{::(-:|.)\.#&,<\)~i.@#  Input: array of chars S
                       #  Length of S
                    i.@   Range, [0, 1, ..., len(S)-1]
(                 )~      Dyadic verb on range and S
           \.               For each outfix of S of size x in range
        |.                    Reverse
      -:                      Matches input (is palindrome)
                <\          Box each infix of S of size x in range
             #&,            Flatten each and copy the ones that match
 0{::                       Fetch the result and index 0 and return

```

# Answer
> 7 votes
## Wolfram Language (Mathematica), ~~53~~ 51 bytes

Byte count assumes CP-1252 encoding.

```
±{a___,Shortest@b___,c___}/;PalindromeQ[a<>c]:={b}

```

Try it online!

Defines a unary operator `±` (or a function `PlusMinus`). Input and output are lists of characters. The test suite does the conversion from and to actual strings for convenience.

# Answer
> 6 votes
# 05AB1E, 18 bytes

```
ā<Œ¯¸«ʒRõsǝÂQ}éнèJ

```

Uses the **05AB1E** encoding. Try it online!

# Answer
> 5 votes
# Jelly, 20 bytes

```
ŒḂ⁹Ƥ
çÐ€JN$Ẏi1ịẆẋ⁻Ṛ$

```

Try it online!

# Answer
> 4 votes
# Python 3, 97 bytes

```
f=lambda s,p='	':min([s][:p[::-1]in p+p]+(s and[f(s[1:],p+s[0]),f(s[:-1],s[-1]+p)]or[p]),key=len)

```

Try it online!

# Answer
> 3 votes
# Python 2, 116 bytes

```
def f(i):R=range(len(i)+1);print min([i[y:k+1]for y in R for k in R if(i[:y]+i[k+1:])[::-1]==i[:y]+i[k+1:]],key=len)

```

Try it online!

Saved a couple of bytes with help from Halvard Hummel!

# Answer
> 2 votes
# Japt, ~~26~~ 22 bytes

```
¬£¬ËUjEY ê¬©UtEY
c æ+0

```

Test it online! Trying to figure out how to map `false` to something falsy and any string to something truthy in one byte. Currently I'm using `+0`...

# Answer
> 2 votes
# Bash, 108 bytes

```
for((j=0;;j++)){
for((i=0;i<${#1};i++)){
r=${1:0:i}${1:j+i}
[[ $r = `rev<<<$r` ]]&&echo "${1:i:j}"&&exit
}
}

```

Takes input as command-line argument.

Try it online! with quotes printed around the output for viewing leading/trailing spaces.

# Answer
> 2 votes
# Prolog, 271 byte

```
p([_]).
p([X,X]).
p([X|Y]):-append([P,[X]],Y),p(P).

s(P,M,S,R,N):-p(P),append([M,S],N).
s(P,M,S,S,N):-p(S),append([P,M],N).
s(P,M,S,P,M):-append([P,S],X),p(X).

d(Y,P,N):-
    findall([A,B,C],(append([R,M,X],Y),s(R,M,X,B,C),length(B,A)),S),
    sort(1,@>,S,[[_,P,N]|_]).

```

At some point I realized this is going to be huge by code-golf standards, so I kept a few extra blank spaces to preserve the resemblance to the non-obfuscated version. But I still think it might be interesting since it's a different approach to the problem.

The non-obfuscated version:

```
palindrome([_]).
palindrome([X, X]).
palindrome([X | Xs]) :-
    append([Prefix, [X]], Xs),
    palindrome(Prefix).

palindrome_split(Prefix, Mid, Suffix, Prefix, N) :-
    palindrome(Prefix),
    append([Mid, Suffix], N).
palindrome_split(Prefix, Mid, Suffix, Suffix, N) :-
    palindrome(Suffix),
    append([Prefix, Mid], N).
palindrome_split(Prefix, Mid, Suffix, P, Mid) :-
    append([Prefix, Suffix], P),
    palindrome(P).

palindrome_downgrade(NP, P, N):-
    findall(
        [La, Pa, Na],
        (append([Prefix, Mid, Suffix], NP),
         palindrome_split(Prefix, Mid, Suffix, Pa, Na),
         length(Pa, La)),
        Palindromes),
    sort(1, @>, Palindromes, [[_, P, N] | _]).

```

# Answer
> 2 votes
## C++, ~~254~~ ~~248~~ 246 bytes

-6 bytes thanks to Zacharý -2 bytes thanks to Toby Speight

```
#include<string>
#define S size()
#define T return
using s=std::string;int p(s t){for(int i=0;i<t.S;++i)if(t[i]!=t[t.S-i-1])T 0;T 1;}s d(s e){if(!p(e))for(int i,w=1;w<e.S;++w)for(i=0;i<=e.S-w;++i){s t=e;t.erase(i,w);if(p(t))T e.substr(i,w);}T"";}

```

So...

* I used `T` as a macro definition because doing `R""` as another effect on string literal ( it's a prefix used to define raw string literals, see cppreference for more informations ) that is not there when i do `T""`
* Preprocessor definitions can't be on the same line, and have to have at least one space between the name and the content in the definition
* 2 functions : `p(std::string)` to test if the string is a palindrome. If it is, it returns `1` which casts to `true`, else it returns `0`, which casts to `false`
* The algorithm loops over the whole string testing if it's a palindrome when erasing each time 1 element, then test erasing 2 elements ( loops over that to the maximum size of the string ), from the first index to `the last index - number of erased char`. If it finds erasing some part is a palindrome, then, it returns. For example, when passing the string `"aabcdbaa"` as parameter, both `c` and `d` are valid answer, but this code will return `c` because erasing it and testing if it's a palindrome comes before testing if erasing `d` and testing if it's palindrome
* Here is the code to test :

```
std::initializer_list<std::pair<std::string, std::string>> test{
    {"800233008","2"},
    { "racecarFOOL","FOOL" },
    { "abcdedcba","" },
    { "ngryL Myrgn","L " },
    { "123456789","12345678" },
    { "aabcdbaa","c" },
    { "[[]]","[[" },
    { "a","" },
    { "aabaab","b" }
};

for (const auto& a : test) {
    if (a.second != d(a.first)) {
        std::cout << "Error on : " << a.first << " - Answer : " << a.second  << " - Current : " << d(a.first) << '\n';
    }
}

```

# Answer
> 1 votes
# Jelly, 33 bytes

```
r/ḟ@J}ị
“”µJp`ç³$ŒḂ$Ðfạ/ÞḢr/ịµŒḂ?

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES6), ~~91~~ 78 bytes

```
(s,i=0,j=0,S=[...s],b=S.splice(i,j))=>S+''==S.reverse()?b:f(s,s[++i]?i:!++j,j)

```

Input and output are lists of characters.

Recursively removes a larger and larger slice from the input until a palindrome is found.

**Snippet:**

```
f=
(s,i=0,j=0,S=[...s],b=S.splice(i,j))=>S+''==S.reverse()?b:f(s,s[++i]?i:!++j,j)

console.log(f([...'800233008']).join``)   // 2
console.log(f([...'racecarFOOL']).join``) // FOOL
console.log(f([...'abcdedcba']).join``)   // (empty string)
console.log(f([...'ngryL Myrgn']).join``) // "L " (or " M")
console.log(f([...'123456789']).join``)   // 12345678 (or 23456789)
console.log(f([...'aabcdbaa']).join``)    // c (or d)
console.log(f([...'[[]]']).join``)        // [[ (or ]])
console.log(f([...'a']).join``)           // (empty string)
```

# Answer
> 1 votes
# PHP 104+1 bytes

```
while(~($s=$argn)[$e+$i++]?:++$e|$i=0)strrev($t=substr_replace($s,"",$i,$e))==$t&&die(substr($s,$i,$e));

```

Run as pipe with `-nR` or try it online.

# Answer
> 1 votes
# Perl 5, 72 +1 (-p) bytes

```
$\=$_;/.*(?{$,=$`.$';$\=$&if length$&<length$\&&$,eq reverse$,})(?!)/g}{

```

Try it online

# Answer
> 1 votes
# Haskell, ~~109~~ 105 bytes

```
snd.minimum.([]#)
p#s@(a:b)=[(i,take i s)|i<-[0..length s],(==)<*>reverse$p++drop i s]++(p++[a])#b
p#_=[]

```

Try it online!

EDIT: Thanks @H.PWiz for taking off 4 bytes! I need to get better with those monads!

# Answer
> 1 votes
# Haskell, ~~98~~ ~~94~~ ~~81~~ 80 bytes

```
""#0
(h#n)t|(==)=<<reverse$h++drop n t=take n t|x:r<-t=(h++[x])#n$r|m<-n+1=t#m$h

```

Try it online! Example usage: `""#0 $ "aabaab"` yields `"b"`.

*Edit: -1 byte thanks to Ørjan Johansen.*

# Answer
> 1 votes
# JavaScript, 90 bytes

```
a=>a.map((_,p)=>a.map((_,q)=>k||(t=(b=[...a]).splice(q,p),k=''+b==b.reverse()&&t)),k=0)&&k

```

Try it online!

```
f=
a=>a.map((_,p)=>a.map((_,q)=>k||(t=(b=[...a]).splice(q,p),k=''+b==b.reverse()&&t)),k=0)&&k

F=a=>console.log(a.padEnd(11)+' ---> '+f([...a]).join``)
F('800233008')
F('racecarFOOL')
F('abcdedcba')
F('ngryL Myrgn')
F('123456789')
F('aabcdbaa')
F('[[]]')
F('a')
F('aabaab')
```

# Answer
> 1 votes
# TSQL (2016) 349B

Not the most compact but straightforward solution:

```
DECLARE @i VARCHAR(255)='racecarFOOL'
;WITH DAT(v,i,l)AS(SELECT value,(ROW_NUMBER()OVER(ORDER BY value))-1,LEN(@i)FROM STRING_SPLIT(REPLICATE(@i+';',LEN(@i)+1),';')WHERE value<>'')
SELECT TOP 1C,S
FROM(SELECT LEFT(D.v, D.i)+SUBSTRING(D.v,D.i+E.i+1,D.l)C,SUBSTRING(D.v,D.i+1,E.i)S
FROM DAT D CROSS APPLY DAT E)C
WHERE C=REVERSE(C)
ORDER BY LEN(C)DESC

```

# Answer
> 1 votes
# C++, ~~189~~ ~~186~~ ~~176~~ 167 bytes

I started with HatsuPointerKun's answer, changing the test to simply compare equality with reversed string; then I changed how we enumerate the candidate strings. Following this, the macros were only used once or twice each, and it was shorter to inline them.

```
#include<string>
using s=std::string;s d(s e){for(int i,w=0;;++w){s t=e.substr(w);for(i=-1;++i<=t.size();t[i]=e[i])if(t==s{t.rbegin(),t.rend()})return e.substr(i,w);}}

```

## Explanation

Equivalent readable code:

```
std::string downgrade(std::string e)
{
    for (int w=0; ; ++w) {
        std::string t = e.substr(w);
        for (int i=0;  i<=t.size();  ++i) {
            if (t == std::string{t.rbegin(),t.rend()})
                // We made a palindrome by removing w chars beginning at i
                return e.substr(i,w);
            t[i] = e[i];  // next candidate
        }
    }
}

```

The enumeration of candidates begins by initialising a string with the first `w` characters omitted, and then copying successive characters from the original to move the gap. For example, with the string `foobar` and `w`==2:

```
foobar
  ↓↓↓↓
  obar

```

```
foobar
↓
fbar

```

```
foobar
 ↓
foar

```

```
foobar
  ↓
foor

```

```
foobar
   ↓
foob

```

The first pass (with `w`==0) is a no-op, so the full string will be considered over and over again. That's fine - golfing trumps efficiency! The last iteration of this loop will access the one-past-the-end index; I seem to get away with that with GCC, but strictly, that's Undefined Behaviour.

## Test program

A direct lift from HatsuPointerKun's answer:

```
static const std::initializer_list<std::pair<std::string, std::string>> test{
    { "800233008", "2" },
    { "racecarFOOL", "FOOL" },
    { "abcdedcba", "" },
    { "ngryL Myrgn", "L " },
    { "123456789", "12345678" },
    { "aabcdbaa", "c" },
    { "[[]]", "[[" },
    { "a","" },
    { "aabaab", "b" }
};

#include <iostream>
int main()
{
    for (const auto& a : test) {
        if (a.second != d(a.first)) {
            std::cout << "Error on: " << a.first
                      << " - Expected: " << a.second
                      << " - Actual: " << d(a.first) << '\n';
        }
    }
}

```

# Answer
> 1 votes
# Husk, 18 bytes

```
◄LfmS=↔†!⁰ṠM-Qŀ⁰Q⁰

```

Try it online!

## Explanation

```
◄LfmS=↔†!⁰ṠM-Qŀ⁰Q⁰  Input is a string, say s="aab"
              ŀ⁰    Indices of s: x=[1,2,3]
             Q      Slices: [[],[1],[1,2],[2],[1,2,3],[2,3],[3]]
          ṠM-       Remove each from x: [[1,2,3],[2,3],[3],[1,3],[],[1],[1,2]]
       †!⁰          Index into s: ["aab","ab","b","ab","","a","aa"]
   mS=↔             Check which are palindromes: [0,0,1,0,1,1,1]
  f             Q⁰  Filter the slices of s by this list: ["aa","aab","ab","b"]
◄L                  Minimum on length: "b"

```

# Answer
> 0 votes
# Ruby, ~~86~~ 84 bytes

```
->s{l=i=0
(l+=(i+=1)/z=s.size-l+1
i%=z)while(w=s[0,i]+s[i+l..-1])!=w.reverse
s[i,l]}

```

Try it online!

* Saved 2 bytes thanks to Cyoce

# Answer
> 0 votes
## REXX, 132 bytes

```
a=arg(1)
l=length(a)
do i=1 to l
  do j=0 to l-i+1
    b=delstr(a,i,j)
    if b=reverse(b) & m>j then do
      m=j
      s=substr(a,i,j)
      end
    end
  end
say s

```

# Answer
> 0 votes
# C (gcc), 307 bytes

```
#define T malloc(K)
P(S,i,y,z,k,u,L,K,V)char*S;{char*M,*R,*E;K=strlen(S);M=T;R=T;E=T;for(i=0;i<K;++i){for(y=0;y<=K-i;++y){strcpy(M,S);for(z=y;z<y+i;E[z-y]=M[z],++z);for(k=y;k+i<=K;M[k]=M[k+i],++k);V=strlen(M);strcpy(R,M);for(u=0;u<V/2;L=R[u],R[u]=R[V-u-1],R[V-u-1]=L,++u);if(!strcmp(M,R))puts(E),exit(0);}}}

```

Try it online!

---
Tags: code-golf, string, palindrome
---


# Question
Title: The lowest initial numbers in a Fibonacci-like sequence
Given a positive integer input **N**, output the two non-negative numbers, **a** and **b**, where **a \< b**, with the lowest possible mean value that will result in the number **N** being part of the recurring relation sequence:

```
f(0) = a
f(1) = b
f(n) = f(n-2)+f(n-1)

```

~~In case there are more than one solution where the mean of **a** and **b** are minimal, then you should output the one with the lowest **b**.~~ Proof that this is not possible is provided by cardboard\_box.

Your can assume **N** is within the representative range of integers in your language / system.

### Test cases

```
N = 1
a = 0, b = 1

N = 15
a = 0, b = 3

N = 21
a = 0, b = 1

N = 27
a = 0, b = 9   <- Tricky test case. [3, 7] is not optimal and [4, 3] is not valid

N = 100
a = 4, b = 10

N = 101
a = 1, b = 12

N = 102
a = 0, b = 3

N = 1000
a = 2, b = 10

```

# Answer
> 9 votes
# Husk, ~~19~~ ~~18~~ ~~16~~ ~~14~~ ~~13~~ 15 bytes

Thanks Zgarb for saving 1 byte.

```
ḟö£⁰ƒẊ++ÖΣṖ2Θḣ⁰

```

Try it online!

### Explanation:

**Disclaimer:** I really don't understand the `ȯƒẊ++` section of the code.

Edit: It appears to translate to the Haskell `fix.(mapad2(+).).(++)`, where `mapad2` is apply function to all adjacent pairs in a list. (Although, knowing Husk, in the context of this program it could mean something else)

```
            Θḣ⁰    Create the list [0..input]
          Ṗ2       Generate all possible sublists of length 2
        ÖΣ         Sort them on their sums
ḟ                  Find the first element that satisfies the following predicate.
    ƒẊ++             Given [a,b], magically generate the infinite Fibonacci-like
                     sequence from [a,b] without [a,b] at the start.
 ö£⁰                 Is the input in that list (given that it is in sorted order)?

```

# Answer
> 8 votes
# APL (Dyalog), ~~75~~ ~~71~~ ~~64~~ ~~59~~ ~~53~~ ~~48~~ ~~44~~ 43 bytes

*2 bytes saved thanks to @Adám*

*12 bytes saved thanks to @ngn*

```
⊃o/⍨k∊¨+\∘⌽⍣{k≤⊃⍺}¨o←a/⍨</¨a←,⍉|-\¨⍳2⍴1+k←⎕

```

Try it online!

Uses `⎕IO←0`.

**How?** *This had gone real nuts.*

`k←⎕` \- assign input to `k`

`⍳2⍴1+k←⎕` \- Cartesian product of the range `0` to `k` with itself

`|-\¨` \- substract each right pair element from the left, and get absolute values

`a←,⍉` \- transpose, flatten and assign to `a`

`o←a/⍨</¨a` \- keep only pairs where the left element is smaller than the right, and assign to `o`

`o` now contains list of all pairs with `a < b`, ordered by their arithematical mean

`+\∘⌽⍣{k≤⊃⍺}¨o` \- for each pair in `o`, apply fibonacci (reverse the pair and cumsum) until `k` or higher term is reached

`k∊¨` \- then decide if `k` is this last term (meaning it is contained in the sequence)

`o/⍨` \- and keep pairs in `o` where the previous check applies

\- return the first result.

# Answer
> 8 votes
# JavaScript (Node.js), 92 90 89 91 83 82 bytes

-3 bytes -1 byte thanks to ThePirateBay

-8 -9 bytes thanks to Neil.

```
f=(n,a=1,b=0,c=(a,b)=>b<n?c(a+b,a):b>n)=>c(a,b)?b+2<a?f(n,a-1,b+1):f(n,b-~a):[b,a]

```

Try it online!

Note: this solution relies on the fact that there are never multiple minimal solutions.

# Proof that there are never multiple solutions:

Let `FIB(a,b,k)` be the Fibonacci-like sequence starting with `a,b`:

```
FIB(a,b,0) = a
FIB(a,b,1) = b
FIB(a,b,k) = FIB(a,b,k-1) + FIB(a,b,k-2)

```

## Lemma 1

The difference between Fibonacci-like sequences is itself Fibonacci-like, i.e. `FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k)`. The proof is left to reader.

## Lemma 2

For `n >= 5`, a solution `a,b` exists satisfying `a+b < n`:

if `n` is even, `FIB(0,n/2,3) = n`

if `n` is odd, `FIB(1,(n-1)/2,3) = n`

## Proof

Cases where `n < 5` can be checked exhaustively.

Suppose we have two minimal solutions for `n >= 5`, `a0,b0` and `a1,b1` with `a0 + b0 = a1 + b1` and `a0 != a1`.

Then there exist `k0,k1` such that `FIB(a0,b0,k0) = FIB(a1,b1,k1) = n`.

* Case 1: `k0 = k1`

WLOG assume `b0 < b1` (and therefore `a0 > a1`)

Let `DIFF(k)` be the difference between the Fibonnaci-like sequences starting with `a1,b1` and `a0,b0`:

`DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k)` (Lemma 1)

`DIFF(0) = a1 - a0 < 0`

`DIFF(1) = b1 - b0 > 0`

`DIFF(2) = (a1+b1) - (a0+b0) = 0`

`DIFF(3) = DIFF(1) + DIFF(2) = DIFF(1) > 0`

`DIFF(4) = DIFF(2) + DIFF(3) = DIFF(3) > 0`

Once a Fibonnaci-like sequence has 2 positive terms, all subsequent terms are positive.

Thus, the only time `DIFF(k) = 0` is when `k = 2`, so the only choice for `k0 = k1` is `2`.

Therefore `n = FIB(a0,b0,2) = a0 + b0 = a1 + b1`

The minimality of these solutions contradicts Lemma 2.
* Case 2: `k0 != k1`:

WLOG assume `k0 < k1`.

We have `FIB(a1,b1,k1) = n`

Let `a2 = FIB(a1,b1,k1-k0)`

Let `b2 = FIB(a1,b1,k1-k0+1)`

Then `FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0)` (exercise for the reader)

Since `FIB(a1,b1,k)` is non-negative for `k >= 0`, it is also non-decreasing.

This gives us `a2 >= b1 > a0` and `b2 >= a1+b1 = a0+b0`.

Then let `DIFF(k) = FIB(a2,b2,k) - FIB(a0,b0,k) = FIB(a2-a0,b2-b0,k)` (Lemma 1)

`DIFF(0) = a2 - a0 > 0`

`DIFF(1) = b2 - b0 >= (a0 + b0) - b0 = a0 >= 0`

`DIFF(2) = DIFF(0) + DIFF(1) >= DIFF(0) > 0`

`DIFF(3) = DIFF(1) + DIFF(2) >= DIFF(2) > 0`

Once again, `DIFF` has 2 positive terms and therefore all subsequent terms are positive.

Thus, the only time when it's possible that `DIFF(k) = 0` is `k = 1`, so the only choice for `k0` is `1`.

`FIB(a0,b0,1) = n`

`b0 = n`

This contradicts Lemma 2.

# Answer
> 8 votes
# Haskell, ~~76 72~~ 74 bytes

EDIT:

* -4 bytes: @H.PWiz suggested using `/` instead of `div`, although this requires using a fractional number type.
* +2 bytes: Fixed a bug with `Enum` ranges by adding `-1`.

`f` takes a value of `Double` or `Rational` type and returns a tuple of same. `Double` should suffice for all values that are not large enough to cause rounding errors, while `Rational` is theoretically unlimited.

```
f n|let a?b=b==n||b<n&&b?(a+b)=[(a,s-a)|s<-[1..],a<-[0..s/2-1],a?(s-a)]!!0

```

Try it online! (with H.PWiz's header adjustments to input/output `Rational`s in integer format)

# How it works

* `?` is a locally nested operator in the scope of `f`. `a?b` recursively steps through the Fibonacci-like sequence starting with `a,b` until `b>=n`, returning `True` iff it hits `n` exactly.
* In the list comprehension:
    + `s` iterates through all numbers from `1` upwards, representing the sum of `a` and `b`.
    + `a` iterates through the numbers from `0` to `s/2-1`. (If `s` is odd the end of range rounds up.)
    + `a?(s-a)` tests if the sequence starting with `a,s-a` hits `n`. If so, the list comprehension includes the tuple `(a,s-a)`. (That is, `b=s-a`, although it was too short to be worth naming.)
    + `!!0` selects the first element (hit) in the comprehension.

# Answer
> 5 votes
# Python 2, ~~127~~ ~~109~~ 107 bytes

*-2 bytes thanks to ovs (changing `and` to `*`)*

```
g=lambda x,a,b:a<=b<x and g(x,b,a+b)or b==x
f=lambda n,s=1,a=0:g(n,a,s-a)*(a,s-a)or f(n,s+(a==s),a%s+(a<s))

```

**Try it online!**

Any bonus points for `n,a,s-a`?

### Explanation:

* The first line declares a recursive lambda, `g`, which verifies whether `a, b` expanded as a Fibonacci sequence will reach `x`. It also checks that `a <= b`, one of the criteria of the question. (This would allow cases where `a == b`, but in such a case `0, a` would have already been discovered and returned).
    + The chained inequality `a<=b<x` performs two handy tasks at once: verifying `a <= b`, and that `b < x`.
    + If `b < x` yields `True`, the function calls itself again with the next two numbers in the Fibonacci sequence: `b, a+b`. This means the function will keep working out new terms until...
    + If `b < x` yields `False`, then we have reached the point where we need to check if `b==x`. If so, this will return `True`, signifying that the initial pair `a, b` will eventually reach `x`. Otherwise, if `b > x`, the pair is invalid.
* The second line declares another recursive lambda, `f`, which finds the solution for a given value `n`. It recursively tries new initial pairs, `a, b`, until `g(n, a, b)` yields `True`. This solution is then returned.
    + The function recursively counts up initial Fibonacci pairs using two variables, `s` (initially 1) and `a` (initially 0). On each iteration, `a` is incremented, and `a, s-a` is used as the first pair. However, when `a` hits `s`, it is reset back to 0, and `s` is incremented. This means the pairs are counted up in the following pattern:
    ```
    s=1 (0, 1) (1, 0)
    s=2 (0, 2) (1, 1)  (2, 0)
    s=3 (0, 3) (1, 2), (2, 1), (3, 0)

    ```
    Obviously, this contains some invalid pairs, however these are eliminated instantly when passed to `g` (see first bullet point).
    + When values `a` and `s` are found such that `g(n, a, s-a) == True`, then this value is returned. As the possible solutions are counted up in order of 'size' (sorted by mean, then min value), the first solution found will always be the smallest, as the challenge requests.

# Answer
> 3 votes
# , ~~183 bytes~~ 160 bytes

```
n=scan();e=expand.grid(n:0,n:0);e=e[e[,2]>e[,1],];r=e[mapply(h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),n,e[,1],e[,2]),];r[which.min(rowSums(r)),]

```

Try it online!

**Thanks to Giuseppe for golfing off 23 bytes**

Code explanation

```
n=scan()                        #STDIO input
e=expand.grid(n:0,n:0)          #full outer join of integer vector n to 0
e=e[e[,2]>e[,1],]               #filter so b > a
r=e[mapply(
  h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),
                                #create a named recursive function mid-call
                                #(requires using <- vs = to denote local variable creation
                                #rather than argument assignment
  n,e[,1],e[,2]),]              #map n, a and b to h() which returns a logical
                                #which is used to filter the possibilities
r[which.min(rowSums(r)),]       #calculate sum for each possibility,
                                #get index of the minimum and return
                                #because each possibility has 2 values, the mean and
                                #sum will sort identically.

```

# Answer
> 1 votes
# Jelly, 19 bytes

```
ṫ-Sṭµ¡³e
0rŒcÇÐfSÐṂ

```

Try it online!

-1 byte thanks to the proof by cardboard\_box. In case it's disproved, you can append `UṂṚ` to the end of the second line for 22 bytes in total.

# Answer
> 1 votes
# Mathematica, 117 bytes

```
If[#==1,{0,1},#&@@SortBy[(S=Select)[S[Range[0,s=#]~Tuples~2,Less@@#&],!FreeQ[LinearRecurrence[{1,1},#,s],s]&],Mean]]&

```

Try it online!

# Answer
> 1 votes
## GolfScript \- ~~88~~ 77 bytes

```
~:N[,{1+:a,{[.;a]}/}/][{[.~{.N<}{.@+}while\;N=]}/]{)1=\;},{(\;~+}$(\;);~~' '\

```

I did not check for multiple solutions, thanks to cardboard\_box!

### Explanation

```
~:N                           # Reads input
[,{1+:a,{[.;a]}/}/]           # Creates an array of pairs [a b]
[{[.~{.N<}{.@+}while\;N=]}/]  # Compute solutions
{)1=\;},         # Pairs that are not solutions are discarded
{(\;~+}$         # Sorts by mean
(\;);~~' '\      # Formats output

```

# Answer
> 0 votes
## Batch, ~~160~~ 158 bytes

```
@set/aa=b=0
:g
@if %a% geq %b% set/ab-=~a,a=0
@set/ac=a,d=b
:l
@if %c% lss %1 set/ad+=c,c=d-c&goto l
@if %c% gtr %1 set/aa+=1,b-=1&goto g
@echo %a% %b%

```

---
Tags: code-golf, number, sequence, fibonacci
---


title: Largest Deep Sum

text:
# Question
Title: Largest Deep Sum
Given an *n*-dimensional array filled with numbers, output which *p*-dimensional array has the largest sum.

# Input

* An *n*-dimensional array of numbers, or your language's equivalent. You can assume this is a rectangular array, or not.
* *n*, the number of dimensions in the array. (doesn't need to be called `n`)
* *p*, the number of dimensions in the arrays you are adding up. (doesn't need to be called `p`)

# Output

The respective indices of the *p*-dimensional array with the largest sum. You may have undefined behavior in the case of a tie. The dimensions of the array that you find should be the last *p* dimensions of the original array.

# Test Cases

Input:

```
[[[4,2],
  [6,8]],

 [[0,0],
  [500,327]]], 3, 2

```

Output:

```
1

```

Input:

```
[[1,2],
 [4,3]], 2, 0

```

Since *p*=0, you're just finding the largest number in the array, which in this case is 4. The coordinates are:

```
1 0

```

Input:

```
[[1,2],
 [4,-1]], 2, 1

```

You might see the 1 and 4 in the same column, and that that would have the largest sum of 5. However, because those share the second index, not the first, they are ignored. Both of the rows in this array add to 3, resulting in a tie, so you can return whatever you want here.

---

Input:

```
[[1,2],
 [3,4]], 2, 2

```

Since *p*=*n*, there are no indices of the array with the largest sum, so the output would be empty.

# Additional Rules

# Answer
> 3 votes
# APL (Dyalog), 21 bytes

```
(⍴⊤⊃∘⍒∘,)+/,⍤⎕⊢⎕

```

First input is the array, second is `p`.

Try it online!

**How?**

`+/,⍤⎕` \- apply sum over sub arrays of rank `p`

`⊃∘⍒∘,` \- flatten, grade down and take first

`⍴⊤` \- encode in the mixed base derived by the shape of the previous result

# Answer
> 4 votes
## Wolfram Language (Mathematica), 36 bytes

```
#~Position~Max@#&@Total[#,{-#2,-1}]&

```

Try it online!

Returns an array containing all the indices where the maximum value can be found. So for normal inputs that's a singleton array, containing the list of indices to it. If there's a tie, you'll get all the lists of indices for where that value shows up.

The function doesn't actually read the `n` parameter, because it isn't needed, but you could pass it in as a third argument if you like (it would just be ignored anyway).

One catch here is that for some reason the dimension specification `{0,-1}` for `Total` never sums anything. I don't really understand why, but luckily that's just what we need for this challenge.

# Answer
> 1 votes
# Python 3 \+ numpy, 92 bytes

```
lambda a,n,p:unravel_index(argmax(sum(a,(*-arange(n-p,n),))),a.shape[p:])
from numpy import*

```

Try it online!

Quite a bit longer than I would have hoped. Errors out on cases with no solution.

# Answer
> 0 votes
# Python 3, 138 bytes

There is probably a better way of doing this

```
lambda x,n,p:f(x,n,p)[:0:-1]
f=lambda x,n,p:n>p and max([*f(l,n-1,p),i]for i,l in enumerate(x))or[sum(f(l,n-1,p)[0]for l in x)if n else x]

```

Try it online!

---
Tags: code-golf, array
---