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

• user100690: Could we take input as an array of characters?
• pxeger: @ophact Yep, that's fine. I'll edit it in
• Silvio Mayolo: 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).
• Kaz: Code Gölf is on, mofos!

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!

• ovs: 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.
• Neil: @ovs But how do I tell TIO to provide input as a list of characters?
• pxeger: Just change the input to be in Python list syntax: Try it online!
• ovs: 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.
• Neil: @ovs Ugh, well if I'm going to do that then I guess I might as well set up a test suite...

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 

• caird coinheringaahing: 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.
• user: @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
• Dominic van Essen: Save 1 byte by changing !İ1 to ←D (double and subtract 1).

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!

• dingledooper: 83 bytes with a magic formula.

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

• ovs: I think j<=sqrt(p) can be shortened to j<p.

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#a×ばつ

Try it

£_j}iY p#a×ばつ :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
 #a88 : 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!

• pxeger: 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

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

• pajonk: -1 byte by swapping roles of p and T.
• Dominic van Essen: @pajonk - Ah, yes, thanks very much!

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.

• Shaggy: You can save a byte on the initial call to g by using backticks instead of (0).

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.

• rydwolf: Welcome to Code Golf! Nice first answer.
• pxeger: 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.
• Pierre Paquette: Thank you, pxeger; I have a lot yet to learn! ;-)

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
} //

• Arnauld: 110 bytes with my updated formula.
• Noodle9: @Arnauld It just gets more and more magical - thanks! :D
• Noodle9: @ceilingcat Nice one - thanks! :D

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.

• pxeger: Welcome to Code Golf, and nice first answer! Be sure to check out our Tips for golfing in Python page for ways you can golf your program!

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!