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

  1. \$r_0\$ is a limit ordinal
  2. \$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 < n\$, \$a_i\$ is an ordinal expressed in Cantor normal form and \$a_n\$ is an integer. Furthermore, for \$1 < i < n\$, the ordinal inequality \$a_{i-1} \ge a_i\$ holds.


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.


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.


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


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] => [100] * [1, 1]
[2,1] => prime
[3,0] => [2,0] * [1,0]
[[1,1],2] => [2] * [[1,1],1]
[[1,1],0] => [[1,0],0] * [1,0] 
[[1,0],0] => prime
[1,1,1] => [1,1] * [2]
  • 3
    \$\begingroup\$ Welcome to Code Golf Stack Exchange. Nice first challenge. Maybe some test cases? \$\endgroup\$ – Adám Dec 25 '19 at 12:10
  • 1
    \$\begingroup\$ I think the Wikipedia page clears up primness and multiplication well enough. For example, [2,1] would be prime, but [2] would be composite and output [1],[1]. \$\endgroup\$ – Baaing Cow Dec 25 '19 at 13:04
  • 3
    \$\begingroup\$ Sure, but it is customary here to include some test cases, especially edge cases to ease testing and verification of solution posts. \$\endgroup\$ – Adám Dec 25 '19 at 13:05
  • 7
    \$\begingroup\$ Questions should be self contained, rather than link elsewhere. Can you add explanations for the linked sections, and maybe a short description of an algorithm to determine if an ordinal number is prime? \$\endgroup\$ – Jo King Dec 25 '19 at 14:21
  • 4
    \$\begingroup\$ @JoKing While I agree in principle, I do think that this question is self contained. You should not have to explain advanced mathematics, just to ask about it. \$\endgroup\$ – Post Rock Garf Hunter Dec 26 '19 at 0:33

Haskell, 1068 1042 bytes

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


[]\$ = 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] => p
[W [W [W [] 1] 1] 1] => p
[W [W [W [W [] 1] 1] 1] 1] => p
[W [W [] 1] 1,W [] 100] => [W [] 2]*[W [W [] 1] 1,W [] 50]
[W [W [] 3] 1] => [W [W [] 1] 1]*[W [W [] 2] 1]
[W [W [W [] 1] 1,W [] 1] 1,W [] 2] => [W [] 2]*[W [W [W [] 1] 1,W [] 1] 1,W [] 1]
[W [W [W [] 1] 1,W [] 1] 1] => [W [W [W [] 1] 1] 1]*[W [W [] 1] 1]
[W [W [] 1] 2,W [] 1] => [W [W [] 1] 1,W [] 1]*[W [] 2]
[W [] 2903591] => [W [] 1699]*[W [] 1709]

Output from the pretty-print version:

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


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.


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 < 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.


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.

New contributor
SirBogman is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • \$\begingroup\$ Welcome to PPCG and nice first answer. Having you also seen the approach given at Wikipedia for factorisation in to primes en.wikipedia.org/wiki/…? It would appear only ordinal subtraction would need to be implemented, but I am not sure \$\endgroup\$ – Kritixi Lithos 3 hours ago
  • \$\begingroup\$ I didn't fully understand it, but I'll take another look at some point. \$\endgroup\$ – SirBogman 1 hour ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.