18
\$\begingroup\$

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 , so the shortest code in bytes wins
\$\endgroup\$
4
  • \$\begingroup\$ Could we take input as an array of characters? \$\endgroup\$
    – user100690
    May 26 at 9:15
  • 1
    \$\begingroup\$ @ophact Yep, that's fine. I'll edit it in \$\endgroup\$
    – pxeger
    May 26 at 9:24
  • 4
    \$\begingroup\$ For what it's worth, Godel used odd numbers for the symbols for disambiguation. The only odd numbers are individual symbols, whereas all strings have a positive power of two in them, hence are even. Thus, we can always tell the difference between a symbol (s is 3, for instance) and a string which happens to contain only one symbol ("s" as a string is 8). \$\endgroup\$ May 27 at 16:53
  • \$\begingroup\$ Code Gölf is on, mofos! \$\endgroup\$
    – Kaz
    May 29 at 1:09

20 Answers 20

17
\$\begingroup\$

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
\$\endgroup\$
10
\$\begingroup\$

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*...)
\$\endgroup\$
0
6
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ I didn't know about , very nice! Apparently it is only documented in info.txt, but not in the wiki. Taking input as a list of characters is allowed, this would simplify to I. \$\endgroup\$
    – ovs
    May 26 at 10:24
  • \$\begingroup\$ @ovs But how do I tell TIO to provide input as a list of characters? \$\endgroup\$
    – Neil
    May 26 at 10:33
  • \$\begingroup\$ Just change the input to be in Python list syntax: Try it online! \$\endgroup\$
    – pxeger
    May 26 at 10:35
  • \$\begingroup\$ If the input can be parsed as a list, 05AB1E will do it. Note that you need to use double quotes, strings in single quotes get read as codepoint lists. \$\endgroup\$
    – ovs
    May 26 at 10:36
  • \$\begingroup\$ @ovs Ugh, well if I'm going to do that then I guess I might as well set up a test suite... \$\endgroup\$
    – Neil
    May 26 at 10:46
5
\$\begingroup\$

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            
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Golf, and nice first answer! You can remove the trailing " for -1 byte. Be sure to check out our Tips for golfing in Husk page for ways you can golf your program. \$\endgroup\$ May 26 at 23:07
  • 1
    \$\begingroup\$ @cairdcoinheringaahing Thanks for the tip! I'm user (a sockpuppet) btw. This account was mostly so I could pretend to have come from the future in chat :P \$\endgroup\$
    – user
    May 26 at 23:08
  • \$\begingroup\$ Save 1 byte by changing !İ1 to ←D (double and subtract 1). \$\endgroup\$ May 27 at 10:13
4
\$\begingroup\$

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!

\$\endgroup\$
1
4
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think j<=sqrt(p) can be shortened to j<p. \$\endgroup\$
    – ovs
    May 26 at 11:00
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

J, 28 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.
}
\$\endgroup\$
2
  • \$\begingroup\$ -1 byte by swapping roles of p and T. \$\endgroup\$
    – pajonk
    May 28 at 19:16
  • \$\begingroup\$ @pajonk - Ah, yes, thanks very much! \$\endgroup\$ May 28 at 19:40
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 19 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can save a byte on the initial call to g by using backticks instead of (0). \$\endgroup\$
    – Shaggy
    May 26 at 11:43
1
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

Pyth, 28 bytes

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

Test suite

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf! and nice first post! Make sure you check out our Tips for golfing in Mathematica page. In particular, I think you might be able to shorten the lookup of the character to its value using some ideas in the other answers, by finding the index of the character in the string 0s~|A() and using a bit of maths to get the right value from 1-13 \$\endgroup\$
    – pxeger
    May 27 at 12:32
1
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Golf! Nice first answer. \$\endgroup\$ May 28 at 0:24
  • 1
    \$\begingroup\$ This isn't a valid answer, I'm afraid - it won't work for arbitrarily long strings because you've only hardcoded 14 primes. Also, taking input from a predefined variable name (here $i) is not considered a valid input method on this site. You may also want to check out the Tips for golfing in PHP page for ways you can golf your program. \$\endgroup\$
    – pxeger
    May 28 at 7:17
  • \$\begingroup\$ Thank you, pxeger; I have a lot yet to learn! ;-) \$\endgroup\$ May 29 at 3:54
1
\$\begingroup\$

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
}                                  //
\$\endgroup\$
3
  • \$\begingroup\$ 110 bytes with my updated formula. \$\endgroup\$
    – Arnauld
    May 26 at 14:14
  • \$\begingroup\$ @Arnauld It just gets more and more magical - thanks! :D \$\endgroup\$
    – Noodle9
    May 26 at 14:16
  • \$\begingroup\$ @ceilingcat Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    May 28 at 9:05
1
\$\begingroup\$

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.

\$\endgroup\$
1

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.