Gödel numbering of a string

Question

Background

Gödel numbers are a way of encoding any string with a unique positive integer, using prime factorisations:

First, each symbol in the alphabet is assigned a predetermined integer code.

Then, to encode a string \$ x_1 x_2 x_3 \ldots x_n \$, where each \$ x_i \$ represents an symbol's integer code, the resultant number is

$$ \prod_{i=1}^n p_i^{x_i} = 2^{x_1} \cdot 3^{x_2} \cdot 5^{x_3} \cdot \ldots \cdot p_n^{x_n} $$

where \$ p_i \$ represents the \$ i \$th prime number. By the fundamental theorem of arithmetic, this is guaranteed to produce a unique representation.

For this challenge, we will only consider strings made of the symbols Gödel originally used for his formulae and use their values, which are:

• 0: 1
• s: 3
• ¬: 5
• ∨: 7
• ∀: 9
• (: 11
• ): 13

...although for simplicity the symbols ¬, ∨, and ∀ can be replaced by the ASCII symbols ~, |, and A respectively.

(I don't know why Gödel used only odd numbers for these, but they're what he assigned so we're sticking with it)

Challenge

Given a string consisting only of the symbols above, output its Gödel encoding as an integer.

You may assume the input will consist only of character in the set 0s~|A().

Example

For the string ~s0:

• start with \$ 1 \$, the multiplicative identity
• the first character ~ has code \$ 5 \$; the 1st prime is \$ 2 \$, so multiply by \$ 2 ^ 5 \$; the running product is \$ 32 \$
• the 2nd character s has code \$ 3 \$; the 2nd prime is \$ 3 \$, so multiply by \$ 3 ^ 3 \$; the running product is \$ 864 \$
• the 3rd character 0 has code \$ 1 \$; the 3rd prime is \$ 5 \$, so multiply by \$ 5 ^ 1 \$; the running product is \$ 4320 \$
• so the final answer is \$ 4320 \$

Test-cases

Input        Output
""           1
"A"          512
"~s0"        4320
"0A0"        196830
")("         1451188224
"sssss0"     160243083000
"~(~0|~s0)"  42214303957706770300186902604046689348928700000
"0s~|A()"    5816705571109335207673649552794052292778133868750

Rules

• Your program does not have to work for strings that would produce larger integers than your programming language can handle, but it must work in theory
• You can accept input as a string, list of characters, or list of code-points
• You may use any reasonable I/O method
• Standard loopholes are forbidden
• This is code-golf, so the shortest code in bytes wins

Answer 1

JavaScript (ES7),  75  72 bytes

Expects an array of ASCII codes.

a=>a.map(g=k=>--d-1?g(k,d=n%d?d:++n):p*=n**(17088/k%75%14|1),d=p=n=1)&&p

Try it online!

Magic formula

The formula 17088/k%75%14|1 was found by injecting random values into several handcrafted templates.

More specifically, the template for this one was `${p}/k%${m0}%${m1}|1` with \$0<p<10^5\$, \$0<m_0<10^3\$ and \$12\le m_1 \le 15\$.

 char. |  k  | floor(17088 / k) | mod 75 | mod 14 | OR 1
-------+-----+------------------+--------+--------+------
  '('  |  40 |        427       |   52   |   10   |  11
  ')'  |  41 |        416       |   41   |   13   |  13
  '0'  |  48 |        356       |   56   |    0   |   1
  'A'  |  65 |        262       |   37   |    9   |   9
  's'  | 115 |        148       |   73   |    3   |   3
  '|'  | 124 |        137       |   62   |    6   |   7
  '~'  | 126 |        135       |   60   |    4   |   5

Commented

a =>                // a[] = input
a.map(g = k =>      // for each ASCII code k in a[]:
  --d - 1 ?         //   decrement d; if d is not equal to 1:
    g(              //     do a recursive call to the callback function:
      k,            //       pass k unchanged
      d =           //       update d:
        n % d ? d   //         if d is not a divisor of n, leave d unchanged
              : ++n //         otherwise, increment n and set d = n
    )               //     end of recursive call
  :                 //   else (n is now the next prime):
    p *=            //     multiply p by
      n ** (        //     n raised to the power of
        17088 / k   //     the odd positive integer <= 13 which is obtained
        % 75 % 14   //     by applying our magic formula to k
        | 1         //
      ),            //
  d = p = n = 1     //   start with d = p = n = 1
) && p              // end of map(); return p

Answer 2

Jelly,  13  11 bytes

-2 thanks to Nick Kennedy! (I had a bug in my Python search code so failed to find the hash for a domain of [1..7].)

⁽=ȧ,7ḥⱮḤ’ÆẸ

A monadic Link accepting a list of characters that yields the Gödel number.

Try it online!

How?

⁽=ȧ,7ḥⱮḤ’ÆẸ - Link: list of characters, S
⁽=ȧ         - 16481
    7       - 7
   ,        - literal pair -> [16481, 7]
      Ɱ     - map across (c in S) with:
     ḥ      -   (c) hash (salt=16481, domain=[1..7])
       Ḥ    - double
        ’   - decrement
         ÆẸ - prime-index-exponentiate ([a,b,c,...]->2^a*3^b*5^c*...)

Answer 3

05AB1E, 16 15 bytes

"0s~|A()"sk·>.Ó

Try it online! Link includes test suite. Takes input as a list of characters (test suite expects a list of lists) saving 1 byte thanks to @ovs. Explanation:

"0s~|A()"       Literal string of symbols
         s      Swap with implicit input
          k·>   Get the incremented doubled indices
             .Ó Decode as list of prime exponents

Previous version took input as a string, which is easier to use: Try it online!

Answer 4

Husk, 21 20 19 bytes

• Saved 1 byte thanks to caird coinheringaahing
• Saved 1 byte thanks to Dominic Van Essen

Πz`^İpmȯ←D€"0s~|A()

Try it online!

Πz`^İpmȯ←D€"0s~|A()
      m             For each character in the input
          €"0s~|A() Find its index in the string "0s~|A()"
         D          Double
        ←           and decrement to get the corresponding code
 z                  Zip this with
    İp              the list of prime numbers
  `^                by raising the prime numbers to the powers of the codes
Π                   Get the product of that            

Answer 5

Python 2, 89 bytes

Takes input as a list of characters.

s=input()
P=k=r=1
while s:r*=P%k<1or k**(3+2*'s~|A()'.find(s.pop(0)));P*=k*k;k+=1
print r

Try it online!

Answer 6

AWK, 109 102 bytes

-7 bytes; thank you, @ovs!

Pretty naïve.

a=1{for(p=2;i++<length;)for(a*=p++**(index("0s~|A()",substr($0,i,1))*(j=2)-1);j<p;)p%j++||p++<j=2}$0=a

Try it online!

Ungolfed

{
# accumulator and currently seeing prime number
a=1;p=2;
for(i=1;i<=length($0);i++){
   # multiply p_i^(x_i)
   a*=p**(index("0s~|A()",substr($0,i,1))*2-1);
   # get next prime
   p++;
   for(j=2;j<p;)
      if(p%j!=0)
         j++;
      else{
         p++;j=2;}}
# finally
$0=a

Answer 7

Japt, 26 24 23 bytes

Ew! Don't think I've ever been more jealous of languages with built-ins for lists of primes and exponents and what-not :\

Input is an array of codepoints. Saved a byte by borrowing Arnauld's formula.

£_j}iY p#ª88÷X%75%E|1Ã×

Try it

£_j}iY p#ª88÷X%75%E|1Ã×     :Implicit input of codepoint array
£                           :Map each X at index Y
 _                          :  Function taking an integer as argument
  j                         :    Is prime?
   }                        :  End function
    iY                      :  Get the Yth integer that returns true
       p                    :  Raise to the power of
        #ª88                :    17088
            ÷X              :    Divide by X
              %75           :    Mod 75
                 %E         :    Mod 14
                   |1       :    Bitwise OR with 1
                     Ã      :End map
                      ×     :Reduce by multiplication

Answer 8

Japt, 24 bytes

Japt is fairly verbose when it comes to primes, taking 6 bytes to get the Nth prime. Takes input as an array of letters.

£Èj}iY p"0s~|A()"aX ÑÄÃ×
£                        // Map the input with X as values, Y as indexes.
 Èj}iY                   // Get the Y-th prime
       p         aX      // to the power of the index of X in
        "0s~|A()"        // string constant,
                    ÑÄ   // times two plus one to map to correct values.
                      Ã× // Finally, reduce with multiplication, return result.

Try it here.

Answer 9

Mathematica, 120 106 102 99 bytes

-14 bytes, thank you pxeger!

1##&@@(Prime[Range@Length@#]^#&@((Tr@StringPosition["0s~|A()",#]*2-1)&/@Characters@InputString[]))

First golfing, and would welcome feedback!

Answer 10

J, 28 bytes

[:*/p:@i.@#^1+2*'0s~|A()'&i.

Try it online!

Answer 11

Factor + math.primes math.unicode, 64 bytes

[ dup length nprimes swap [ "0s~|A()"index 2 * 1 + ] map v^ Π ]

Try it online!

Explanation:

It's a quotation (anonymous function) that takes a string from the data stack as input and leaves an integer on the data stack as output. Assuming "~s0" is on the data stack when this quotation is called...

• dup Duplicate the object on top of the data stack (TOS).

  Stack: "~s0" "~s0"

• length Take the length of a sequence.

  Stack: "~s0" 3

• nprimes Obtain a list of the first number of primes indicated by TOS.

  Stack: "~s0" { 2 3 5 }

• swap Swap the top two objects on the data stack.

  Stack: { 2 3 5 } "~s0"

• [ "0s~|A()"index 2 * 1 + ] Push a quotation for map to use later. This is a function that maps letters of our alphabet to numeric values.

  Stack: { 2 3 5 } "~s0" [ "0s~|A()"index 2 * 1 + ]

• map Apply a quotation to each element of a sequence, collecting the results into a sequence of the same length. Inside the quotation now during the first iteration...

  Stack: { 2 3 5 } 126

• "0s~|A()" Push our alphabet string to the stack.

  Stack: { 2 3 5 } 126 "0s~|A()"

• index Find the index of NOS (next on stack) in TOS.

  Stack: { 2 3 5 } 2

• 2 * 1 + Multiply by 2, then add 1.

  Stack: { 2 3 5 } 5

• Now map will collect 5 into the sequence it's building and move on to the rest of the elements in our input string...

  Stack { 2 3 5 } "\x05\x03\x01"

• As a side note, strings in Factor are just arrays of code points. Often when we map over a string, we'll get a string result, but we can still do vector math and such with them. This string is equivalent to { 5 3 1 }.

• v^ Component-wise exponentiation.

  Stack: { 32 27 5 }

• Π Product.

  Stack: 4320

Answer 12

R, 98 97 bytes

Edit: -1 byte thanks to pajonk

function(x,p=1){for(y in x){while(sum(!(T=T+1)%%2:T)>1)1;p=p*T^(regexpr(y,"0s~|A()",f=T)*2-1)};p}

Try it online!

Input is a vector of characters.

goedel_numbering=
function(x){                            # x is the input character vector;
p=1                                     # initialize p to 1 (one less than the first prime);
for(y in x){                            # now cycle through each character y in x:
  while(sum(!(p=p+1)%%2:p)>1)1          # update p to the next prime
  T=T*                                  # multiply T (initially 1) by
      p^                                # p to the power of
        (regexpr(y,"0s~|A()",f=T)       # the position of y in the string "0s~|A()"
                                 *2-1)  # times 2, minus 1;
  }
  +T                                    # finally, output T.
}

Answer 13

MATLAB/Octave, 102 97 bytes

@(x)prod(table(primes(intmax)).Var1(1:nnz(x)).^int32(2*arrayfun(@(y)find('0s~|A()'==y),x)-1),'n')

Try it on Octave Online!* - TIO has some problems with function and execution exceeds 60 seconds and is terminated.
Anonymous function. In theory could work forever but maxes out at int32 limit.
Explaination:

% anonymous function - take product of first argument...
@(x)prod(



      primes(intmax)                % all prime numbers < than limit of int32
table(              ).Var1(        )% take elements of array
                           1:nnz(x) % vector 1 to length of input



.^           % element-wise power



int32(                                      )% casting to int32
        arrayfun(                      ,x)   % for each character in input
                 @(y)find('0s~|A()'==y)      % find index in '0s~|A()'
      2*                                  -1 % indices to symbol values



,'n') % shorthand 'native', return product of elements in same type as input

---

Alternative solution as full function, 103 bytes long.

function r=g(x)
p=primes(intmax);r=int64(1);for n=1:nnz(x)
r=r*p(n)^(2*find('0s~|A()'==x(n))-1);end
end

Try it online!*
This one on the other hand maxes out at int64 limit.
Ungolfed:

function result = g(x)
primeNumbers = primes(intmax);
result = int64(1);
for n=1:length(x)
    result = result * primeNumbers(n) ^ (2*find('0s~|A()'==x(n))-1);
end
end

---

It is possible to write a function that doesn't max out (...so easily) but it outputs symbolic numbers instead of integers (and has 105 bytes). Very similar to first function:

@(x)prod(sym(table(primes(intmax)).Var1(1:nnz(x))).^sym(2*arrayfun(@(y)find('0s~|A()'==y),x)-1),'native')

---

*it is adviced for testing to replace primes(intmax) with something like primes(intmax/128) to calculate fewer prime numbers and thus reduce the execution time (and it was done for TIO example). The result will max out much faster than you'll use up all prime numbers, so no worries about that.

Answer 14

05AB1E, 19 bytes

εNØ"0s~|A()"yk·>m}P

Try it online!

Answer 15

JavaScript (Node.js), 81 bytes

s=>s.map(c=>q*=(g=v=>p%v--?g(v):v?g(p++):p*p)``**'0s~|A()'.indexOf(c)*p,q=p=1)&&q

Try it online!

Input as array of characters, output a number.

Saved 1 byte by Shaggy.

---

JavaScript (Node.js), 79 bytes

s=>s.map(c=>q*=(g=v=>p%v--?g(v):v?g(p++):p*p)``**'056 3421'[c%30%9]*p,q=p=1)&&q

Try it online!

Input an array of codepoints, output a number.

Saved 1 byte by Shaggy.

I believe someone may find out better hash functions.

Answer 16

JavaScript (Node.js), 103... 94 bytes

n=>n.map(g=b=>(eval("for(j=++i;i%--j;);"),j)<2?l*=i*(i*i)**'0s~|A()'.indexOf(b):g(b),i=l=1)&&l

Try it online!

Takes input as an array of characters. A naïve implementation.

How it works

For each character, multiplies counter l by the exponential expression if incremented i is prime. If not, recall g until we get a prime number. Then logical-ANDs (short-circuit) with l.

Answer 17

Pyth, 28 bytes

*F.b^Nhyx"0s~|A()"Y.fP_ZlQ)Q

Test suite

Naïve solution. Will attempt to find another solution... eventually.

Answer 18

[PHP], 175 bytes

My first try here, so obviously this will suck…

<?php $G="0s~∨A()";$p=[0,2,3,5,7,11,13,17,19,23,29,31,37,41];$i="~s0";$t=1;for($k=0;$k<strlen($i);$k++){$r=strpos($G,$i[$k]);$r2=$r*2+1;$m=pow($p[$k+1],$r2);$t*=$m;}echo $t;?>

I couldn’t think of a formula to generate primes, so I entered them all in an array. One can obviously do better. Also, my server doesn’t accept just <? as PHP marker, so I’m stuck with <?php.

Answer 19

C (gcc), ^{116 110} 106 bytes

Saved 3 bytes thanks to the man himself Arnauld!!!
Saved 4 bytes thanks to ceilingcat!!!

d;g;p;r;f(char*s){for(p=r=1;*s;r*=pow(p,17088/ *s++%75%14|1))for(g=0;!g;)for(g=d=p++;d>1;)g=g&&p%d--;d=r;}

Try it online!

Inputs a string and returns its Gödel number.

Uses the Magic ASCII to Gödel value mapping formula from Arnauld's JavaScript answer.

Commented Code (before some golfs)

d;g;p;r;f(char*s){                 // declare variables and function  
        r=1                        // init return value r to 1      
      p=                           // init prime number p to 1    
  for(     ;*s;++s){               // loop over chars in s  
    for(g=0;!g;)                   // loop until we find the next prime  
              p++                  // start by bumping p  
            d=                     // init divisor d to p-1  
          g=                       // set g to non-zero p-1 as well  
      for(       ;d>1;)            // loop over d until its 2
        g=g&&p%d--;                // g with only remain non-zero if  
                                   // p is the next prime number 
    r*=pow(p,                 );   // multiply r by p to the power of
             17088/ *s%75%14|1     // the Gödel value for the ASCII  
                                   // code, need the space so it's not 
  }                                // interpreted as start of comment    
  d=r;                             // return r
}                                  //

Answer 20

Python 3, 190 bytes

def f(x):
    P,p=[2],3
    while len(P)<len(x):
        P.append(p)
        while 1:
            p+=1
            for i in P:
                if p%i==0:break
            else:break
    i=1
    for d,n in zip(x,P):i*=n**(2*"0s~|A()".find(d)+1)
    return i

Try it online! Generates enough primes to form the Gödel number, then finds the product.

Answer 21

Haskell, 95 bytes

e=(product.zipWith(^)[p|p<-[2..],all((>0).mod p)[2..p-1]]<$>).mapM(`lookup`zip"0s~|A()"[1,3..])

Try it online!