Is this ordinal prime? You are given an countable ordinal \$1 &lt; r &lt; \varepsilon_0\$. Determine whether or not it is prime. If not, provide exactly two ordinals \$r_0, r_1 &lt; r\$ such that \$r_0r_1 = r\$, following rules of ordinal multiplication, and furthermore satisfy at least one (not necessarily both) of the following:


\$r_0\$ is a limit ordinal
\$r_0 \le r_1\$


More accurately, an ordinal expressed in Cantor normal form is a list \$[a_1, a_2, a_3, \dots, a_{n-1}, a_n]\$, where when \$1 \le i &lt; n\$, \$a_i\$ is an ordinal expressed in Cantor normal form and \$a_n\$ is an integer. Furthermore, for \$1 &lt; i &lt; n\$, the ordinal inequality \$a_{i-1} \ge a_i\$ holds.

Input

Any input that can provably describe any ordinal also expressible in Cantor normal form is accepted. For input forms deviating greatly from Cantor normal form, please also provide a brief way to convert a Cantor normal form ordinal to input.

Output

If the given ordinal is prime, then a constant result, distinct from non-prime inputs must be returned.
Otherwise, return two ordinals, expressed the same way as the input, representing \$r_0\$ and \$r_1\$, respectively.

Scoring

This is code-golf, so shortest program (in bytes) wins.

Examples

An input of \$\omega^2+1\$, or [2,1] in Cantor normal form, would be marked prime.
On the other hand, an input of \$\omega+2\$, or [1,2] in Cantor normal form, would be composite and the program should return a pair ([2],[1,1]) in whatever form it accepted.
Remember that integers are ordinals too.
You do not need to consider \$r=1\$.

More examples:

[1,100] =&gt; [100] * [1, 1]
[2,1] =&gt; prime
[3,0] =&gt; [2,0] * [1,0]
[[1,1],2] =&gt; [2] * [[1,1],1]
[[1,1],0] =&gt; [[1,0],0] * [1,0] 
[[1,0],0] =&gt; prime
[1,1,1] =&gt; [1,1] * [2]
Haskell, 1068 1042 1012 bytes

-30, mostly from replacing if/then with guards. I'm sure it can be golfed more.



data W=W[W]Int deriving Show
f EQ y=y
f x _=x
m=1&lt;0
k=1&gt;0
[]#[]=EQ
[]#_=LT
_#[]=GT
(W x y:z)#(W a b:d)=f(x#a)$f(compare y b)$z#d
x?y=x#y&gt;EQ
b x=break(\(W y _)-&gt;y#x/=GT)
x&amp;[]=x
d&amp;(x@(W v w):u)=case b v d of(y,W f m:_)|f#v&gt;LT-&gt;y++(W v$m+w):u;(y,_)-&gt;y++x:u
x![]=x
d!(W v w:u)=case b v d of(_:_,_)-&gt;d;(_,W f m:g)-&gt;if w&lt;m then(W f$m-w):g else g!u
[]%_=([],k)
x@(W g h:d)%b@(W e f:_)|b?x=([],m)|g!e?[]=(\(q,r)-&gt;([W(g!e)h]&amp;q,r))$d%b|k=(\q-&gt;(q,(foldl(&amp;)[]$t b&lt;$&gt;q)#x==EQ))[W[]$div h f]
t(W x y:z)(W[]n)=(W x$y*n):z
t(W x _:_)(W b n)=[W(x&amp;b)n]
l=all(\(W e _)-&gt;e?[])
q=max
o[]=0
o(W e n:u)=q n$q(o e)$o u
v[]=0
v(W e n:u)=q(1+length u)$q(v e)$v u
d[]=0
d(W e n:u)=q(1+d e)$d u
e(W x _:[])(W y _:_)=x?y
e(_:x)y=e x y
g _ 0_ n=[[W[]x]|x&lt;-[1..n]]
g m d s n|p&lt;-g m(d-1)s n=fst$h s$filter(m?)$p++[[W x y]|x&lt;-p,y&lt;-[1..n]]
h 1z=(z,z)
h n z|(a,p)&lt;-h(n-1)z,n&lt;-[x++y|x&lt;-z,y&lt;-p,e x y]=(a++n,n)
r x=p x$g x(d x)(v x)$o x
p _[]="p"
p x(y:z)|(q,r)&lt;-x%y,x?y&amp;&amp;x?q&amp;&amp;r&amp;&amp;(l y||not(l y&amp;&amp;l q||d y&lt;2&amp;&amp;d q&lt;2)||y#q&lt;GT)=show y++"*"++show q|k=p x z


Try it online!

Or try a version that pretty-prints the inputs and outputs.

Input Format

The input format is Cantor normal form, written as \$\omega ^{\beta _{1}}c_{1}+\omega ^{\beta _{2}}c_{2}+\cdots+\omega ^{\beta _{k}}c_{k}\$, where \$k\$ is a natural number, \$ c_{1},c_{2},\ldots ,c_{k}\$ are positive integers, and \$ \beta _{1}&gt;\beta _{2}&gt;\ldots &gt;\beta _{k}\geq 0 \$ are ordinal numbers.

Each term \$\omega ^{b}c\$ is written as W b c and terms are written as a list in [] separated by commas.

Examples:

[]\$ = 0\$

[W[]1]\$ = 1\$

[W[W[]1]1]\$ = \omega\$

[W[W[]1]1,W[]1]\$ = \omega + 1\$

[W[W[]2]3,W[]4] \$=\omega^2\cdot 3 + 4\$

[W[W[W[]2]1]1,W[]4] \$=\omega^{\omega^2} + 4\$

[W[W[W[]1]1,W[]1]1,W[]1]\$ = \omega^{\omega+1} + 1\$

Test Cases

Output from the main version:

[W [W [] 2] 1,W [] 1] =&gt; p
[W [W [W [] 1] 1] 1] =&gt; p
[W [W [W [W [] 1] 1] 1] 1] =&gt; p
[W [W [] 1] 1,W [] 100] =&gt; [W [] 2]*[W [W [] 1] 1,W [] 50]
[W [W [] 3] 1] =&gt; [W [W [] 1] 1]*[W [W [] 2] 1]
[W [W [W [] 1] 1,W [] 1] 1,W [] 2] =&gt; [W [] 2]*[W [W [W [] 1] 1,W [] 1] 1,W [] 1]
[W [W [W [] 1] 1,W [] 1] 1] =&gt; [W [W [W [] 1] 1] 1]*[W [W [] 1] 1]
[W [W [] 1] 2,W [] 1] =&gt; [W [W [] 1] 1,W [] 1]*[W [] 2]
[W [] 2903591] =&gt; [W [] 1699]*[W [] 1709]


Output from the pretty-print version:

[W [W [] 2] 1,W [] 1] == w^2 + 1 =&gt; p
[W [W [W [] 1] 1] 1] == w^w =&gt; p
[W [W [W [W [] 1] 1] 1] 1] == w^(w^w) =&gt; p
[W [W [] 1] 1,W [] 100] == w + 100 =&gt; (2)*(w + 50)
[W [W [] 3] 1] == w^3 =&gt; (w)*(w^2)
[W [W [W [] 1] 1,W [] 1] 1,W [] 2] == w^(w + 1) + 2 =&gt; (2)*(w^(w + 1) + 1)
[W [W [W [] 1] 1,W [] 1] 1] == w^(w + 1) =&gt; (w^w)*(w)
[W [W [] 1] 2,W [] 1] == w*2 + 1 =&gt; (w + 1)*(2)
[W [] 2903591] == 2903591 =&gt; (1699)*(1709)


Strategy

This is probably not the fastest solution, but I thought it might be relatively short for code golf. It works for all of the test cases and works well for natural numbers. For ordinals with many terms, this may take a very long time to run.


Generate a sequence of ordinals which may divide the input.
Test each ordinal in the sequence to determine whether it divides the input and meets the additional criteria. If it does, return a formatted string containing the divisor and quotient.
If the sequence was exhausted, return "p" for prime.


Implementation

I started with code I found online that implements ordinal addition and multiplication and uses the QuickCheck library to test that properties (theorems) are true for a large number of inputs.

I implemented left subtraction and then left division with remainder and verified that the operations were consistent with the following theorems.

Left subtraction: Let \$x\$ and \$y\$ be ordinals such that \$x \geq y\$. Then there exists a unique ordinal \$z\$ such that \$x = y + z\$.

Left division: Let \$x\$ and \$y\$ be ordinals. Suppose \$y\neq0\$. Then there exist unique ordinals \$z\$ and \$w\$ such that \$x=y\cdot z+w\$ and \$w &lt; y\$.

Generated Sequences

To test whether an ordinal is prime, I generate a list of potential divisors. This would be easy for natural numbers, but infinite ordinals are greater than infinitely many ordinals.

I check the given ordinal to determine the depth, maximum number of terms (at each depth), and maximum coefficient.

I then recursively generate ordinals that are less than the given one and up to the given depth, term count, maximum coefficient. I don't have a proof that this is sufficient, but intuitively it seems like it would be.

Here are some examples.

Example 1: \$\omega^2\cdot 3 + 4\$. Depth: 2, Max term count: 2, Max coefficient: 4. Generated list of potential divisors, length 26: \$1, 2, \omega, \omega + 1, \omega + 2, \omega\cdot2, \omega\cdot2 + 1, \omega\cdot2 + 2, \omega^2, \omega^2 + 1, \omega^2 + 2, \omega^2 + \omega, \omega^2 + \omega + 1, \omega^2 + \omega + 2, \omega^2 + \omega\cdot2, \omega^2 + \omega\cdot2 + 1, \omega^2 + \omega\cdot2 + 2, \omega^2\cdot2, \omega^2\cdot2 + 1, \omega^2\cdot2 + 2, \omega^2\cdot2 + \omega, \omega^2\cdot2 + \omega + 1, \omega^2\cdot2 + \omega + 2, \omega^2\cdot2 + \omega\cdot2, \omega^2\cdot2 + \omega\cdot2 + 1, \omega^2\cdot2 + \omega\cdot2 + 2\$

Example 2: \$\omega^\omega\cdot3+4\$. Depth: 3, Max term count: 2, Max coefficient: 4. Generated terms list length: 151,994.
Since that list is generated lazily, the program still gives a fast answer.

As the depth and maximum term count increase, the lengths of the generated sequences increase very quickly.

Note

For the last given test case, \$\omega\cdot2+1=(\omega+1)\cdot2\$, I was unable to satisfy either of the two given additional criteria (\$_0\$ is a limit ordinal, \$_0 \leq r_1\$). However, I was able to satisfy the following criteria stated on Wikipedia, which is a slight variation of the given criteria:


Every limit prime occurs before every successor prime
If two consecutive primes of the prime factorization are both limits or both finite, then the second one is at most the first one.


If anyone is interested, I could provide a less golfed version of this code.