Gödel encoding - Part I

Question

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:

[0] → 3

[[0]] → \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

Task

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
[[1], [1]] → 38443359375
[0, [[0]], 0] → 156462192535400390625
[[[0], 0], 0] → 128925668357571406980580744739545891609191243761536322527975268535

• Paŭlo Ebermann: Wouldn't an empty list just be encoded as 1? Ah, that would be the same as the encoding of the number 0.
• Stef: I upvoted just for "the Gödel"
• Jane: @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 ^^
• lesobrod: @PaŭloEbermann Thank you for interesting idea, I made some updates
• David Conrad: @WilliamMartens Yes, Kurt Gödel's relationship to this question is that he came up with Gödel encoding.

Answer 1

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 [0])
 ÆẸ - recompose from prime exponent list
 e.g.:
 [0,4,0,2] -> 3^4 ×ばつ 7^2 = 3969
 [0] -> 2^0 = 1
 n -> 2^n (non-list n treated as [n])

• Unrelated String: 8 with ð
• Jonathan Allan: Pesky ` :) thanks @UnrelatedString

Answer 2

Brachylog, 24 bytes

;2^(|↰mGl~l×ばつ

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)
 ↰mG 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
 N3mṗm≠≜ It must be a list of primes greater than 3 and all different (it always unifies with increasing magnitudes)
 ;Gz Zip with G
 ^m Map power
 ×ばつ Multiply

Answer 3

Vyxal, A (削除) 23 (削除ここまで) (削除) 21 (削除ここまで) 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!

• AndrovT: 11
• lesobrod: @AndrovT Cool, thanks! You should post your own answer! Or, please explain, how Π works correct without closed ] ?
• AndrovT: there's no need to close structures in vyxal

Answer 4

R, (削除) 103 (削除ここまで) (削除) 102 (削除ここまで) 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!

• pajonk: You've got an unnecessary newline at the end, I think.
• Dominic van Essen: @pajonk - Oh, thanks for spotting that!
• pajonk: Another -1: x[[1]]->el(x)
• pajonk: 98 bytes by renaming the recurrence function to ?.
• Dominic van Essen: @pajonk - Thanks again!

Answer 5

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.

• lesobrod: So we can use BigInt() in JS just adding n suffix?
• Arnauld: @lesobrod Basically yes. :-)

Answer 6

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

• lesobrod: Interesting fresh and bright language!

Answer 7

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[0])*f(l[1:]or 0,g(p))

Attempt This Online!

Method for calculating next prime is shamelessly adapted from Dennis's answer.

Answer 8

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[1])*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[1]) * 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([0])) \\ 3
print(G([[0]])) \\ 27
print(G([0,0,0,0,0])) \\ 15015
print(G([1,2,3])) \\ 32427005625
print(G([[0,1],1])) \\ 15206669692833942727992099815471532675

Answer 9

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!

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

Answer 10

05AB1E, (削除) 23 (削除ここまで) 19 bytes

o"Ddië®δ.VāØsmP"©.V

Also works for loose integer inputs, instead of just (ragged) lists.

Try it online or verify all test cases.

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

Answer 11

Charcoal, 67 bytes

×ばつXζ⊟+⟦0⟧κη»⊞ιη»I⊟θ

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

≔X2Aθ

Vectorised raise 2 to the power of the input.

⊞υθFυFΦι+⟦⟧κ⊞υκF⮌υ«

Extract all of the sublists and loop over them in reverse.

≔1η≔2ζ

Start with a product of 1 and a last prime of 2.

Fι«

Loop over the elements of the list.

≦⊕ζW¬⬤...2ζ%ζμ≦⊕ζ

Get the next prime number by trial division (1 byte shorter than Wilson's theorem).

×ばつXζ⊟+⟦0⟧κη»

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.

»I⊟θ

Output the resulting value of the original list.

Answer 12

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

• Jane: woah. great ! respect

Answer 13

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

Answer 14

J, ³² 30 bytes

*/@(p:@#\^$:&>)`(2^x:)@.(0=L.)

Try it online!

-2 thanks to att

• att: I think you can p:@#\
• Jonah: Yep, and that change allows me to save another byte too.

Answer 15

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!

Answer 16

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]]@_))}

Answer 17

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!

Answer 18

PARI/GP, 51 bytes

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

Attempt This Online!