title: Pigeonhole Principle & Code Golf

text:
# Question
Title: Pigeonhole Principle & Code Golf
The pigeonhole principle states that

> If *N* items are put into *M* boxes, with *N* \> *M*, then at least one box must contain more than one item.

For many, this principle has a special status compared to other mathematical enouncements. As E.W. Dijkstra wrote,

> It is surrounded by some mystique. Proofs using it are often regarded as something special, something particularly ingenious.

## The challenge

The purpose of this challenge is to illustrate the pigeonhole principle using ASCII art representations. Specifically:

1. Take as input `N` (number of items) and `M` (number of boxes), with `N` non-negative and `M` positive. `N` may be smaller than `M` (even if the principle does not apply in that case).
2. Randomly select one of the possible assignments of items to boxes. Each assignment should have a non-zero probability of being picked.
3. Produce an ASCII art representation of the assignment as follows:

* There are `M` lines, each corresponding to a box.
    * Each line starts with a non-whitespace character, such as `|`.
    * Following that character is another non-whitespace character, such as `#`, repeated as many times as there are items in that box.

Consider for example `N = 8`, `M = 5`. If the selected assigment of items to boxes is `4`, `1`, `0`, `3`, `0`, the representation is

```
|####
|#
|
|###
|

```

A different run (resulting in a different assignment) of the same program could give

```
|#
|##
|#
|#
|###

```

There is some flexibility regarding the representation; see below.

## Specific rules

The code should **theoretically run for any values** of `N` and `M`. In practice it may be restricted by memory size or data type limitations.

Since observing the output is not sufficient to determine if all assignments have **non-zero probability**, each submission should explain how the code achieves that, if not obvious.

The following **representation variations** are allowed:

* Any pair of different, non-whitespace characters can be chosen. They must be consistent across program executions.
* 90-degree rotations of the representation are acceptable. Again, the choice must be consistent.
* Trailing or leading whitespace is allowed.

As an example with a different representation format, for `N = 15`, `M = 6` the results of two executions of the program could be

```
VVVVVV
@@@@@@
@@ @@@
 @  @@
    @

```

or

```
VVVVV
@@@ @
@@@ @
@ @ @
@ @ @
@

```

Likewise, `N = 5`, `M = 7` could give, using another variation of the representation,

```
  *
* * * *
UUUUUUU

```

or

```
 *** **
UUUUUUU

```

or

```
   *
*  *
*  *
UUUUUUU

```

Note how the principle is not applicable in this case, because `N` \<`M`.

## General rules

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

Input can be taken by any reasonable means; and with any format, such as an array of two numbers or two different strings.

Output means and format are also flexible. For example, the output can be a list of strings or a string with newlines; returned as function output argument or displayed in STDOUT. In the latter case it is not necessary to worry about line wrapping caused by limited display width.

Shortest code in bytes wins.

# Answer
> 4 votes
# Jelly, ~~9~~ 8 bytes

```
=þṗX¥S⁵*

```

This is a dyadic link that takes **M** as its left and **N** as its right argument. Output is an array of integers, where **0** represents pigeons and **1** represents holes.

Try it online!

### How it works

```
=þṗX¥S⁵*  Main link. Left argument: m. Right argument: n

    ¥     Combine the two links to the left into a dyadic chain and call it
          with arguments m and n.
  ṗ        Compute the n-th Cartesian power of [1, ..., m], i.e., generate all
           vectors of length n that consist of elements of [1, ..., m].
   X       Pseudo-randomly choose one of those vectors with a uniform distribution.
=þ        Equal table; for each k in [1, ..., m] and each vector to the right,
          compare the elements of the vector with k. Group the results by the
          vectors, yielding a 2D Boolean matrix.
     R    Range; map 1 to [1], 0 to [].
      S   Take the sum of all columns.
       ⁵* Raise 10 to the resulting powers.

```

# Answer
> 10 votes
## Mathematica, 68 bytes

```
Print/@(10^RandomSample@RandomChoice[IntegerPartitions[+##,{#}]-1])&

```

An unnamed function that takes two integer arguments, the number of boxes, followed by the number of items.

It first computes all possible partitions of `N+M` into exactly `M` positive parts, and subtracts `1` from each partition afterwards. This gives us all possible partitions of `N` into `M` non-negative parts (which `IntegerPartitions` wouldn't generate otherwise). Then pick a random partition and shuffle it. This guarantees all possible ordered partitions with zeros are allowed. Finally, convert each bin of the partition to an output line by raising 10 to the corresponding power (such that each line becomes `1000...` with `k` zeros). An example output might look like:

```
100
10000
1
10
10

```

# Answer
> 9 votes
# Python 2, 77 86 bytes

```
from random import*
n,m=input()
exec'c=randint(0,n);n-=c;print 10**c;'*~-m
print 10**n

```

Generates a number in \[0, n\], prints that many items and substracts it from n. It does this m times.

This makes it very unlikely anything makes it to the last box, but the question only asked that every output be *possible*, not *equally likely*.

# Answer
> 7 votes
## Batch, 164 bytes

```
@for /l %%i in (1,1,%1)do @set h%%i=1
@for /l %%j in (1,1,%2)do @call set/ab=%%random%%%%%%%1+1&call set/ah%%b%%*=10
@for /l %%i in (1,1,%1)do @call echo %%h%%i%%

```

I think 7 consecutive `%` signs might be a new personal best! Note: this produces odd output should it ever assign more than 9 items to the same box; if that's a problem, then for 180 bytes:

```
@for /l %%i in (1,1,%1)do @set h%%i=1
@for /l %%j in (1,1,%2)do @call set/ab=%%random%%%%%%%1+1&call call set h%%b%%=%%%%h%%b%%%%%%0
@for /l %%i in (1,1,%1)do @call echo %%h%%i%%

```

Yes, that's 28 `%`s in total on the second line.

# Answer
> 5 votes
# C, 102 bytes

```
n,m;main(x){srand(time(0));for(scanf("%d %d",&n,&m);m--;n-=x)printf("|%0*s\n",x=m?rand()%(n+1):n,"");}

```

Takes input on stdin, e.g.:

```
echo "5 4" | ./pigeonhole

```

Won't generate each output with equal probability, but is capable of generating all possible combinations.

### Breakdown:

```
n,m;
main(x){
    srand(time(0));             // Seed random number generator
    for(scanf("%d %d",&n,&m);   // Parse input values into n and m
        m--;                    // Loop through each bucket (count down)
        n-=x)                   // Subtract number assigned to bucket from total
        printf(                 // Output a formatted string using padding
            "|%0*s\n",          // (turns out %0s will actually zero-pad a string!)
            x=m?rand()%(n+1):n, // Calculate a number of items for this bucket
            "");
}

```

Relies on GCC's handling of the undefined behaviour of `%0s` — normally `%0` will zero-pad an integer or float, but it can only pad (never truncate), so it's not possible to print a blank. But the behaviour for strings isn't defined, and GCC decided to make it zero-pad the same way, so this zero-pads an empty string to be able to write zero-or-more `0`s.

# Answer
> 3 votes
# Python 2, ~~102~~ ~~99~~ ~~97~~ 90 bytes

`m-1` times, chose a random amount `x` between `0` and `n`, inclusive and subtract it from n. Then print a `1` and `'0'*x`.

Finally, print `1` and the rest of `0`s. Not at all equal chances, but all configurations are possible.

```
from random import*
n,m=input()
exec'x=randrange(n+1);n-=x;print 10**x;'*(m-1)
print 10**n

```

(Reused code from the broken Python answer.)

# Answer
> 3 votes
# Haskell, ~~114~~ 94 bytes

```
import System.Random
n#m=map(10^).take m.until((==n).sum.take m)tail.randomRs(0,m)<$>newStdGen

```

A bit of a brute force approach: Generates an infinite list of random numbers, takes n numbers of the start of the list, sums them up, and checks if they're equal to m. If not, take the first element off the list and repeat.

Try it online!

Note: 73 bytes without the import

EDIT: Saved some bytes with the 10^ trick (Try the new version online!)

# Answer
> 2 votes
# C, ~~175~~ 138 bytes

*Thanks to @Dave for saving 37 bytes!*

```
i;f(n,m){char**l=calloc(m,8);for(i=0;i<m;)l[i]=calloc(n+1,1),*l[i++]=124;for(i=n+1;--i;)*strchr(l[rand()%m],0)=35;for(;i<m;)puts(l[i++]);}

```

Try it online!

# Answer
> 2 votes
## CJam, ~~30~~ ~~31~~ 21 bytes

```
:B1a*:C\{CBmrAt.*}*N*

```

Input is two numbers `n m` on the stack. Uses `1` for the column character and `0` for the repeated character.

Explanation:

```
:B          e# Store m in B (without deleting it from the stack)
1a          e# Push 1 and wrap it in an array: [1]
*           e# Repeat the array m times
:C          e# Store this array in C (without deleting)
\{          e# Do n times:
  CBmrAt    e#   Create an array of 1s with a random element replaced with 10.
  .*        e#   Vectorized multiplication: multiply the respective elements in the arrays.
            e#   Effectively, we multiply a random value in the array by 10 (and add a 0 to the end).
}*          e# End loop.
N*          e# Join with newlines.

```

# Answer
> 2 votes
## REXX, 74 bytes

```
arg n m
m=m-1
o.=@
do n
  a=random(m)
  o.a=o.a||#
  end
do a=0 to m
  say o.a
  end

```

Output (8 5):

```
@#
@###
@
@#
@###

```

Output (8 5):

```
@#
@#
@
@####
@##

```

# Answer
> 2 votes
# AHK, 66 bytes

```
2-=1
Loop,%2%{
Random,r,0,%1%
Send,|{# %r%}`n
1-=r
}
Send,|{# %1%}

```

I followed the same principal that orlp did using random numbers from 0 to N and then subtracting it from N. Unfortunately, I couldn't save bytes by using 10^r because of the way the Send function works. Alas and alack. Here are some outputs for n=8, m=5:

```
|##     |#####    |##       |##     |#      |##
|##     |#        |#####    |       |###    |#
|#      |##       |         |###    |###    |
|###    |         |         |       |#      |
|       |         |#        |###    |       |#####

```

# Answer
> 1 votes
# Röda, 79 bytes

```
f n,m{a=[0]*m
i=0{{n--
a[i%m]++}if randomBoolean
i++}while[n>0]
a|[`|`.."#"*_]}

```

Try it online!

This creates an array of zeroes and increments them at random places.

# Answer
> 1 votes
# Python 2, 80 95 89 88 bytes

```
from random import*
n,m=input()
while m:x=randint(0,n);print'1'+'0'*[n,x][m>1];m-=1;n-=x

```

Try it online!

* Added 15 Bytes: Previous edit was a bit flawed, some piegons were left out.
* Saved 6 Bytes: replaced if else by \[n,x\]\[m\>1\]
* Saved 1 Byte: import *

# Answer
> 1 votes
# JavaScript, 105 bytes

```
x=>y=>{s=[];for(;x>1;y-=t)s[--x]="|"+"#".repeat(t=Math.random()*(y+1)|0);s[0]="|"+"#".repeat(y);return s}

```

Try it online!

Due to the method of assigning the rows, this will tend to place more towards the bottom, although there is a small chance that the top will get some.

# Answer
> 1 votes
# PHP, 100 bytes

```
list($z,$m,$n)=$argv;$a=array_fill(0,$n,z);while($m>0){$a[rand(0,$n-1)].=a;$m--;}echo join("\n",$a);

```

**Breakdown :**

```
list($z,$m,$n)=$argv;     // assigns the input vars to $m and $n
$a=array_fill(0,$n,z);    // creates an array $a of $n elements containing 'z'
while($m>0){              // randomly populate array $a
    $a[rand(0,$n-1)].=a;  //
    $m--;                 //
}                         //
echo join("\n",$a);       // output $a contents separated by a new line

```

Outputs for `m=7` and `n=5` :

First execution :

```
za
zaa
za
za
zaa

```

Second execution :

```
za
zaa
zaaa
z
za

```

Try it online!

# Answer
> 1 votes
# Ruby, 52 bytes

```
->(n,m){r=Array.new(m){?|};n.times{r[rand m]+=?#};r}

```

Creates an anonymous function which takes two integers as arguments and returns an array of Strings:

```
>> puts ->(n,m){r=Array.new(m){?|};n.times{r[rand m]+=?#};r}.call 7,5
|#
|#
|##
|##
|#

```

# Answer
> 1 votes
## MATLAB, ~~103~~ 94 bytes

```
function a(m,n)
d=@(p)disp(char([1,~(1:p)]+48));for i=1:m-1;p=randi([0,n]);d(p);n=n-p;end;d(n)

```

### With Formatting

```
function a(m,n)
for i=1:m-1
    d=@(p)disp(char([1,~(1:p)]+48));  % inline function for displaying
    p=randi([0,n]);              % picking a random number b/w 0 and n
    d(p);                        % '1' represents the box/pigeonhole, with '0's denoting entries
    n=n-p;
end
d(n);                            % writing the remaining entries/zeros

```

### Sample Output

```
>> a(4,7)
10
10000
10
10

```

There are trailing whitespaces since each array entry is displayed with a tab between them, but this should be acceptable as per specs.

This seems like a very simplistic implementation to me, so I'm sure this could be improved.

Thanks to @Luis Mendo for suggestions.

# Answer
> 1 votes
# TI-Basic, ~~63~~ 62 bytes

```
Prompt N,M
For(A,1,M
N→B
If M-A
randInt(0,N→B
":→Str0
For(C,1,B
Ans+"X→Str0
End
Disp Ans
N-B→N
End

```

> Each assignment should have a non-zero probability of being picked.

This criteria made this program much easier to write.

Example I/O:

```
prgmPIDGEON
N=?5
M=?2
:XXXX
:X

```

Explanation:

```
Prompt N,M     # 5 bytes, input number of items, number of boxes
For(A,1,M      # 7 bytes, for each box
N→B            # 4 bytes, on last box, make sure the sum is met by adding N items
If M-A         # 5 bytes, if not last box
randInt(0,N→B  # 8 bytes, add random number of items from 0 to N to box A
":→Str0        # 6 bytes, first character
For(C,1,B      # 7 bytes, add B items to the box
Ans+"X→Str0    # 8 bytes
End            # 2 bytes
Disp Ans       # 3 bytes, print this box
N-B→N          # 6 bytes, subtract the items used in this box
End            # 1 byte, move on to next box

```

# Answer
> 1 votes
## Python 2, 81 bytes

```
from random import*
def f(n,m):l=['#']*m;exec('l[randrange(m)]+="o";'*n);return l

```

Returns a list of strings.

# Answer
> 1 votes
## Javascript (ES7), 75 bytes

```
(N,M)=>{for(r='';M;M--,N-=x=~~(Math.random()*(N+1)),r+=10**x+`
`);return r}

```

I thought I was clever for coming up with the powers of 10 idea only to realize that most answers were already using that.

# Answer
> 1 votes
## AWK, 78 bytes

```
{srand();for(;n++;)c[k]=c[k=int($2*rand())]"#"}END{for(;j<$2;)print"|"c[j++]}

```

Takes 2 arguments, first the number of items, then the number of boxes. Starts by seeding the random number generator so each run is different. Then simply builds up strings in an array, Example usage:

```
awk '{srand();for(;n++;)c[k]=c[k=int($2*rand())]"#"}END{for(;j<$2;)print"|"c[j++]}' <<< "12 5"

Example output:
|##
|###
|##
|##
|###

```

# Answer
> 1 votes
# Octave, ~~62~~ 54 bytes

```
@(n,m)strcat(62,(sum(randi(m,1,n)==(1:m)',2)>=1:n)*42)

```

Anonymous function that takes two numbers and outputs a 2D array of chars with `>` for boxes and `*` for objects. All results are equally likely.

Try it online!

# Answer
> 1 votes
## MATLAB, ~~73~~ ~~64~~ 58 bytes

### Update#3

I do need the sorting, it seems, since otherwise I get negative integers. I did replace `disp(sprintf(...))` with `fprintf(...)` now, though, so the answer remains 58 bytes.

```
@(m,n)fprintf('%i\n',10.^diff([0;sort(randi(n,m-1,1));n]))

```

### Update#2:

I realized I didn't need to sort the array, and in fact sorting would actually reduce the average of numbers in the array. So I deleted the `sort(...)` part. Note that the output remains the same, so I am not updating the "sample output".

```
@(m,n)disp(sprintf('%i\n',10.^diff([0;randi(n,m-1,1);n])))

```

***Finally closing in on the Octave answer by Luis! :D***

### Update#1:

```
@(m,n)disp(sprintf('%i\n',10.^diff([0;sort(randi(n,m-1,1));n])))

```

Instead of converting to string, I just display numbers directly. I could reduce to 58 bytes, by removing the `disp(...)`, but then I get the extra `ans =` with just sprintf, and don't know if that's acceptable.

### Initial code:

```
@(m,n)disp(strjust(num2str(10.^diff([0;sort(randi(n,m-1,1));n])),'left'))

```

Thanks to some suggestions by Luis, I got rid of the loop in my previous answer. Now I first create a vertical array of `m` random numbers adding up to `n` (`diff([0;sort(randi(n,m-1,1));n])`), then use them as exponents of 10, convert them to a string, left-justify them, and display them.

I could technically get rid of the disp(...) to save another 6 bytes, but then an "ans" gets printed which may violate specs. There may also be a way around to changing them to string and left-justifying to get the desired end format, so I'm open to suggestions.

### Sample output:

```
>> a=@(m,n)disp(strjust(num2str(10.^diff([0;sort(randi(n,m-1,1));n])),'left'));
>> a(4,6)
1000
10
100
1

```

***Note***: I have changed my function to an anonymous function here, based on suggestions. In the sample output, I have assigned that to `a` in order to demonstrate. I hope this does not violate specs, but if it does please let me know and I will change it.

# Answer
> 1 votes
# Stacked, 29 bytes

```
('|')\rep\[:randin'#'push@.]*

```

Try it online!

Behaves by constructing an array of `M` singletons containing `'|'`, then adding `'#'` to a randomly chosen array `N` times.

# Answer
> 1 votes
# Charcoal, 19 bytes

```
≔ＥＮ⟦⟧θＦＮ⊞‽θ#Ｅθ⁺|⪫ιω

```

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

```
  Ｎ                 Input `M`
 Ｅ                  Map over implicit range
   ⟦⟧               Empty array
≔    θ              Assign resulting nested array to `q`

       Ｎ            Input `N`
      Ｆ             Loop over implicit range
          θ         Nested array `q`
         ‽          Random element
           #        Literal string
        ⊞           Append to array

             θ      Nested array `q`
            Ｅ       Map over array
                 ι  Current element
                  ω Empty string
                ⪫   Join
               |    Literal string
              ⁺     Concatenate
                    Implicitly print on separate lines

```

# Answer
> 1 votes
# Vyxal `j`, 19 bytes

```
Ṅ'L⁰≤;℅₅⁰εð*ƛ0;JÞ℅↵

```

Try it Online!

```
Ṅ                   # The partitions of the first number
 '   ;              # Filtered by...
  L⁰≤               # Length is less than or equal to the second input
      ℅             # Choose a random item of this
       ₅            # Get length
        ⁰εð*        # Subtract from second input, and get that many spaces
            ƛ0;     # Fill with 0s
               J    # Append this to the current string
                Þ℅  # Get a random permutation of this
                  ↵ # 10 to the power of each item of this

```

# Answer
> 1 votes
# Japt `-R`, ~~17 (15?)~~ 16 (14?) bytes

```
@¶Xx}a@ô öVÃ£ApX

```

Try it

If we don't have to allow for the possibility of all `N` items ending up in the same box then we can save 2 bytes:

```
@¶Xx}a@öVÃ£ApX

```

Try it

```
@¶Xx}a@ô öVÃ£ApX     :Implicit input of integers U=N & V=M
@                    :Left function, taking an array X as argument
 ¶                   :  Is U equal to
  Xx                 :  X reduced by addition
    }                :End function
     a               :Get the first result of the right function that returns true when passed through the left one
      @              :Right function
       ô             :  Range [0,U]
         öV          :  Get V random elements (or V random elements in [0,U) if ô is omitted)
           Ã         :End function
            £        :Map each X
             A       :  10
              pX     :  Raised to the power of X
                     :Implicit output joined with newlines

```

---
Tags: code-golf, ascii-art, random, integer
---


title: SKI calculus golf: Hello, World!

text:
# Question
Title: SKI calculus golf: Hello, World!
## Background

SKI combinator calculus, or simply SKI calculus, is a system similar to lambda calculus, except that SKI calculus uses a small set of *combinators*, namely `S`, `K`, and `I` instead of lambda abstraction. Unlike lambda calculus, beta reduction is possible only when a combinator is given enough arguments to reduce.

The three combinators in SKI calculus are defined as follows:

$$ \begin{aligned} S\\;x\\;y\\;z & \overset{S}{\implies} x\\;z\\;(y\\;z) \\ K\\;x\\;y & \overset{K}{\implies} x \\ I\\;x & \overset{I}{\implies} x \end{aligned} $$

For example, the SKI expression \\$ e=S(K(S\\;I))K \\$ is equivalent to the lambda expression \\$ λx.λy.y\\;x \\$, as applying two arguments to \\$ e \\$ reduces to the desired result:

$$ \begin{aligned} S(K(S\\;I))K\\;x\\;y & \overset{S}{\implies} (K(S\\;I)x)(K\\;x)y \\ & \overset{K}{\implies} S\\;I(K\\;x)y \\ & \overset{S}{\implies} (I\\;y)(K\\;x\\;y) \\ & \overset{I,K}{\implies} y\\;x \end{aligned} $$

It is known that any lambda expression can be converted to a SKI expression.

A Church numeral is an encoding of natural numbers (including zero) as a lambda expression. The Church encoding of a natural number \\$ n \\$ is \\$ λf. λx. f^n\\;x \\$ \- given a function \\$ f \\$ and an argument \\$ x \\$, \\$ f \\$ repeatedly applied to \\$ x \\$ \\$ n \\$ times.

It is possible to construct a lambda expression (and therefore a SKI expression) that performs various arithmetic (e.g. addition, multiplication) in Church encoding. Here are a few examples of Church numerals and Church arithmetic functions: (The given SKI expressions are possibly not minimal.)

$$ \begin{array}{r|r|r} \text{Expr} & \text{Lambda} & \text{SKI} \\ \hline 0 & λf. λx. x & K\\;I \\ 1 & λf. λx. f\\;x & I \\ 2 & λf. λx. f(f\\;x) & S (S (K\\;S) K) I \\ \text{Succ} \\; n & λn. λf. λx. f(n\\;f\\;x) & S (S (K\\;S) K) \\ m+n & λm. λn. λf. λx. m\\;f(n\\;f\\;x) & S (K\\;S) (S (K (S (K\\;S) K))) \end{array} $$

It is also possible to represent lists as lambda terms using right-fold encoding. For example, the list of numbers `[1, 2, 3]` is represented by the lambda term \\$λc. λn. c\\;1 (c\\;2 (c\\;3\\;n))\\$ where each number represents the corresponding Church numeral.

## Challenge

Write a SKI expression that evaluates to the string `Hello, World!`, i.e. the Church list of Church numerals representing the list

```
[72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33]

```

## Scoring and winning criterion

The score is the total number of `S`, `K`, and `I` combinators used. The submission with the lowest score wins.

Here is a Python script to check the correctness and score of your SKI expression.

# Answer
> 15 votes
# Score = 192

```
S(SI(K(S(S(SSI)I))))
(S(SI(K(S(SIS)(KS))))
 (S(SS)I(K(S(SI(K(S(S(SI(K(SS)))(K(KI))))))))
  (S(SI(K(SS(S(K(S(SI)))K))))
   (S(SI(K(S(SI(S(K(SIS)))))))
    (S(SI(K(S(S(S(S(SSI))))K)))
     (S(SI(K(SI(S(S(SS))I))))
      (S(SI(K(SS(S(K(S(SI)))K))))
       (S(SI(K(S(SI(SI(S(K(S(SI)))))))))
        (S(SI(K(S(S(SI(K(SS)))(K(KI))))))
         (S(SI(K(S(SII)(K(SS)))))
          (S(SI(K(K(S(S(S(S(SI)))(KI))))))
           (K(KI)))))))))))))
(S(KS)
 (S(K(S(K(S(KS)K))))
  (S(K(SI))
   (S(KK)
    (S
     (S
      (S
       (SS(S(S(KS)S))(KS))
       (KS))
      (K(S(KS)K)))
     (KI))))))

```

Try it online!

An attempt to factor out common expressions from the numerals.

## Old answer: score = 256

```
S(SI(K(S(SS)S(S(SI)(K(S(S(KS)K))))I)))
(S(SI(K(S(S(S(S(SIS)(KS)))S)S(S(KS)K)I)))
 (S(SS)I(K(S(SI(K(S(S(K(SSS))(SI))S(S(KS)K)I)))))
  (S(SI(K(S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I)))
   (S(SI(K(SIS(S(SS)K(SSK(S(S(KS)K))))I)))
    (S(SI(K(SS(S(S(SI))S)(K(S(S(KS)K)I)))))
     (S(SI(K(SS(S(SIS))(SSK)(S(S(KS)K))I)))
      (S(SI(K(S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I)))
       (S(SI(K(S(SS)S(SI(SSK(S(K(S(S(KS)K))))))II)))
        (S(SI(K(S(S(K(SSS))(SI))S(S(KS)K)I)))
         (S(SI(K(SIS(S(S(SS)K(S(S(KS)K))))II)))
          (S(SI(K(S(S(SSI))(SSK)(S(S(KS)K))I)))
           (K(KI)))))))))))))
(S(KS)(S(K(S(K(S(KS)K))))(S(K(SI))K)))

```

Try it online!

### How it works

I used a slightly targeted brute-force search to find expressions for the numbers. The basic idea is to loop through all expressions in order of increasing size, apply them to two arguments (with appropriate bounds on the evaluation length and depth), and see if any numbers fall out. For larger sizes, I restricted the search to expressions with `S(KS)K` (the B combinator) and one or more `I` at the end, since that seems to find a lot of numbers. Search code is below.

```
72 = S(SS)S(S(SI)(K(S(S(KS)K))))I
101 = S(S(S(S(SIS)(KS)))S)S(S(KS)K)I
108 = S(S(K(SSS))(SI))S(S(KS)K)I
108 = S(S(K(SSS))(SI))S(S(KS)K)I
111 = S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I
44 = SIS(S(SS)K(SSK(S(S(KS)K))))I
32 = SS(S(S(SI))S)(K(S(S(KS)K)I))
87 = SS(S(SIS))(SSK)(S(S(KS)K))I
111 = S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I
114 = S(SS)S(SI(SSK(S(K(S(S(KS)K))))))II
108 = S(S(K(SSS))(SI))S(S(KS)K)I
100 = SIS(S(S(SS)K(S(S(KS)K))))II
33 = S(S(SSI))(SSK)(S(S(KS)K))I

```

To build the list, I used an intermediate list encoding where cons is simpler, then converted to the target encoding:

```
# pack [x, y, ..., z] = λc. c x (c y (... (c z [])))

square f = S(SS)I(Kf)   # λx. f (f x)
pack [] = K(KI)
pack [n, ...l] = S(SI(Kn))(pack [...l])
pack [n, n, ...l] = square (S(SI(Kn))) (pack [...l])
cons = S(KS)(S(K(S(K(S(KS)K))))(S(K(SI))K))
[...l] = pack [...l] cons

```

### Search code (Rust with `rayon` and `typed_arena`)

```
use rayon::prelude::*;
use std::borrow::Cow::{self, Borrowed, Owned};
use std::cell::Cell;
use std::fmt;
use std::ptr;
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering;
use typed_arena::Arena;

const N_BOUND: usize = 115;
const FUEL: u64 = 200;

#[derive(Clone, Copy)]
enum InputNode {
    S,
    K,
    I,
    B,
    App(usize, usize),
}

enum Side {
    Root,
    Left,
    Right { left: usize },
}

struct Input {
    nodes: Vec<(Option<InputNode>, Side)>,
    variables: Vec<usize>,
    apps_left: usize,
    primitives_left: usize,
    size: usize,
}

impl Input {
    fn new(size: usize) -> Input {
        Input {
            nodes: vec![(None, Side::Root)],
            variables: vec![],
            apps_left: size - 1,
            primitives_left: size,
            size,
        }
    }
}

struct InputTerm<'a>(&'a Input, usize);

impl fmt::Display for InputTerm<'_> {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        let &InputTerm(input, ix) = self;
        match input.nodes[ix].0 {
            None => write!(fmt, "?"),
            Some(InputNode::S) => write!(fmt, "S"),
            Some(InputNode::K) => write!(fmt, "K"),
            Some(InputNode::I) => write!(fmt, "I"),
            Some(InputNode::B) => write!(fmt, "S(KS)K"),
            Some(InputNode::App(x, y)) => match input.nodes[y].0 {
                Some(InputNode::App(_, _)) | Some(InputNode::B) => {
                    write!(fmt, "{}({})", InputTerm(input, x), InputTerm(input, y))
                }
                _ => write!(fmt, "{}{}", InputTerm(input, x), InputTerm(input, y)),
            },
        }
    }
}

#[derive(Clone, Copy, Debug)]
enum Node<'a> {
    S,
    S1(&'a Cell<Node<'a>>),
    S2(&'a Cell<Node<'a>>, &'a Cell<Node<'a>>),
    K,
    K1(&'a Cell<Node<'a>>),
    I,
    B,
    B1(&'a Cell<Node<'a>>),
    B2(&'a Cell<Node<'a>>, &'a Cell<Node<'a>>),
    F,
    F1(&'a Cell<Node<'a>>),
    N,
    App(&'a Cell<Node<'a>>, &'a Cell<Node<'a>>),
    Ref(&'a Cell<Node<'a>>),
    Input(usize),
}
use Node::*;

struct Evaluator<'a> {
    arena: &'a Arena<Cell<Node<'a>>>,
    input: Input,
    fuel: u64,
}

impl<'a> Evaluator<'a> {
    fn whnf<'b>(&mut self, mut node: &'b Cell<Node<'a>>) -> Option<&'b Cell<Node<'a>>> {
        loop {
            match node.get() {
                S | S1(_) | S2(_, _) | K | K1(_) | I | B | B1(_) | B2(_, _) | F | F1(_) | N => {
                    break
                }
                App(x, y) => match self.apply(x, y)? {
                    Owned(node1) => node.set(node1.get()),
                    Borrowed(node1) => {
                        if !ptr::eq(node, node1) {
                            node.set(Ref(node1));
                        }
                        node = node1;
                    }
                },
                Ref(x) => node = x,
                Input(ix) => {
                    let Input {
                        nodes,
                        variables,
                        primitives_left,
                        apps_left,
                        ..
                    } = &mut self.input;
                    let input_node = if let Some(input_node) = nodes[ix].0 {
                        input_node
                    } else if *primitives_left > *apps_left + 1 || *apps_left == 0 {
                        variables.push(ix);
                        let input_node = InputNode::S;
                        *primitives_left -= 1;
                        nodes[ix].0 = Some(input_node);
                        input_node
                    } else {
                        variables.push(ix);
                        let len = nodes.len();
                        let input_node = InputNode::App(len, len + 1);
                        *apps_left -= 1;
                        nodes.push((None, Side::Left));
                        nodes.push((None, Side::Right { left: len }));
                        nodes[ix].0 = Some(input_node);
                        input_node
                    };
                    node.set(match input_node {
                        InputNode::S => S,
                        InputNode::K => K,
                        InputNode::I => I,
                        InputNode::B => B,
                        InputNode::App(ix0, ix1) => App(
                            self.arena.alloc(Cell::new(Input(ix0))),
                            self.arena.alloc(Cell::new(Input(ix1))),
                        ),
                    });
                }
            };
        }
        Some(node)
    }

    fn apply<'b>(
        &mut self,
        left: &'b Cell<Node<'a>>,
        right: &'a Cell<Node<'a>>,
    ) -> Option<Cow<'a, Cell<Node<'a>>>> {
        if self.fuel == 0 {
            return None;
        }
        self.fuel -= 1;
        match self.whnf(left)?.get() {
            S => Some(Owned(Cell::new(S1(right)))),
            S1(x) => Some(Owned(Cell::new(S2(x, right)))),
            S2(x, y) => {
                let xz = self.apply(x, right)?;
                self.apply(&xz, self.arena.alloc(Cell::new(App(y, right))))
            }
            K => Some(Owned(Cell::new(K1(right)))),
            K1(x) => Some(Borrowed(x)),
            I => Some(Borrowed(right)),
            B => Some(Owned(Cell::new(B1(right)))),
            B1(x) => Some(Owned(Cell::new(B2(x, right)))),
            B2(x, y) => self.apply(x, self.arena.alloc(Cell::new(App(y, right)))),
            F => Some(Owned(Cell::new(F1(right)))),
            F1(_) | N => None,
            App(_, _) | Ref(_) | Input(_) => unreachable!(),
        }
    }

    fn eval_number(&mut self, node: &Cell<Node<'a>>) -> Option<usize> {
        self.fuel = FUEL;
        let node = self.apply(node, self.arena.alloc(Cell::new(F)))?;
        self.fuel = FUEL;
        let node = self.apply(&node, self.arena.alloc(Cell::new(N)))?;
        let mut node = node.as_ref();
        for n in 0..N_BOUND {
            self.fuel = FUEL;
            match self.whnf(node)?.get() {
                N => return Some(n),
                F1(node1) => node = node1,
                _ => break,
            }
        }
        None
    }
}

fn search(found: &[AtomicUsize], mut input: Input) {
    'outer: loop {
        let mut evaluator = Evaluator {
            arena: &Arena::new(),
            input,
            fuel: FUEL,
        };
        let n = evaluator.eval_number(&Cell::new(Input(0)));
        input = evaluator.input;
        if let Some(n) = n {
            if found[n].fetch_min(input.size, Ordering::Relaxed) > input.size {
                println!("{} {} {}", n, input.size, InputTerm(&input, 0));
            }
        }
        loop {
            if let Some(&ix) = input.variables.last() {
                let len = input.nodes.len();
                let node = &mut input.nodes[ix].0;
                match node {
                    None | Some(InputNode::B) => unreachable!(),
                    Some(InputNode::S) => *node = Some(InputNode::K),
                    Some(InputNode::K) => *node = Some(InputNode::I),
                    Some(InputNode::I) => {
                        input.primitives_left += 1;
                        if input.apps_left > 0 {
                            *node = Some(InputNode::App(len, len + 1));
                            input.apps_left -= 1;
                            input.nodes.push((None, Side::Left));
                            input.nodes.push((None, Side::Right { left: len }));
                        } else {
                            *node = None;
                            input.variables.pop();
                            continue;
                        }
                    }
                    &mut Some(InputNode::App(x, y)) => {
                        input.apps_left += 1;
                        *node = None;
                        input.nodes.pop();
                        assert_eq!(y, input.nodes.len());
                        input.nodes.pop();
                        assert_eq!(x, input.nodes.len());
                        input.variables.pop();
                        continue;
                    }
                }
                match &input.nodes[ix] {
                    (Some(InputNode::I), Side::Left) => continue,
                    &(Some(InputNode::K), Side::Right { left: l }) => {
                        if let Some(InputNode::S) = &input.nodes[l].0 {
                            continue;
                        }
                    }
                    _ => (),
                }
                break;
            } else {
                break 'outer;
            }
        }
    }
}

fn main() {
    const MAX: AtomicUsize = AtomicUsize::new(usize::MAX);
    let found = [MAX; N_BOUND];
    for size in 1..10 {
        search(&found, Input::new(size));
    }
    for size in 10.. {
        (0..size - 5).into_par_iter().for_each(|b_depth| {
            for i_depths in 1..1 << (b_depth + 1) {
                let mut input = Input::new(size);
                for i in 0..b_depth + 1 {
                    input.nodes.push((None, Side::Left));
                    input.nodes.push((None, Side::Right { left: 2 * i + 1 }));
                    input.nodes[2 * i].0 = Some(InputNode::App(2 * i + 1, 2 * i + 2));
                    input.apps_left -= 1;
                }
                input.nodes[2 * b_depth + 2].0 = Some(InputNode::B);
                input.apps_left -= 3;
                input.primitives_left -= 4;
                for i_depth in 0..b_depth + 1 {
                    if i_depths & 1 << i_depth != 0 {
                        input.nodes[2 * i_depth + 1].0 = input.nodes[2 * i_depth + 2].0;
                        input.nodes[2 * i_depth + 2].0 = Some(InputNode::I);
                        input.primitives_left -= 1;
                    }
                }
                search(&found, input);
            }
        });
    }
}

```

Output for all numbers 0, …, 114:

```
0 2 KI
1 1 I
2 6 S(S(KS)K)I
3 9 S(K(SS(S(SS)I)))K
4 9 SII(S(S(KS)K)I)
5 11 S(S(SS)S)S(S(KS)K)I
6 11 SII(SSS(S(KS)K))I
7 13 S(SI)S(SSK(S(S(KS)K)))I
8 12 S(S(KS)S)I(S(S(KS)K))I
9 12 SII(SS(K(S(S(KS)K))))I
10 13 SI(SS)(SSK(S(S(KS)K)))I
11 13 S(SS)S(SSK(S(S(KS)K)))I
12 11 S(S(SI))I(S(S(KS)K))I
13 12 S(S(SS)I)I(S(S(KS)K))I
14 13 SS(SS)(SSK)(S(S(KS)K))I
15 14 S(SI)(S(SSK(S(S(KS)K))))II
16 10 S(S(SI))(S(S(KS)K))I
17 14 S(SS(K(S(S(SI)))))S(S(KS)K)I
18 13 SS(SS)(SS)(K(S(S(KS)K)))I
19 15 SS(SS(SS)(SS))(K(S(S(KS)K)))I
20 12 S(S(SIS))I(S(S(KS)K))I
21 14 S(SSK)(S(SIS))(S(S(KS)K))I
22 13 S(SSI(SSS))S(S(KS)K)I
23 13 S(S(SI))(SSK)(S(S(KS)K))I
24 14 S(S(S(S(SS))K))I(S(S(KS)K))I
25 13 SS(S(SSK)S)(S(S(KS)K))I
26 14 S(S(SS)S)(SS(KI))(S(KS)K)I
27 12 SSS(SS)(K(S(S(KS)K)))I
28 14 SS(SSS(SS))(K(S(S(KS)K)))I
29 14 S(S(S(S(SI))I))S(S(KS)K)II
30 15 S(S(SS(S(SS)K)))S(S(KS)K)II
31 14 SIS(S(SII)(K(S(S(KS)K))))I
32 14 SS(S(S(SI))S)(K(S(S(KS)K)I))
33 14 S(S(SSI))(SSK)(S(S(KS)K))I
34 15 SI(S(SS))(S(SSK))(S(S(KS)K))I
35 15 S(S(SI))(S(SSS)K)(S(S(KS)K))I
36 12 SI(SI)(SSS(S(KS)K))I
37 14 SII(S(S(SS)S)S(S(KS)K))I
38 16 S(S(S(S(S(K(SSK))))I))S(S(KS)K)I
39 12 SSS(SSS)S(S(KS)K)I
40 13 S(S(S(SSI))S)S(S(KS)K)I
41 15 S(SS(S(S(SSI))S))S(S(KS)K)I
42 13 S(S(SS(KI)))I(S(S(KS)K))I
43 15 SI(SIS)(S(SI)(K(S(S(KS)K))))I
44 16 SIS(S(SS)K(SSK(S(S(KS)K))))I
45 15 S(S(S(SI)))(SSS)(K(S(S(KS)K)))I
46 16 S(SI)(S(S(SSS)K(S(S(KS)K))))II
47 16 S(S(SIK))S(SSK(S(S(KS)K)))II
48 16 S(SS(S(S(S(SS)I))))K(S(S(KS)K))I
49 15 SS(S(S(SS))(SSK))(S(S(KS)K))I
50 14 SSS(S(S(SI))S(S(KS)K))II
51 15 S(SS(SS))I(SSK(S(S(KS)K)))I
52 15 SSS(SSI(S(K(S(S(KS)K)))))II
53 17 SS(S(SS(SS))I)(SSK(S(S(KS)K)))I
54 13 S(SI)S(SS)(K(S(S(KS)K)))I
55 15 SS(S(SI)S(SS))(K(S(S(KS)K)))I
56 13 S(S(SS)(SSS))S(S(KS)K)I
57 15 S(SS(S(SS)(SSS)))S(S(KS)K)I
58 17 SSS(S(S(S(SIK))))(K(K(S(S(KS)K))))I
59 18 S(S(S(S(SIS(S(SS))K)))S)S(S(KS)K)I
60 17 S(SS(SS(KI)))(SSK)(S(S(KS)K))II
61 14 S(S(S(S(SS)I))S)S(S(KS)K)I
62 16 S(SS(S(S(S(SS)I))S))S(S(KS)K)I
63 15 S(SS)S(SI(SSK(S(S(KS)K))))I
64 13 S(SSS)S(K(S(S(KS)K)I))I
65 15 S(SS)K(S(SS)S(K(S(S(KS)K))))I
66 16 S(SS(S(S(S(SIS)))))K(S(S(KS)K))I
67 16 S(S(S(S(S(SS))I)))S(K(S(S(KS)K)))I
68 15 SIS(S(SSS(K(S(S(KS)K)))))II
69 18 SS(SI(K(SI)))(SS(SSK)(S(S(KS)K)))I
70 17 S(S(S(S(S(SI)(S(KS)))))S)S(S(KS)K)I
71 18 SIS(S(S(SSK))(S(SI)S)(S(KS)K))II
72 14 S(SS)S(S(SI)(K(S(S(KS)K))))I
73 16 SS(S(SI)(SS)(SS))(K(S(S(KS)K)))I
74 15 S(S(SI)(S(SSS)S))S(S(KS)K)I
75 17 S(SS(S(SI)(S(SSS)S)))S(S(KS)K)I
76 16 SS(SSS)(S(SIK))(K(S(S(KS)K)))I
77 17 S(SS(SI(SI)))(SSK)(S(S(KS)K))II
78 18 S(SI)(S(S(SI)I)S)(SI(K(S(S(KS)K))))I
79 17 S(S(S(SI(KK))))S(SSK(S(S(KS)K)))I
80 14 S(SIS)(S(SI)I)(S(S(KS)K))I
81 12 SIS(SS(K(S(S(KS)K))))I
82 16 SS(S(K(SIS))(SS))(K(S(S(KS)K)))I
83 16 S(S(SSI)(S(KS)S))K(S(S(KS)K))I
84 15 SIS(SSK(SI(K(S(S(KS)K)))))I
85 14 S(S(S(SS)I)I)I(S(S(KS)K))I
86 15 S(SS)S(SS(K(K(S(S(KS)K)))))II
87 15 SS(S(SIS))(SSK)(S(S(KS)K))I
88 15 S(SI)(S(S(SSK))I)(S(S(KS)K))I
89 17 SI(S(SSI)K)(S(SI)(K(S(S(KS)K))))I
90 16 SI(S(SI))(S(SSS)K(S(S(KS)K)))I
91 15 S(SIS)(S(SSK)I)(S(S(KS)K))I
92 15 SI(S(SIS))(SSK(S(S(KS)K)))I
93 18 S(SI)S(SIS(S(K(SSK(S(S(KS)K))))))I
94 17 SS(SI(S(SIS)))(SSK(S(S(KS)K)))I
95 18 S(S(S(S(S(SI)))S)S)(SIS)(S(KS)K)II
96 16 SIS(S(S(SSI)(K(S(S(KS)K)))))II
97 16 S(S(S(SS)I))(SSS)(K(S(S(KS)K)))I
98 15 S(SS)(SSS)(SI(K(S(S(KS)K))))I
99 16 S(SI)S(SIK(SSK(S(S(KS)K))))I
100 15 SIS(S(S(SS)K(S(S(KS)K))))II
101 16 S(S(S(S(SIS)(KS)))S)S(S(KS)K)I
102 17 S(SI(S(SS)))S(SI(K(S(S(KS)K))))II
103 15 S(S(SI)S(SS(KS)))S(S(KS)K)I
104 15 SIS(SSI(S(K(S(S(KS)K)))))II
105 17 S(S(S(S(S(SSS)))K))S(K(S(S(KS)K)))I
106 17 S(S(S(S(S(SS(KI)))I))S)S(S(KS)K)I
107 19 S(S(SSS(SIS))(S(SI)))S(K(S(S(KS)K)))I
108 14 S(S(K(SSS))(SI))S(S(KS)K)I
109 16 SSS(S(S(SSK))(K(S(S(KS)K))))II
110 16 SSK(S(SSS(K(S(S(KS)K)))))III
111 17 S(S(S(S(S(SS)I))S)(KI))S(S(KS)K)I
112 16 S(SSS)(S(S(S(SS))S)S)(S(KS)K)I
113 18 S(SS(S(S(S(S(K(S(SI))))))S))S(S(KS)K)I
114 18 S(SS)S(SI(SSK(S(K(S(S(KS)K))))))II

```

# Answer
> 4 votes
# 5844 SKIs

## The Baseline

In order to respect your scrolling fingers, I won't copy & paste it here. The 5,844 score is the SKI count; it doesn't even include all the parentheses. But please do try it online!

### Generating Lambda Calculus

```
def church_numeral(n):
    return r'(\f.\x. '+'f('*n +'x'+ ')'*n+')'

def church_list(lst):
    acc = r'\c.\n.'
    for l in lst:
        acc+='(c '+l+' '
    acc+='n'+')'*len(lst)
    return acc

def church_numeral_list(lst):
    nums = [church_numeral(l) for l in lst]
    return church_list(nums)

print(church_numeral_list([72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33]))

```
* The function `church_numeral` generates a number of the form: `\f. \x. f (f (f x))`.
* The function `church_list` generates a list of the form: `\c. \n. c 0 (c 1 (c 2 n)` which is precisely the format a right-fold list takes as per Wikipedia.
* The function `church_numeral_list` just converts the numbers to Church numerals and sends them over to be list-churchified.

If anyone would like to strategically compile the lambda calculus to SKI, here's a link to the output on TIO. The lambda calculus it generates is totally naive; it doesn't attempt to optimize anything, as you can tell.

### Compiling to SKI

This part was super hacky. I used the intermediate form generated by this site– the first *lambda2ski* compiler I could find. That site is actually a compiler from the lambda calculus into WebAssembly, which seems totally out of left field!

That's why the output I used was just the intermediate form which the site luckily spits outs as well. There may be more efficient compilers, I don't know. Even still, there was one more issue, the output — *I mean intermediate form* — also used the `B` & `C` combinators. Those took me a while to find, but eventually I found their translation into SKI here on good ol' Wikipedia.

So just two more lines of code left:

```
B = "S(KS)K"
C = "S(S(K(S(KS)K))S)(KK)"
ski = ski.replace('B', B)
ski = ski.replace('C', C)

```

### A bad bug

Just kidding! There's a bug in the very last step. And there are no SKI interpreters to help you out. Just Bubbler's TIO link which spits out nasty and nonsensical python errors at you. Or maybe it seems to do run fine, only to output `<function <lambda> at 0xmadbadhex>`.

Can you spot it?

The `B` & `C` combinators need to be wrapped in parentheses. So it should really be:

```
B = "(S(KS)K)"
C = "(S(S(K(S(KS)K))S)(KK))"
ski = ski.replace('B', B)
ski = ski.replace('C', C)

```

And now you've built your very own hello-world app in SKI and successfully deployed it to TIO!

---
Tags: hello-world, atomic-code-golf, combinatory-logic
---


title: JavaScript load and SHA-256

text:
# Question
Title: JavaScript load and SHA-256
This is a code golf puzzle with a real-world application. Some current browsers, if you enter a URL that looks like

```
data:text/html,<script>alert("hi")</script>

```

will execute the given JavaScript code. Now suppose you had a URL which looked like (pseudocode):

```
data:text/html,<script>
    myPublicKey="12345678";
    cryptoLib=download("http://example.com/somecryptolib.js");
    if(sha256sum(cryptoLib) == "12345678")
        eval(cryptoLib)
</script>

```

If you printed this on business cards as a QR code, then anyone who went to that URL with an appropriate browser would get a public-key crypto client, with your public key pre-loaded, without having to install anything. Because of the hash verification, you could be confident they got the real crypto software, even if their ISP meddles with traffic.

Unfortunately, the real version of this pseudocode is quite long for a QR code. My challenge is: how short can you make it? An implementation would:

* Be a data:... URL which executes correctly from the address bar of Chrome and Firefox. (To make a valid data: URL, you'll have to encode % as %25, and strip newlines)
* Have a URL and a SHA-256 hash embedded, preferably as plain-text string literals near the beginning
* Download a file from a URL using XMLHttpRequest (or a similar API). (Note that the server will need to include an Access-Control-Allow-Origin:\* header for this to work.)
* If that URL loaded successfully and the result is a file with the expected hash, eval() it. Otherwise do nothing or show an error message.
* All builtin JavaScript functions that're present in both Chrome and Firefox are fair game, but loading libraries is impossible.
* Use as few bytes as possible

I made a naive version using CryptoJS (minified version):

```
data:text/html,<script>
    u = 'http://localhost:8000'
    h = '5e3f73c606a82d68ef40f9f9405200ce24adfd9a4189c2bc39015345f0ee46d4'
    // Insert CryptoJS here
    r = new XMLHttpRequest;
    r.open('GET', u, false);
    r.send();
    if(CryptoJS.SHA256(r.response) == h)
        eval(r.response);
</script>

```

Which comes out of the minifier as:

```
data:text/html,<script>u="http://localhost:8000";h="5e3f73c606a82d68ef40f9f9405200ce24adfd9a4189c2bc39015345f0ee46d4";var CryptoJS=CryptoJS||function(k,w){var f={},x=f.lib={},g=function(){},l=x.Base={extend:function(a){g.prototype=this;var c=new g;a&&c.mixIn(a);c.hasOwnProperty("init")||(c.init=function(){c.$super.init.apply(this,arguments)});c.init.prototype=c;c.$super=this;return c},create:function(){var a=this.extend();a.init.apply(a,arguments);return a},init:function(){},mixIn:function(a){for(var c in a)a.hasOwnProperty(c)&&(this[c]=a[c]);a.hasOwnProperty("toString")&&(this.toString=a.toString)},clone:function(){return this.init.prototype.extend(this)}},t=x.WordArray=l.extend({init:function(a,c){a=this.words=a||[];this.sigBytes=c!=w?c:4*a.length},toString:function(a){return(a||y).stringify(this)},concat:function(a){var c=this.words,d=a.words,b=this.sigBytes;a=a.sigBytes;this.clamp();if(b%254)for(var e=0;e<a;e++)c[b+e>>>2]|=(d[e>>>2]>>>24-8*(e%254)&255)<<24-8*((b+e)%254);else if(65535<d.length)for(e=0;e<a;e+=4)c[b+e>>>2]=d[e>>>2];else c.push.apply(c,d);this.sigBytes+=a;return this},clamp:function(){var a=this.words,c=this.sigBytes;a[c>>>2]&=4294967295<<32-8*(c%254);a.length=k.ceil(c/4)},clone:function(){var a=l.clone.call(this);a.words=this.words.slice(0);return a},random:function(a){for(var c=[],d=0;d<a;d+=4)c.push((1<<30)*4*k.random()|0);return new t.init(c,a)}}),z=f.enc={},y=z.Hex={stringify:function(a){var c=a.words;a=a.sigBytes;for(var d=[],b=0;b<a;b++){var e=c[b>>>2]>>>24-8*(b%254)&255;d.push((e>>>4).toString(16));d.push((e&15).toString(16))}return d.join("")},parse:function(a){for(var c=a.length,d=[],b=0;b<c;b+=2)d[b>>>3]|=parseInt(a.substr(b,2),16)<<24-4*(b%258);return new t.init(d,c/2)}},m=z.Latin1={stringify:function(a){var c=a.words;a=a.sigBytes;for(var d=[],b=0;b<a;b++)d.push(String.fromCharCode(c[b>>>2]>>>24-8*(b%254)&255));return d.join("")},parse:function(a){for(var c=a.length,d=[],b=0;b<c;b++)d[b>>>2]|=(a.charCodeAt(b)&255)<<24-8*(b%254);return new t.init(d,c)}},n=z.Utf8={stringify:function(a){try{return decodeURIComponent(escape(m.stringify(a)))}catch(c){throw Error("Malformed UTF-8 data");}},parse:function(a){return m.parse(unescape(encodeURIComponent(a)))}},B=x.BufferedBlockAlgorithm=l.extend({reset:function(){this._data=new t.init;this._nDataBytes=0},_append:function(a){"string"==typeof a&&(a=n.parse(a));this._data.concat(a);this._nDataBytes+=a.sigBytes},_process:function(a){var c=this._data,d=c.words,b=c.sigBytes,e=this.blockSize,f=b/(4*e),f=a?k.ceil(f):k.max((f|0)-this._minBufferSize,0);a=f*e;b=k.min(4*a,b);if(a){for(var p=0;p<a;p+=e)this._doProcessBlock(d,p);p=d.splice(0,a);c.sigBytes-=b}return new t.init(p,b)},clone:function(){var a=l.clone.call(this);a._data=this._data.clone();return a},_minBufferSize:0});x.Hasher=B.extend({cfg:l.extend(),init:function(a){this.cfg=this.cfg.extend(a);this.reset()},reset:function(){B.reset.call(this);this._doReset()},update:function(a){this._append(a);this._process();return this},finalize:function(a){a&&this._append(a);return this._doFinalize()},blockSize:16,_createHelper:function(a){return function(c,d){return(new a.init(d)).finalize(c)}},_createHmacHelper:function(a){return function(c,d){return(new A.HMAC.init(a,d)).finalize(c)}}});var A=f.algo={};return f}(Math);(function(k){for(var w=CryptoJS,f=w.lib,x=f.WordArray,g=f.Hasher,f=w.algo,l=[],t=[],z=function(a){return (1<<30)*4*(a-(a|0))|0},y=2,m=0;64>m;){var n;a:{n=y;for(var B=k.sqrt(n),A=2;A<=B;A++)if(!(n%25A)){n=!1;break a}n=!0}n&&(8>m&&(l[m]=z(k.pow(y,0.5))),t[m]=z(k.pow(y,1/3)),m++);y++}var a=[],f=f.SHA256=g.extend({_doReset:function(){this._hash=new x.init(l.slice(0))},_doProcessBlock:function(c,d){for(var b=this._hash.words,e=b[0],f=b[1],p=b[2],k=b[3],s=b[4],l=b[5],m=b[6],n=b[7],q=0;64>q;q++){if(16>q)a[q]=c[d+q]|0;else{var v=a[q-15],g=a[q-2];a[q]=((v<<25|v>>>7)^(v<<14|v>>>18)^v>>>3)+a[q-7]+((g<<15|g>>>17)^(g<<13|g>>>19)^g>>>10)+a[q-16]}v=n+((s<<26|s>>>6)^(s<<21|s>>>11)^(s<<7|s>>>25))+(s&l^~s&m)+t[q]+a[q];g=((e<<30|e>>>2)^(e<<19|e>>>13)^(e<<10|e>>>22))+(e&f^e&p^f&p);n=m;m=l;l=s;s=k+v|0;k=p;p=f;f=e;e=v+g|0}b[0]=b[0]+e|0;b[1]=b[1]+f|0;b[2]=b[2]+p|0;b[3]=b[3]+k|0;b[4]=b[4]+s|0;b[5]=b[5]+l|0;b[6]=b[6]+m|0;b[7]=b[7]+n|0},_doFinalize:function(){var a=this._data,d=a.words,b=8*this._nDataBytes,e=8*a.sigBytes;d[e>>>5]|=128<<24-e%2532;d[(e+64>>>9<<4)+14]=k.floor(b/(1<<30)*4);d[(e+64>>>9<<4)+15]=b;a.sigBytes=4*d.length;this._process();return this._hash},clone:function(){var a=g.clone.call(this);a._hash=this._hash.clone();return a}});w.SHA256=g._createHelper(f);w.HmacSHA256=g._createHmacHelper(f)})(Math);r=new XMLHttpRequest;r.open("GET",u,!1);r.send();CryptoJS.SHA256(r.response)==h&&eval(r.response)</script>

```

Tested with this minimal Python server:

```
import BaseHTTPServer

class RequestHandler(BaseHTTPServer.BaseHTTPRequestHandler):
    def do_HEAD(s):
        s.send_response(200)
        s._sendHeaders()
        s.end_headers()
    def do_GET(s):
        s.send_response(200)
        s._sendHeaders()
        s.end_headers()
        s.wfile.write('alert("Success!")')
    def _sendHeaders(s):
        s.send_header("Content-type", "script/javascript");
        s.send_header("Access-Control-Allow-Origin", "*");

def run(server_class=BaseHTTPServer.HTTPServer,
    handler_class=RequestHandler):
    server_address = ('', 8000)
    httpd = server_class(server_address, handler_class)
    httpd.serve_forever()

run()

```

The JavaScript portion is 4700 bytes, but it can be much smaller. How small can it get?

# Answer
> 6 votes
# 844 Characters

```
K=new XMLHttpRequest;K.open("get","http://localhost:8000",O=j=n=q=0);K.send();m=K.response;l=m.length;k=l+1|63;W=[o=Math.pow];for(H=[R=o(i=2,32)];i<313+l;i++)for(W[i]||(K[q]=o(i,1/3)*R|0,H[q++]=o(i,.5)*R|0,I=2);W[i*I++]=199>I;)o[n>>2]|=(n^l?m.charCodeAt(n):128)<<24-n++%4*8;for(o[k>>2]=8*l;j<=k;H[I-7]+=a=t+T|0)i=j++&63||(a=H[0],b=H[1],c=H[2],d=H[3],e=H[4],f=H[5],g=H[6],h=H[7],0),y=W[i-15],x=W[i-2],t=h+(e<<26^e>>>6^e<<21^e>>>11^e<<7^e>>>25)+(e&f^~e&g)+K[i]+(W[i]=16>i?o[O++]:(y<<25^y>>>7^y<<14^y>>>18^y>>>3)+W[i-7]+(x<<15^x>>>17^x<<13^x>>>19^x>>>10)+W[i-16]),T=(a<<30^a>>>2^a<<19^a>>>13^a<<10^a>>>22)+(a&b^a&c^b&c),H[I=i-63|7]+=h=g,H[I-1]+=g=f,H[I-2]+=f=e,H[I-3]+=e=d+t|0,H[I-4]+=d=c,H[I-5]+=c=b,H[I-6]+=b=a;1581216710^H[0]|111684968^H[1]|4014012921^H[2]|1079115982^H[3]|615382426^H[4]|1099547324^H[5]|956388165^H[6]|4042147540^H[7]||eval(m)

```

The URL and Hash values are hard coded. The Hash is encoded as decimal double words, the values in my code correspond to the script in the example Python server.

I also didn't bother doing the URL encoding, but it works when you type `javascript:` manually in the URL bar and then paste the code (and also in the console).

The implementation is not compliant, but it should work for files smaller than 512 MB.

# Answer
> 1 votes
# HTML Data URL, 131 Characters

It's been a while and there's a native way to do this now: Subresource Integrity. Also, data URLs are not allowed to be linked to by major browsers so this whole idea no longer works :( Also, I used a hosted copy of the script that should be CORS-accessible, `http:localhost:8000` was what OP specified and would save 3 characters.

```
data:text/html,<script src=https:fk.ci/9Rg2HKk.js integrity=sha256Xj9zxgaoLWjvQPn5QFIAziSt/ZpBicK8OQFTRfDuRtQ crossorigin></script>

```

---
Tags: code-golf, javascript
---


title: It's a yearly task, alright

text:
# Question
Title: It's a yearly task, alright
Given a number 1≤n≤365, output the nth day of the year in "Day-numberth Month" format. For example, given 1, you should output "1st January", without "of".

The Gregorian calendar will be used and the program should not account for leap years, so your program should never output "29th February" in any circumstance. Any method can be used, as long as it follows the "Day-numberth Month" format mentioned before. Your program should also output ordinals correctly, meaning it should always output 1st, 2nd, 3rd, should 1, 2 or 3 respectively be the day numbers for any input. Leading spaces or other indentation are allowed.

This is code golf, so the shortest solution by characters wins.

Test cases:

```
1 gives 1st January
2 gives 2nd January
3 gives 3rd January
365 gives 31st December
60 gives 1st March
11 gives 11th January

```

# Answer
> 11 votes
# PHP, ~~38~~ ~~40~~ ~~30~~ 28 bytes

```
<?=date("jS F",86399*$argn);

```

Try it online!

Run with `php -nF` input is from `STDIN`. Example (above script named `y.php`):

```
$ echo 1|php -nF y.php
1st January
$ echo 2| php -nF y.php
2nd January
$ echo 3| php -nF y.php
3rd January
$ echo 11|php -nF y.php
11th January
$ echo 21|php -nF y.php
21st January
$ echo 60|php -nF y.php
1st March
$ echo 365|php -nF y.php
31st December

```

**Explanation**

Construct an epoch timestamp for the desired day in 1970 (conveniently not a leap year) by multiplying the `day number * number of seconds per day` (86400). However, this would yield one day higher so instead multiply by `number of seconds in a day - 1` (86399) which for the range of input numbers (1≤n≤365) will result with the timestamp of the end of each correct day. Then just use PHP's built-in date formatting for output.

# Answer
> 6 votes
# C# (Visual C# Interactive Compiler), ~~115~~ ~~113~~ ~~109~~ 98 bytes

```
g=>$"{f=(g=p.AddDays(g-1)).Day}{"tsnr"[f=f%30%20<4?f%10:0]}{"htdd"[f]} {g:MMMM}";DateTime p;int f;

```

Thanks to @someone for saving 9 bytes

Try it online!

# Answer
> 6 votes
# Jelly,  ~~79 78~~  77 bytes

-1 fixing a bug :) (shouldn't pre-transpose to find index, should post-reverse, but then we can tail rather than head)
-1 using reflection (`⁽©ṅB+30_2¦2` -\> `⁽0ṗb4+28m0`)

```
⁽0ṗb4+28m0SRṁRƲœiµṪȮ%30%20«4ị“nḄƲf⁷»s3¤Ṗ,ị“£ṢtẒ⁽ẹ½MḊxɲȧėAṅ ɓaṾ¥D¹ṀẏD8÷ṬØ»Ḳ¤$K

```

A full program which prints the result

**Try it online!**

### How?

*will update this later...*

```
⁽©ṅB+30_2¦2SRṁRƲZœiµḢȮ%30%20«4ị“nḄƲf⁷»s3¤Ṗ,ị“...»Ḳ¤$K - Main Link: integer, n
⁽©ṅB+30_2¦2SRṁRƲZœi - f(n) to get list of integers, [day, month]
⁽©ṅ                 - compressed literal 2741
   B                - to a list of binary digits -> [ 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1]
    +30             - add thirty                    [31,30,31,30,31,30,31,31,30,31,30,31]
         ¦          - sparse application...
        2           - ...to indices: [2]
       _  2         - ...action: subtract two       [31,28,31,30,31,30,31,31,30,31,30,31]
               Ʋ    - last four links as a monad - i.e. f(x):
           S        -   sum x                       365
            R       -   range                       [1..365]
              R     -   range x (vectorises)        [[1..31],[1..28],...]
             ṁ      -   mould like                  [[1..31],[32..59],...]
                Z   - transpose                     [[1,32,...],[2,33,...],...]
                 œi - 1st multi-dimensional index of n  -> [day, month]

µḢȮ%30%20«4ị“nḄƲf⁷»s3¤Ṗ,ị“...»Ḳ¤$K - given [day, month] format and print
µ                                  - start a new monadic chain - i.e. f(x=[day, month])
 Ḣ                                 - head -- get the day leaving x as [month])
  Ȯ                                - print it (with no newline) and yield it
   %30                             - modulo by thirty
      %20                          - modulo by twenty
         «4                        - minimum of that and four
                     ¤             - nilad followed by link(s) as a nilad:
            “nḄƲf⁷»                -   dictionary words "standard"+" the" = "standard the"
                   s3              -   split into threes = ["sta","nda","rd ","the"]
           ị                       - index into
                      Ṗ            - remove rightmost character
                               ¤   - nilad followed by link(s) as a nilad:
                         “...»     -   dictionary words "January"+" February"+...
                              Ḳ    -   split at spaces = ["January","February",...]
                        ị          - index into (vectorises across [month])
                       ,           - pair                  e.g. ["th", ["February"]]
                                K  - join with spaces           ["th ", "February"]
                                   - print (implicitly smashes)   th February

```

# Answer
> 5 votes
# Python 3.8 (pre-release), 112 bytes

```
lambda x:str(d:=(t:=gmtime(x*86399)).tm_mday)+'tsnrhtdd'[d%5*(d%30%20<4)::4]+strftime(' %B',t)
from time import*

```

Try it online!

Weirdly enough, I don't have to parenthesize `d:=(t:=gmtime(~-x*86400)`, probably because the interpreter only checks if there are `()` characters around the assignment expression and not that the expression itself is parenthesized.

-2 thanks to gwaugh.
-5 thanks to xnor.

# Answer
> 5 votes
# Perl 6, ~~166~~ 161 bytes

```
{~(.day~(<th st nd rd>[.day%30%20]||'th'),<January February March April May June July August September October November December>[.month-1])}o*+Date.new(1,1,1)-1

```

Try it online!

Hardcodes all the month names, which takes up most of the space. Man, Perl 6 really needs a proper date formatter.

# Answer
> 4 votes
# JavaScript (ES6),  ~~117~~  113 bytes

*Saved 4 bytes thanks to @tsh*

```
d=>(n=(d=new Date(1,0,d)).getDate())+([,'st','nd','rd'][n%30%20]||'th')+' '+d.toLocaleString('en',{month:'long'})

```

Try it online!

### Commented

```
d =>                     // d = input day
  ( n =                  //
    ( d =                // convert d to
      new Date(1, 0, d)  //   a Date object for the non leap year 1901
    ).getDate()          // save the corresponding day of month into n
  ) + (                  //
    [, 'st', 'nd', 'rd'] // ordinal suffixes
    [n % 30 % 20]        // map { 1, 2, 3, 21, 22, 23, 31 } to { 'st', 'nd', 'rd' }
    || 'th'              // or use 'th' for everything else
  ) + ' ' +              // append a space
  d.toLocaleString(      // convert d to ...
    'en',                // ... the English ...
    { month: 'long' }    // ... month name
  )                      //

```

---

# Without date built-ins, 188 bytes

```
f=(d,m=0)=>d>(k=31-(1115212>>m*2&3))?f(d-k,m+1):d+([,'st','nd','rd'][d%30%20]||'th')+' '+`JanuaryFebruaryMarchAprilMayJuneJulyAugustSeptemberOctoberNovemberDecember`.match(/.[a-z]*/g)[m]

```

Try it online!

# Answer
> 4 votes
# Hack, ~~115~~ ~~59~~ 39 bytes

```
$x==>date("jS F",mktime(0,0,0,1,$x));

```

Since @gwaugh got to the same solution as mine while I was golfing, I'm posting this in Hack instead :).

# Answer
> 4 votes
# Smalltalk, 126 bytes

```
d:=Date year:1day:n.k:=m:=d dayOfMonth.10<k&(k<14)and:[k:=0].o:={#st.#nd.#rd}at:k\\10ifAbsent:#th.m asString,o,' ',d monthName

```

# Answer
> 3 votes
# C# (Visual C# Interactive Compiler), ~~141~~ ~~139~~ ~~133~~ ~~124~~  122 bytes

```
a=>{var d=s.AddDays(a-1);int x=d.Day,m=x%30%20;return x+"thstndrd".Substring(m<4?m*2:0,2)+d.ToString(" MMMM");};DateTime s

```

Thanks to Arnauld for faster method of removing 11,12,13th saving 4 bytes

Try it online!

# Answer
> 3 votes
# , 158 134 bytes

-24 bytes @Nick Kennedy for golfing the 'st', 'nd', 'rd', & 'th'. Thanks!

```
f=format;paste0(a<-as.double(f(d<-as.Date(scan(,''),'%j'),'%e')),`if`((a-1)%%10>2|a%/%10==1,'th',c("st","nd","rd")[a%%10]),f(d,' %B'))

```

Try it online!

# Answer
> 3 votes
# 05AB1E, ~~81~~ ~~79~~ ~~78~~ ~~76~~ ~~75~~ ~~74~~ ~~73~~ ~~71~~ ~~70~~ 69 bytes

```
•ΘÏF•ºS₂+.¥-D0›©ÏθDT‰ć≠*4šß„—ÃŠØ3ôsè¨ð”……‚æ‡‰…ä†ï€¿…Ë…ê†Ä…æ…Ì…Í”#®OèJ

```

-9 bytes thanks to *@Grimy*.
-1 byte thanks to @JonathanAllan's `standard the` trick for `th,st,nd,rd`, which he used in his Jelly answer.

Try it online or verify all possible test cases.

**Explanation:**

```
•ΘÏF•        # Push compressed integer 5254545
     º       # Mirror it vertically: 52545455454525
      S      # Converted to a list of digits: [5,2,5,4,5,4,5,5,4,5,4,5,2,5]
       ₂+    # And 26 to each: [31,28,31,30,31,30,31,31,30,31,30,31,28,31]
             # (the additional trailing 28,31 won't cause any issues)
.¥           # Undelta this list (with automatic leading 0):
             #  [0,31,59,90,120,151,181,212,243,273,304,334,365,393,424]
  -          # Subtract each from the (implicit) input-integer
   D0›       # Duplicate the list, and check for each if it's positive (> 0)
      ©      # Store the resulting list in the register (without popping)
       Ï     # Only leave the values at those truthy indices
        θ    # And get the last value from the list, which is our day
D            # Duplicate this day
 T‰          # Take the divmod-10 of this day: [day//10, day%10]
   ć         # Extract the head; pop and push the remainder-list and head: [day%10], day//10
    ≠        # Check whether the day//10 is NOT 1 (0 if day//10 == 1; 1 otherwise)
     *       # Multiply that by the [day%10] value
      4š     # Prepend a 4 to this list
        ß    # Pop and push the minimum of the two (so the result is one of [0,1,2,3,4],
             # where the values are mapped like this: 1..3→1..3; 4..9→4; 10..19→0; 20..23→0..3; 24..29→4; 30,31→0,1)
 …thŠØ       # Push dictionary string "th standards"
      3ô     # Split it into parts of size 3: ["th ","sta","nda","rds"]
        sè   # Swap and index the integer into this list (4 wraps around to index 0)
          ¨  # And remove the trailing character from this string
ð            # Push a space " "
”……‚æ‡‰…ä†ï€¿…Ë…ê†Ä…æ…Ì…Í”
             # Push dictionary string "December January February March April May June July August September October November"
 #           # Split on spaces
  ®          # Push the list of truthy/falsey values from the register again
   O         # Get the amount of truthy values by taking the sum
    è        # Use that to index into the string-list of months (12 wraps around to index 0)
J            # Join everything on the stack together to a single string
             # (and output the result implicitly)

```

See this 05AB1E tip of mine to understand why:

* (section *How to use the dictionary?*) `”……‚æ‡‰…ä†ï€¿…Ë…ê†Ä…æ…Ì…Í”` is `"December January February March April May June July August September October November"`
* (section *How to use the dictionary?*) `…thŠØ` is `"th standards"`
* (section *How to compress large integers?*) `•ΘÏF•` is `5254545`

# Answer
> 3 votes
# MySQL, ~~47~~ ~~45~~ 42 bytes

```
SELECT DATE_FORMAT(MAKEDATE(1,n),"%D %M")

```

1901 can be replaced with any year that was/is not a leap year.

Edit: saved two bytes by removing spaces and another three bytes by changing the year to 1, thanks to @Embodyment of Ignorance.

# Answer
> 2 votes
# Jelly, ~~115~~ ~~114~~ ~~101~~ 97 bytes

```
%30%20¹0<?4Ḥ+Ø½ị“thstndrd”ṭ
“5<Ḟ’b4+28ÄŻ_@µ>0T,>0$ƇZṪµ1ịị“£ṢtẒ⁽ẹ½MḊxɲȧėAṅ ɓaṾ¥D¹ṀẏD8÷ṬØ»Ḳ¤,2ịÇƊṚK

```

Try it online!

Long by Jelly standards, but done from first principles.

Thanks to @JonathanAllan for saving 13 bytes through better understanding of string compression.

# Answer
> 2 votes
# Shell + coreutils, ~~112~~ 90 bytes

```
date -d0-12-31\ $1day +%-dth\ %B|sed 's/1th/1st/;s/2th/2nd/;s/3th/3rd/;s/\(1.\).. /\1th /'

```

Try it online! Link includes test cases. Edit: Saved 22 bytes thanks to @NahuelFouilleul. Explanation:

```
date -d0-12-31\ $1day

```

Calculate the number of day(s) after the first day preceding a non-leap year. (Sadly you can't do relative date calculations from `@-1`.)

```
+%-dth\ %B|sed

```

Output the day of month (without leading zero), `th`, and the full month name.

```
's/1th/1st/;s/2th/2nd/;s/3th/3rd/;

```

Fix up `1st`, `2nd`, `3rd`, `21st`, `22nd`, `23rd` and `31st`.

```
s/\(1.\).. /\1th /'

```

Restore `11th` to `13th`.

# Answer
> 2 votes
# bash, ~~82~~ 80 bytes

-2 bytes thanks to @ASCII-only

```
a=(th st nd rd);set `printf "%(%e %B)T" $[$1*86399]`;echo $1${a[$1%30%20]-th} $2

```

TIO

# bash +GNU date, 77 bytes

```
a=(th st nd rd);set `date -d@$[$1*86399] +%e\ %B`;echo $1${a[$1%30%20]-th} $2

```

# Answer
> 2 votes
# Google Sheets, ~~118~~ ~~103~~ 86 bytes

```
=day(A1+1)&mid("stndrdth",min(7,1+2*mod(mod(day(A1+1)-1,30),20)),2)&text(A1+1," mmmm")

```

I can't edit my comment so, here's a working version of the Google Sheets code.

Try it Online!

# Answer
> 1 votes
# APL(NARS), 235 chars, 470 bytes

```
{k←↑⍸0<w←+\v←(1-⍵),(12⍴28)+13561787⊤⍨12⍴4⋄k<2:¯1⋄d←1+v[k]-w[k]⋄(⍕d),({d∊11..13:'th'⋄1=10∣d:'st'⋄2=10∣d:'nd'⋄3=10∣d:'rd'⋄'th'}),' ',(k-1)⊃(m≠' ')⊂m←'January February March April May June July August September October November December'}

```

13561787 is the number that in base 4 can be summed to (12⍴28) for obtain the lenght of each month... test:

```
  f←{k←↑⍸0<w←+\v←(1-⍵),(12⍴28)+13561787⊤⍨12⍴4⋄k<2:¯1⋄d←1+v[k]-w[k]⋄(⍕d),({d∊11..13:'th'⋄1=10∣d:'st'⋄2=10∣d:'nd'⋄3=10∣d:'rd'⋄'th'}),' ',(k-1)⊃(m≠' ')⊂m←'January February March April May June July August September October November December'}
  ⊃f¨1 2 3 365 60 11
1st January
2nd January
3rd January
31st December
1st March
11th January

```

# Answer
> 1 votes
# Red, 124 bytes

```
func[n][d: 1-1-1 + n - 1[rejoin[d/4 either 5 > t: d/4 % 30 % 20[pick[th st nd rd]t + 1]['th]]pick system/locale/months d/3]]

```

Try it online!

Adds `n` \- 1 days to 1-1-1 (1-Jan-2001) to form a date, than uses Arnauld's method to index into month suffixes. Too bad Red is 1-indexed, this requires additional tweaking. The good thing is that Red knows the names of the months :)

# Answer
> 0 votes
# C (gcc), ~~174~~ 155 bytes

```
i;char a[99],*b="thstndrd";f(long x){x--;x*=86400;strftime(a,98,"%d   %B\0",gmtime(&x));i=*a==49?0:a[1]-48;a[2]=b[i=i>3?0:i*2];a[3]=b[++i];x=*a==48?a+1:a;}

```

Try it online!

# Answer
> 0 votes
# Vyxal , 81 bytes

```
kṁ¦Ṫ0p-'0>;:L`ƛǓ ⟇∩ ∨₄ ∨⋏ λ√ ∨ɾ ∨∑ ⟇τ ∨₆ ∨Þ ∨∞ ⟑√`⌈$i$t:t:4<[` ∨ǐ`3/vḢȮ‹i|‛th]$_+

```

Try it Online! What a mess.

```
kṁ                                                # List of month lengths
  ¦                                               # Cumulative sums
   Ṫ0p                                            # Pop off the last and prepend a 0
      -                                           # Subtract from input
       '0>;                                       # Filter by positive
           :L                                     # Duplicate and get length
             `...`⌈$i                             # Index into list of month names
                     $t:t                         # Get the last digit
                         :4<[                     # If it's less than 4 then...
                             `...`                # Push ' standard'
                                  3/              # Split into 3
                                    vḢ            # Lop off the first char of each
                                      Ȯ‹i         # Index the number into this
                                         |   ]    # Else
                                          ‛th     # Push 'th'
                                              $_+ # Swap, pop and concatenate
                                                  # (ṡ flag) join stack by spaces

```

---
Tags: code-golf, date
---


title: Minimal Power Root

text:
# Question
Title: Minimal Power Root
The *minimal power iteration* of a number \\$n\\$ is defined as follows:

$$\text{MPI}(n):=n^{\text{min}(\text{digits}(n))}$$

That is, \\$n\\$ raised to the lowest digit in \\$n\\$. For example, \\$\text{MPI}(32)=32^2=1024\\$ and \\$\text{MPI}(1234)=1234^1=1234\\$.

The *minimal power root* of a number \\$n\\$ is defined as the number obtained from repeatedly applying \\$\text{MPI}\\$ until a fixed point is found. Here is a table of the minimal power roots of numbers between 1 and 25:

```
   n              MPR(n)
--------------------------
   1                   1
   2                   1
   3              531441
   4                   1
   5                3125
   6 4738381338321616896
   7                   1
   8            16777216
   9                   1
  10                   1
  11                  11
  12                  12
  13                  13
  14                  14
  15                  15
  16                  16
  17                  17
  18                  18
  19                  19
  20                   1
  21                  21
  22                   1
  23              279841
  24                   1
  25                   1

```

**Challenge:** Generate the numbers whose minimal power root is not equal to 1 or itself.

Here are the first 50 numbers in this sequence:

> 3, 5, 6, 8, 23, 26, 27, 29, 35, 36, 39, 42, 47, 53, 59, 64, 72, 76, 78, 82, 83, 84, 92, 222, 223, 227, 228, 229, 233, 237, 239, 254, 263, 267, 268, 269, 273, 276, 277, 278, 279, 285, 286, 287, 289, 296, 335, 338, 339, 342

## Rules

* You may generate the first `n` numbers of this sequence (0- or 1-indexed), generate the `n`th term, create a generator which calculates these terms, output infinitely many of them, etc.
* You may take input and give output in any base, but the calculations for MPR must be in base 10. E.g., you may take input `###` (in unary) and output `### ##### ######` (in unary)
* You **must** yield numbers. You may not (e.g.) output `"3", "5", "6"`, since those are strings. `3, 5, 6` and `3 5 6` are both valid, however. Outputting `2 3`, `"23"`, or `twenty-three` are all considered invalid representations of the number `23`. (Again, you may use any base to represent these numbers.)
* This is a , so the shortest code (in bytes) wins.

# Answer
> 6 votes
# 05AB1E, 8 bytes

Generates the **nth** number **1**-indexed

```
µNÐΔWm}‹

```

Try it online!

**Explanation**

```
µ          # run until counter equals input
 NÐ        # push 3 copies of the current iteration index (1-based)
   Δ  }    # run this code until the result no longer changes
    Wm     # raise the number to the power of its minimum digit
       ‹   # check if greater than the index

```

Optionally as an infinite list at the same byte count:

```
∞ʒDΔWm}‹

```

Try it online!

# Answer
> 7 votes
# Perl 6, 49 bytes

```
{grep {($_,{$_**.comb.min}...*==*).tail>$_},1..*}

```

Try it online!

Returns an infinite sequence. I suppose that the following 45 byte version works, too, but I can't prove that the fixed point is always found after n iterations.

```
{grep {($_,{$_**.comb.min}...*)[$_]>$_},3..*}

```

# Answer
> 5 votes
# , ~~41~~ ~~39~~ 37 bytes

```
(>:[echo^:(<(^0".@{/:~@":)^:_))^:_]1x

```

Try it online!

This one is a full program printing the infinite sequence. A very rare occasion where a full program beats a verb in J.

### How it works

```
(>:[echo^:(<mpi_fix))^:_]1x    Using the mpi_fix below; it finds the MPI fixpoint
          (<mpi_fix)           Is mpi_fix greater than the input?
    echo^:                     If so, apply echo; do nothing otherwise
                               echo returns an empty array
 >:[                           Discard the above and return input+1
(                   )^:_       Repeat the above infinitely (increment has no fixpoint)
                        ]1x    starting from arbitrary-precision number 1

```

---

# , ~~41~~ 39 bytes

```
>:^:(>:(^0".@{/:~@":)^:_)^:_@>:@]^:[&0x

```

Try it online!

A monadic verb. Given a 1-based index, returns the number at that index. The footer checks that first 20 terms are correct.

Reading the word "fixpoint", I immediately thought "Oh yeah, `^:_` will do the great job." Then I ended up with this abomination of angry and sad faces. And it's not even a train, it's a *single verb*.

### Ungolfed & How it works

```
nth_term =: >:^:(>:(^0".@{/:~@":)^:_)^:_@>:@]^:[&0x

mpi =: ^0".@{/:~@":    Find the MPI
             /:~@":    Sort the string representation
        0   {          Take first item
         ".@           Convert back to number
       ^               Raise the input to the power of above

mpi_fix =: mpi^:_      Find the MPI fixpoint

next_term =: >:^:(>:mpi_fix)^:_@>:    Given a number, find the next term
                               @>:    Increment once, and then...
                  >:mpi_fix           Is mpi_fix not greater than input?
             >:^:           ^:_       Increment while the above is true

nth_term =: next_term@]^:[&0x    Given one-based index, find the nth term
            next_term@]          Apply next_term monadically
                       ^:[       n times
                          &0x    to the starting value of zero

```

The arbitrary-precision integer `0x` is needed to compute the fixpoint accurately, e.g. of the number 6.

# Answer
> 4 votes
# Mathematica, ~~59~~ 51 bytes

*-8 bytes thanks to Misha Lavrov.*

```
Select[Range@#,#<(#//.x_:>x^Min@IntegerDigits@x)&]&

```

Pure function. Takes a number as input, and returns the list of terms up to that number as output. Nothing very complicated here.

# Answer
> 4 votes
# Jelly, 10 bytes

```
*DṂƊƬḊCȦµ#

```

A monadic Link taking an integer, `I`, from STDIN which yields the first `I` entries.

**Try it online!**

(`*DṂƊƬṪ%@µ#` works for 10 too)

### How?

Counts up starting a `n=0` until `input` truthy results of a monadic function are encountered and yields those `n`s.

The function repeatedly applies another monadic function starting with `x=n` and collects the values of `x` until the results are no longer unique. (e.g.: `19` yields `[19]`; `23` yields `[23,529,279841]`; `24` yields `[24, 576, 63403380965376, 1]`; etc...) and then dequeues the result (removes the leftmost value), complements all the values (`1-x`) and uses `Ȧ` to yield `0` when there is a zero in the list or if it's empty.

The innermost function raises the current `x` to *all* the digits of `x` and then keeps the minimum (doing this is a byte save over finding the minimum digit first).

```
*DṂƊƬḊCȦµ# - Link (call the input number I)
         # - count up from 0 and yield the first I for which this yields a truthy value:
        µ  -   a monadic chain:
    Ƭ      -     collect until results are not unique:
   Ɗ       -       last three links as a monad:
 D         -         convert to a list of decimal digits
*          -         exponentiate
  Ṃ        -         minimum
     Ḋ     -     dequeue
      C    -     compliment
       Ȧ   -     any-and-all?

```

# Answer
> 4 votes
# Pyth, 10 bytes

```
.f>u^GshS`

```

Try it online!

This generates a list of the first \\$ n \\$ such numbers. The auto-filled program has `GZZQ` as a suffix. This simply finds (`.f`) the first `Q` numbers that have a minimal power root `u^GshS`G` greater than itself `Z`.

The minimal power root code works by finding a fixed point `u` of raising the current number `G` to the power of it's minimal digit, which is the same as the first digit (`h`) sorted lexicographically (`S`), then converted back to an integer (`s`).

# Answer
> 3 votes
# Python 3, ~~90~~ 88 bytes

-2 bytes by @mypetlion

```
def F(x):m=x**int(min(str(x)));return[int,F][m>x](m)
x=1
while 1:x<F(x)and print(x);x+=1

```

Try it online!

`print` as an expression saves two bytes over using `if` statement in Python 2. `F` computes the MPI fixpoint; the rest gives the infinite sequence to STDOUT.

# Answer
> 3 votes
## Haskell, ~~67~~ 62 bytes

```
filter((<)<*>until((==)=<<g)g)[1..]
g a=a^read[minimum$show a]

```

Returns an infinite list.

Try it online!

# Answer
> 2 votes
# Ruby, 52 bytes

```
x=1;loop{b=x+=1;1while b<b**=b.digits.min;b>x&&p(x)}

```

Try it online!

Prints infinite sequence

# Answer
> 2 votes
# Java 10, ~~178~~ 173 bytes

```
v->{for(int x=1,m;;){var b=new java.math.BigInteger(++x+"");for(m=9;m>1;)b=b.pow(m=(b+"").chars().min().orElse(0)-48);if(b.compareTo(b.valueOf(x))>0)System.out.println(x);}}

```

Port of *@GB*'s Ruby answer, so also prints indefinitely.

Try it online.

**Explanation:**

```
v->{             // Method with empty unused parameter and no return-type
  for(int x=1,   //  Start an integer `x` at 1
      m;         //  Temp integer for the smallest digit, starting uninitialized
      ;){        //  Loop indefinitely
    var b=new java.math.BigInteger(++x
                 //   Increase `x` by 1 first
          +"");  //   And create a BigInteger `b` for the new `x`
    for(m=9;     //   Reset `m` to 9
        m>1;)    //   Loop as long as the smallest digit is not 0 nor 1
      b=b.pow(m=(b+"").chars().min().orElse(0)-48
                 //    Set `m` to the smallest digit in `b`
              ); //    Set `b` to `b` to the power of digit `m`
    if(b.compareTo(b.valueOf(x))>0)
                 //   If `b` is larger than `x`:
      System.out.println(x);}}
                 //    Print `x` with a trailing newline

```

# Answer
> 1 votes
# JavaScript (Node.js), ~~98~~ ~~90~~ ~~89~~ 86 bytes

-3 bytes thanks @Conor O'Brien

```
function*(){for(n=0n;;x>n&&(yield n))for(x=++n;(b=Math.min(...""+x))-1;)x**=BigInt(b)}

```

Try it online!

Using the fact that \\$MPR(n)\>n\\$ if \\$MPR(n)\notin \\{1,n\\}\\$

Seems that a generator is shorter than returning an array of `n` numbers?

Or printing infinitely - 72 bytes

```
for(n=0n;;x>n&&alert(n))for(x=++n;(b=Math.min(...""+x))-1;)x**=BigInt(b)

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 75 bytes

Returns the \\$n\\$th term, 1-indexed.

```
f=(i,x=n=1n)=>(N=x**BigInt(Math.min(...x+'')))>x?f(i,N):(i-=N>n)?f(i,++n):n

```

Try it online!

# Answer
> 1 votes
# C (gcc), ~~171~~ ~~153~~ 138 bytes

```
__int128 m,a,t,h,s;r(){for(a=10,h=s;a=fmin(h%10,a),h/=10;);a=pow(s,a);a-s&&r(s=a);}f(n){for(;t-n;a-1&&a-m&&printf("%lu ",m,t++))r(s=++m);}

```

Outputs the first `n` terms whose MPRs are representable within the largest "integer" type.

Brute-forces the solution but still works surprisingly fast.

Some things may be able to be inlined (such as `r`, which is only called once), but it may require a decent amount of effort.

See previous revision for solution without `-lm`.

*-18 bytes thanks to ceilingcat!*

*-15 bytes and ultra-precision thanks to rtpax!*

Try it online!

# Answer
> 1 votes
# Vyxal, 6 bytes

```
λfge;Ẋ

```

Try it Online!

```
λ   ;Ẋ # While result changes...
 f     # Convert to digitlist
  g    # Take minimum
   e   # Number to power of that

```

# Answer
> 0 votes
# Jelly, 14 bytes

```
3*DṂ$$ÐLḟ1,$Ɗ#

```

Try it online!

# Answer
> 0 votes
# JavaScript (Chrome), ~~78~~ 77 bytes

```
F=x=>(m=x**BigInt(Math.min(...''+x)))>x?F(m):m
for(x=0n;++x;)x<F(x)&&alert(x)

```

Try it online!

Port of my own Python 3 solution. The latest version of Chrome supports `BigInt` (tested on my PC). Don't try this code as-is on your browser though.

# Answer
> 0 votes
# Racket, 270, 257 233 bytes

```
(define(f n)(local((define(m x)(expt x(-(first(sort(map char->integer(string->list(~v x)))<))48)))(define(g y)(if(= y(m y))y(g(m y))))(define(k x l)(if(=(length l)n)l(if(< x(g x))(k(+ x 1)(cons x l))(k(+ x 1)l)))))(reverse(k 1'()))))

```

Try it online!

This is my first Racket submission, so it can definitely be golfed much further. Nevertheless I'm somewhat content, at least for managing to solve the task.

## More readable:

```
(define (f n)
  (local ((define (m x)
           (expt x
                 (- (first (sort (map char->integer (string->list (~v x)))
                                 <))
                    48)))
         (define (g y)
           (if
             (= y (m y))
             y
             (g (m y))))
         (define (k x l)
           (if (= (length l) n)
               l
               (if (< x (g x))
                   (k (+ x 1) (cons x l))
                   (k (+ x 1) l))))
    (reverse (k 1 '()))))

```

# Answer
> 0 votes
# Axiom, 168 bytes

```
u(x)==(y:=x::String;x^reduce(min,[ord(y.i)-48 for i in 1..#y])::NNI)
q(a:PI):PI==(b:=a;repeat(c:=u(b);c=b=>break;b:=c);b)
z(x)==[i for i in 1..x|(m:=q(i))~=1 and m~=i]

```

The function to use it is z(); here it print numbers that has the corrispondence one number not 1, not itself and are less than its argument.

```
(6) -> z 1000
 (6)
 [3, 5, 6, 8, 23, 26, 27, 29, 35, 36, 39, 42, 47, 53, 59, 64, 72, 76, 78, 82,
  83, 84, 92, 222, 223, 227, 228, 229, 233, 237, 239, 254, 263, 267, 268,
  269, 273, 276, 277, 278, 279, 285, 286, 287, 289, 296, 335, 338, 339, 342,
  346, 347, 348, 354, 358, 363, 365, 372, 373, 374, 376, 382, 383, 386, 392,
  394, 395, 399, 423, 424, 426, 427, 428, 432, 433, 435, 436, 442, 447, 459,
  462, 464, 466, 467, 468, 469, 476, 477, 479, 483, 487, 488, 489, 493, 494,
  523, 524, 527, 529, 533, 537, 542, 546, 553, 556, 557, 562, 563, 572, 573,
  577, 582, 583, 584, 594, 595, 598, 623, 626, 627, 629, 632, 633, 642, 646,
  647, 648, 663, 664, 669, 672, 676, 682, 683, 684, 693, 694, 695, 698, 722,
  724, 729, 736, 759, 763, 773, 775, 782, 786, 823, 829, 835, 846, 847, 856,
  873, 876, 885, 893, 894, 896, 923, 924, 928, 933, 953, 954, 962, 969, 973,
  974, 984, 993, 994, 995]
                                               Type: List PositiveInteger

```

# Answer
> 0 votes
# Visual Basic .NET (.NET Core), 290 bytes (includes imports)

```
Iterator Function A()As System.Collections.IEnumerable
Dim i=B.One,q=i,p=i
While 1=1
q=i-1
p=i
While q<>p
For j=0To 9
If p.ToString.Contains(j)Then
q=p
p=B.Pow(p,j)
Exit For
End If
Next
End While
If p>1And p<>i Then Yield i
i+=1
End While
End Function

```

Try it online!

Requires the following import:

```
Imports B = System.Numerics.BigInteger

```

This uses an iterator function to return an infinite (lazy loaded) list of integers that meets the criteria. Uses `BigInteger` to avoid any size restrictions, particularly with intermediate calculations.

Un-golfed:

```
Iterator Function A() As System.Collections.IEnumerable
    Dim i As B = 1
    While True
        Dim prevProduct As B = 0
        Dim product As B = i
        While prevProduct <> product
            For j = 0 To 9
                If product.ToString.Contains(j) Then
                    prevProduct = product
                    product = B.Pow(product, j)
                    Exit For
                End If
            Next
        End While
        If product <> 1 And product <> i Then
            Yield i
        End If
        i += 1
    End While
End Function

```

# Answer
> 0 votes
# Common Lisp, 238 bytes

```
(defun x(m n o p q)(setf i(sort(map 'list #'digit-char-p(prin1-to-string m))#'<))(setf j(expt m(first i)))(cond((= q p)nil)((and(= n j)(not(= n 1))(not(= n o)))(cons o(x(1+ o)0(1+ o)p(1+ q))))((= n j)(x(1+ o)0(1+ o)p q))(t(x j j o p q))))

```

Try it online!

# Answer
> 0 votes
# APL(NARS), 96 chars, 192 bytes

```
r←f w;k;i;a
   r←⍬⋄k←1
A: i←k
B: →C×⍳i=a←i*⌊/⍎¨⍕i⋄i←a⋄→B
C: →D×⍳(a=k)∨a=1⋄r←r,k
D: k+←1⋄→A×⍳k≤w

```

test (partial result for argument 22 seems to much big so \<21 arguments I don't know if can be ok)

```
  f 21
3 5 6 8

```

# Answer
> 0 votes
# Python 3, 102 bytes

```
x=int(input())
a=c=0
while x:
 a+=1;b=a
 while b-c:b,c=b**int(min(str(b))),b
 x-=b!=1and b!=a
print(a)

```

Try it online!

Decided to try a Python 3 solution that directly prints the nth term in the sequence.

# Answer
> 0 votes
# Japt, 44 bytes

```

_ì ñ g
_gV ¥1?Z:ZpZgV)gW
@@[1X]øXgW}fXÄ}gUÄ

```

Try it online!

Substantially different from the other Japt answer.

Explanation:

```
                        Empty line preserves the input

_ì ñ g                Function V finds the smallest digit in a number Z
 ì                          Get the digits of Z
   ñ                        Sort the digits
     g                      Get the first (smallest) digit

_gV ¥1?Z:ZpZgV)gW     Function W finds the MPR of a number Z
 gV ¥1?Z                    If V(Z) is 1, then it's stable; return it
        :ZpZgV)             Otherwise get MPI of Z...
               gW           And call W on it ( MPR(Z) == MPR(MPI(Z)) )

@@[1X]øXgW}fXÄ}gUÄ    Main program
@             }gUÄ      Get the nth number by repeatedly applying...
 @        }fXÄ              Find the next smallest number X which returns false to...
       XgW                    MPR(X)
      ø                       is either...
  [1X]                        1 or X

```

In terms of future golfing possibilities, I do a lot of manually calling a function on a number, which I suspect could be reduced but I'm not sure how.

# Answer
> 0 votes
# Husk, ~~16~~ ~~12~~ 10 bytes

```
fS>ωṠ^o▼dN

```

Saved 6 bytes thanks to H.PWiz.
Try it online!

### Explanation

```
fS>ωṠ^o▼dN
f        N       Filter the natural numbers where...
   ω             ... the fixed point...
    Ṡ^o▼d        ... of raising the number to its smallest digit...
 S>              ... is greater than the number.

```

# Answer
> 0 votes
# C (clang) \+ `-DL=long long` `-lm`, 213 bytes

```
q(char*a,char*b){return*a>*b;}L f(L a){char*c;asprintf(&c,"%lld",a);qsort(c,strlen(c),1,q);L b=pow(a,*c-48);return b>a?f(b):b;}i;g(j){for(i=0;j;i++){L x=f(i);x!=i&x!=1&x>0&&printf("%d\n",i)&&j--;}}

```

Try it online!

Function `g(j)` prints the first `j` terms of the sequence.

# Answer
> 0 votes
# Python 3, 54 bytes

```
lambda n,x=0:n!=x and f(n**min(map(int,str(n))),n)or n

```

Try it online!

# Answer
> 0 votes
# Burlesque, 35 bytes

```
r0f{J{J<]**}{J<]1!=}w!J1!=x/x/!=&&}

```

Try it online!

"Produces" the infinite list of MPRs (i.e. never finishes, never prints). For a finite list use:

# Burlesque, 36 bytes

```
ri{J{J<]**}{J<]1!=}w!J1!=x/x/!=&&}FO

```

Try it online!

Takes an integer input `N` and tests the first `N` values

```
r0      # All integers starting from 0
f{      # Filter for
 J      # Duplicate original value (for later)
 {
  J     # Duplicate current value
  <]    # Minimum digit
  **    # Raise current value to power of min digit
 }
 {
  J<]   # Find minimum digit (non-destructive)
  1!=   # Not equal to 1
 }w!    # While current value does not contain 0 or 1
 J      # Duplicate output
 1!=    # Not equal to 1
 x/x/   # Reorganise stack
 !=     # Output is not equal to original
 &&     # AND not equal to 1
}

```

# Answer
> 0 votes
# Dash (or other generic Bourne shell) + bc, 190 bytes

```
a=0
while :
do
a=`echo $a+1|bc`
b=$a
while :
do
for m in `seq 0 9`
do
case "$b" in
*$m*)break;;
esac
done
case $m in
0)break;;
1)[ $a = $b ]||echo $a;break;;
esac
b=`echo $b^$m|bc`
done
done

```

Try it online!

This implementation prints the infinite sequence -- as far as it is allowed.

I specifically did not use bash arithmetic because I didn't want the limit of bash's number system. If you change the line `a=0` to `a=$1`, you can start looking at any number (though subtract 1 if you want the first number considered). Passing in 9922289264447635429194, I found part of the sequence is:

> 9922289264447635429236
> 9922289264447635429254
> 9922289264447635429323
> 9922289264447635429328
> 9922289264447635429335

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