# Gödel encoding - Part I

Related but different.

Part II

Taken from the book: Marvin Minsky 1967 – Computation:
Finite and Infinite Machines, chapter 14.

### Background

As the Gödel proved, it is possible to encode with a unique positive integer not just any string
but any list structure, with any level of nesting.

Procedure of encoding $$\G(x)\$$ is defined inductively:

1. If $$\x\$$ is a number, $$\G(x) = 2^x\$$
2. If $$\x\$$ is a list $$\[n_0, n_1, n_2, n_3, …]\$$, $$\G(x) = 3^{G(n_0)} \cdot 5^{G(n_1)} \cdot 7^{G(n_2)} \cdot 11^{G(n_3)} \cdot...\$$
Bases are consecutive primes.

### Examples:

 → 3

[] → $$\3^3 =\$$ 27

[1, 2, 3] → $$\3^{2^1} \cdot 5^{2^2} \cdot 7^{2^3} = \$$ 32427005625

[[0, 1], 1] → $$\3^{3^{2^0} \cdot 5^{2^1}} \cdot 5^{2^1} = \$$ 15206669692833942727992099815471532675

Create a program that encoding (in this way) any given (possibly ragged) list to integer number.
This is code-golf, so the shortest code in bytes wins.

### Input

Valid non-empty list.
UPD
Some considerations regarding empty lists are given here.

You may assume:

• There are no empty sublists
• Structure is not broken (all parentheses are paired)
• List contains only non-negative integers

### Output

Positive integer obtained by the specified algorithm

### Note

Numbers can be very large, be careful! Your code must be correct in principle, but it is acceptable that it cannot print some number. However, all test cases are checked for TIO with Mathematica program and work correctly.

### Test cases

[0,0,0,0,0] → 15015
[1, 1, 1] → 11025
[, ] → 38443359375
[0, [], 0] → 156462192535400390625
[[, 0], 0] → 128925668357571406980580744739545891609191243761536322527975268535

• Wouldn't an empty list just be encoded as 1? Ah, that would be the same as the encoding of the number 0. Apr 12 at 22:07
• I upvoted just for "the Gödel"
– Stef
Apr 13 at 18:27
• @Stef I dont know what you mean but I upvoted (ofc because the question is good) but also! it does remind me of Kurt Godel (which, has some related to this question right? maybe not sure) anyway, have a great day on both of you ^^ Apr 13 at 19:19
• @PaŭloEbermann Thank you for interesting idea, I made some updates Apr 14 at 18:32

# Jelly,  11 10 9  8 bytes

-1 thanks to Unrelated String! (Use of a dyadic chain in place of a monadic compound link avoiding the need for argument manipulation with .)

ß€Żð%¡ÆẸ


A monadic Link that accepts a ragged list of non-negative integers and yields its Gödel encoding.

Try it online! Or see the test-suite.

### How?

ß€Żð%¡ÆẸ - Link: non-empty list OR number, X
¡   - repeat...
%    -   ...number of times: (X) modulo (X)
positive ints -> 0
zero -> nan*
non-empty lists -> non-empty lists*
* truthy non-integers are treated by ¡ as 1
ð     -   ...action: the dyadic chain - f(X, X):
€       -              for each E in X:
ß        -                call this Link with X=E
Ż      -              prefix with a zero (if X=zero we get )
ÆẸ  - recompose from prime exponent list
e.g.:
[0,4,0,2] -> 3^4 × 7^2 = 3969
 -> 2^0 = 1
n -> 2^n (non-list n treated as [n])

• 8 with ð Apr 12 at 9:41
• Pesky  :) thanks @UnrelatedString Apr 12 at 16:35

# Brachylog, 24 bytes

;2^₍|↰ᵐGl~lℕ₃ᵐṗᵐ≠≜;Gz^ᵐ×


Try it online!

Surely there are shorter ways to generate a list of primes…

Brachylog is based on SWI-Prolog and can deal with arbitrarily large integers, but this will quickly run out of memory for even simple lists.

### Explanation

;2^₍                       Output = 2^Input
|                      Or (if the input is not an integer)
↰ᵐG                   Recursive call of this predicate for all elements of the Input; call the result G
Gl~l                Take a list with as many elements as G
ℕ₃ᵐṗᵐ≠≜         It must be a list of primes greater than 3 and all different (it always unifies with increasing magnitudes)
;Gz     Zip with G
^ᵐ   Map power
×  Multiply


# Vyxal, A2321 11 bytes

@AndrovT cool result:

Eλ-[żǎ$vxeΠ  Try it Online! Unfortunately, can't explain in detail. Hope one of Vyxal' experts helps... My old version, maybe useful for beginners in Vyxal: ƛIȧ[:L›ÞpŻ$vx¨£e|E]fΠ


Every input must be list of lists, so first test case should be [[1, 1, 1]] etc.

-2 bytes thanks @emanresu (Vyxal chat)

ƛ                       #Begin lambda map
Iȧ                     #Condition for If: is it list?
[                  #Begin If
:L›               #If list - get length and add 1
ÞpŻ            #Get slice of given length from infinite  list of primes
$#Swap vx #Recursively apply to list ¨£e #Zip and reduce pairs with exponentiation | #Else E #If number - two power ] #End If and lambda map, fΠ #Flatten and reduce by product  Try it Online! • 11 Apr 12 at 22:34 • @AndrovT Cool, thanks! You should post your own answer! Or, please explain, how Π works correct without closed ] ? Apr 13 at 3:50 • there's no need to close structures in vyxal Apr 13 at 13:31 # R, 103102 98 bytes Edit: -1 byte, and then -4 more, both thanks to pajonk ?=\(x,p=3)if(sum(!p%%1:p)>2,x?p+1,if(is.list(x),if(length(x),(x[-1]?p+1)*p^?el(x),1),2^x))  Attempt This Online! • You've got an unnecessary newline at the end, I think. Apr 13 at 12:03 • @pajonk - Oh, thanks for spotting that! Apr 13 at 12:05 • Another -1: x[]->el(x) Apr 13 at 12:09 • 98 bytes by renaming the recurrence function to ?. Apr 13 at 12:14 • @pajonk - Thanks again! Apr 13 at 16:09 # JavaScript (ES13), 82 bytes Expects a ragged list of Bigints. Returns a Bigint. f=(a,k=2n,t=1n)=>a.at?a.map(a=v=>(g=d=>k%d--?g(d):d)(k++)?a(v):t*=k**f(v))&&t:k**a  Attempt This Online! Or 79 bytes without Bigints. • So we can use BigInt() in JS just adding n suffix? Apr 11 at 17:43 • @lesobrod Basically yes. :-) Apr 11 at 18:41 # Arturo, 66 bytes f:$[x][(block? x)?[p:3∏map x=>[p^f&until->prime? p->'p+2]]->2^x]


Try it

f:$[x][ ; a function f taking an argument x (block? x)?[ ; is x a block? then... p:3 ; assign 3 to p ∏ ; product map x=>[ ; map over x, assign current elt to & p^f& ; p raised to the Gödel encoding of the current elt until->prime? p-> ; until p is prime... 'p+2 ; add 2 to p via in-place modification ] ; end map ] ; end the 'true' part of the ternary ->2^x ; ...otherwise, if x isn't a block, take 2^x ] ; end function  • Interesting fresh and bright language! Apr 11 at 19:19 # Python, 103 bytes g=lambda n,k=1,m=1:m%k>n or-~g(n,k+1,m*k) f=lambda l,p=3:l*0==0and 2**l or p**f(l)*f(l[1:]or 0,g(p))  Attempt This Online! Method for calculating next prime is shamelessly adapted from Dennis's answer. # PARI/GP, 118 bytes Modified from @Dominic van Essen's answer Golfed version, try it online! G(x,p=3)={if(sum(i=1,p,(p%i)==0)>2,G(x,p+1),if(type(x)=="t_VEC",if(#x,p^G(x)*G(vector(#x-1,i,x[i+1]),p+1),1),2^x))}  Ungolfed version G(x, p = 3) = { if (sum(i = 1, p, (p % i) == 0) > 2, G(x, p + 1), if (type(x) == "t_VEC", if (#x, p^G(x) * G(vector(#x - 1, i, x[i + 1]), p + 1), 1 ), 2^x ) ) } print(G(0)) \\ 1 print(G(1)) \\ 2 print(G([0,0])) \\ 15 print(G([0,1])) \\ 75 print(G()) \\ 3 print(G([])) \\ 27 print(G([0,0,0,0,0])) \\ 15015 print(G([1,2,3])) \\ 32427005625 print(G([[0,1],1])) \\ 15206669692833942727992099815471532675  # 05AB1E, 23 19 bytes o"Ddië®δ.VāØsmP"©.V  Also works for loose integer inputs, instead of just (ragged) lists. Explanation: Recursive functions are always so verbose in 05AB1E.. :/ o # Take 2 to the power each inner-most integer of the (implicit) input "..." # Push the recursive string explained below © # Store it in variable ® .V # Evaluate and execute it as 05AB1E code # (after which the result is output implicitly) D # Duplicate the current list di # If it's a single integer: # (do nothing, simply keep it as is) ë # Else (it's a list instead): δ # Map over each inner item: ® .V # Do a recursive call ā # Then push a list in the range [1,length] (without popping) Ø # Map index each to the 0-based prime: [3,5,7,...] s # Swap the two lists on the stack m # Take the primes to the power of the values P # Take the product of this list  # Charcoal, 67 bytes ≔Ｘ²Ａθ⊞υθＦυＦΦι⁺⟦⟧κ⊞υκＦ⮌υ«≔¹η≔²ζＦι«≦⊕ζＷ¬⬤…²ζ﹪ζμ≦⊕ζ≧×Ｘζ⊟⁺⟦⁰⟧κη»⊞ιη»Ｉ⊟θ  Try it online! Link is to verbose version of code. Explanation: ≔Ｘ²Ａθ  Vectorised raise 2 to the power of the input. ⊞υθＦυＦΦι⁺⟦⟧κ⊞υκＦ⮌υ«  Extract all of the sublists and loop over them in reverse. ≔¹η≔²ζ  Start with a product of 1 and a last prime of 2. Ｆι«  Loop over the elements of the list. ≦⊕ζＷ¬⬤…²ζ﹪ζμ≦⊕ζ  Get the next prime number by trial division (1 byte shorter than Wilson's theorem). ≧×Ｘζ⊟⁺⟦⁰⟧κη»  Multiply the product by the prime power of the next list element (but if that's a list, then use its last element, as that's where we put the value on a previous loop iteration). ⊞ιη  Save the resulting value to the sublist. »Ｉ⊟θ  Output the resulting value of the original list. # Pyth, 23 bytes L?sIb^2b*F^V.fP_Zlb3yMb  Try it online! Defines an encoding function y(b). ### Explanation L # define y(b) ?sIb # if b is invariant under s: (sums for list, int for int) ^2b # 2 ^ b # else: yMb # apply y to each element of b .fP_Zlb3 # generate a list of len(b) primes starting with 3 ^V # vectorized exponentiation *F # fold over multiplication  • woah. great ! respect Apr 12 at 14:35 # Wolfram Language (Mathematica), 37 bytes 1##&@@(i=1;Prime@++i^#&/@#)&//@(2^#)&  Try it online!  (2^#) numbers: x -> 2^x //@ lists: 1##&@@( /@#) product of i=1;Prime@++i^#& prime(n+1)^x_n  # J, 32 30 bytes */@(p:@#\^$:&>)(2^x:)@.(0=L.)


Try it online!

-2 thanks to att

• I think you can p:@#\ 
– att
Apr 17 at 6:53
• Yep, and that change allows me to save another byte too. Apr 18 at 21:49

# Julia, 68 66 bytes

!x::Int=2^x
!(x,p=2)=prod(i->(while(p+=1).%(2:p-1)∋0end;p^!i),x)


Attempt This Online!

-2 bytes by MarcMush.

Doesn't use prime built-ins, which are not in Base anyway. Feels a bit weird to include a type annotation while golfing in a language that doesn't require it, but it looks like a decent way to disambiguate between numbers and lists.

Note that this will only produce correct output within Int64. At the expense of 5 bytes, we can add a big(...) wrapper to get a version that processes all test cases as desired:

## Julia, 73 71 bytes

!x::Int=big(2)^x
!(x,p=2)=prod(i->(while(p+=1).%(2:p-1)∋0end;p^!i),x)


Attempt This Online!

• Kirill L. in fact program could accept single numbers. This is not quite clear point, but you can exclude special detection for numbers Apr 22 at 14:18
• @lesobrod Thanks, I've updated the answer to use the shorter version as the "default" one. Apr 22 at 15:52
• I didn't try it but prod(f,x) might be shorter than prod(x.|>f)? Apr 22 at 23:15
• @MarcMush It works indeed, thanks! Apr 23 at 7:39

# Factor + math.primes.lists math.unicode, 83 bytes

: g ( a -- n ) dup real? [ 2^ ] [ [ lprimes cdr lnth swap g ^ ] map-index Π ] if ;


Try it online!

# PowerShell Core, 147 bytes

$f={$r,$p=1,2$args|%{do{$p++;for($u,$k=1,0;++$u-$p){$k+=!($p%$u)}}while($k)$r=$r*($b=[bigint])::Pow($p,(&($f,{$b::Pow(2,$_)})[$_-is[int]]@_))}$r}


Try it online!

Fun challenge!

Recursive function that expects the input list using splatting and returns a [bigint]

Please ignore the inconsistent output of the array in the tests result as PowerShell has a tendency to flatten them sometime.

## Explanation

This part updates $p to become the next prime after $p

do{$p++;for($u,$k=1,0;++$u-$p){$k+=!($p%$u)}}while($k)  This part checks whether the current list item $_ is a number or not If it is a number, we take its power of two, otherwise, we do a recursive call.

$r=$r*($b=[bigint])::Pow($p,(&($f,{$b::Pow(2,$_)})[$_-is[int]]@_))}


# Wolfram Language (Mathematica), 71 bytes

Of course, answering your own challenge is a bit ridiculous, but it is rather a supplement to not break the main post.
Thanks @PaŭloEbermann for the idea!
It seems we can account for the empty lists, naively but correctly, using the next encoding:

1. If $$\x\$$ is non-negative integer, $$\G(x) = 2^{x+1}\$$
2. If $$\x\$$ is an empty list, [ ], $$\G(x) = 2^0 = 1\$$
3. If $$\x\$$ is a list, $$\[n_0, n_1, n_2, n_3, …], G(x) = 3^{G(n_0)} \cdot 5^{G(n_1)} \cdot 7^{G(n_2)} \cdot 11^{G(n_3)} \cdot...\$$

Of course, this is a purely intuitive idea without proof. But I do not see contradictions at the moment.

So here is Mathematica program that encodes any array-like structure (with possible empty lists) with a unique positive integer.

Switch[#,{},1,{__},Times@@(Prime@Range[2,Length@#+1]^#0/@#),_,2^(#+1)]&


Some related test cases:

[] → 1
[[]] → 3
[[], 1, []] → 13125
[[], [0, []], 1] → 204721573027200065553188323974609375


Try it online!

# PARI/GP, 51 bytes

f(x)=if(x'===0,2^x,prod(i=1,#x,prime(i+1)^f(x[i])))
`

Attempt This Online!