15
\$\begingroup\$

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.

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 , 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] => [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]
\$\endgroup\$
  • 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\$ – Ad Hoc Garf Hunter Dec 26 '19 at 0:33
6
\$\begingroup\$

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<0
k=1>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>EQ
b x=break(\(W y _)->y#x/=GT)
x&[]=x
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
x![]=x
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
[]%_=([],k)
x@(W g h:d)%b@(W e f:_)|b?x=([],m)|g!e?[]=(\(q,r)->([W(g!e)h]&q,r))$d%b|k=(\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?[])
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<-[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,x?y&&x?q&&r&&(l y||not(l y&&l q||d y<2&&d q<2)||y#q<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}>\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.

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] => 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)

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

| improve this answer | |
\$\endgroup\$
  • \$\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\$ – user41805 Jan 29 at 18:26
  • \$\begingroup\$ I didn't fully understand it, but I'll take another look at some point. \$\endgroup\$ – SirBogman Jan 29 at 19:37

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.