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

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

Answer 2

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

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!

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!

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.

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

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

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 10

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.

Answer 11

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

Answer 12

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 13

J, ³² 30 bytes

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

Try it online!

-2 thanks to att

Answer 14

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!

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!