# Gödel encoding - Part II (decoding)

Part I

Previous part was considered encoding of non-empty nested lists with a positive integer.

Reminding the coding procedure $$\G(x)\$$:

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.

The number will be unique (it can be proved, but you don’t have to do it). So always there is valid reverse procedure: determine an array-structure from a given number, or verify that no structure exists for that number. This is the task of this challenge.

### Input

Positive integer (possibly very large)
UPD
I know that in CG does not approve strict validation of input.
But here invalid in general number means: negative, float, with typo etc.
You don’t have to check it out!
But figuring out if a number is valid encoding or not is part of the challenge.

### Output UPD

Very sorry I missed the important thing ((
Single number (if it is suitable for the first part of the procedure, see test cases)
or
non-empty list of non-negative integers (possibly nested, without empty sub-lists) that is encoded with given number; printed in any appropriate form: as pure array, string, json etc.
OR
any appropriate message ([ ], None, -1 etc), if there is no decoding for this number.

### Test cases

1 → 0
2 → 1
3 → [0]
4 → 2
5 → None
6 → None
7 → None
8 → 3
9 → [1]
10 → None
666 → None
729 → None
1024 → 10
1215 → None
3375 → [[0], [0]]
77777 → None
5859375 → [0, [1]]
666777666 → None
2210236875 → [3, 2, 1, 0]
7625597484987 → [[[0]]]
1111111111111111111111111111 → None

• Suggested test cases: 729, 1215. I think they're both invalid. Commented Apr 17, 2023 at 10:03
• Can malformed-but-varied outputs be given for malformed inputs, like a nested structure containing -1 where the encoding is immediately malformed? (I assume not, but it's worth clarifying.) Commented Apr 17, 2023 at 10:53
• @UnrelatedString, I also think not; if number is not valid, there is no any corresponding structure for it, so output should be just a message. I think even empty array is not good Commented Apr 17, 2023 at 12:24
• Since you've described the output as a non-empty list of non-negative integers (possibly nested [...]), I've assumed that something like 8 is an invalid input, although it could be also decoded to 3, as assumed by @DominicvanEssen. Could you please clarify? Commented Apr 18, 2023 at 20:08
• Arnauld, I’m very sorry I wasn’t paying attention (( According to the book, single number is valid structure. Post is updated! The point is that we can code single number in many different ways, and for lists we need a special way. But it can also be used for numbers. Commented Apr 19, 2023 at 4:36

# JavaScript (ES6), 167 bytes

Expects a Bigint. Returns -1 if the encoding is invalid.

This is probably longer than it should, but validating the encoding is costly (see below).

n=>(e=h=(n,F=n>1&&n%2n?(n,k=3n,i=0n)=>n%k?i?[h(i),...k>n?[]:F(n,-~k)]:(g=d=>k%--d?g(d):e|=d<2)(k)?[]:F(n,-~k):F(n/k,k,-~i):n=>n%2n?e|=n>1:-~F(n/2n))=>o=F(n))(n)&&-e||o


Try it online!

### 111 bytes (for information only)

A large part of the code is dedicated to Gödel encoding validation. If we assume that the input is a valid encoding, then several sanity checks can be removed and we don't even have to include a primality test:

f=(n,F=n>1&&n%2n?(n,k=3n,i=0n)=>n%k?[...i?[f(i)]:[],...k>n?[]:F(n,-~k)]:F(n/k,k,-~i):n=>n%2n?0:-~F(n/2n))=>F(n)


Try it online!

• Arnauld, Thanks for ideas about validation, post a bit updated Commented Apr 17, 2023 at 16:22
• I think the output for '8' should be '3'... Commented Apr 18, 2023 at 19:46
• @DominicvanEssen Making sure that the top level structure is a list was actually costing me some extra bytes. Now updated according to the new rules. Commented Apr 19, 2023 at 7:12

# R, 168149132117 116 bytes

Edits: -9 and -1 bytes thanks to pajonk (re-defining if as [, now no longer needed, and then function as ~), -7 bytes by switching to \ instead of function, and -35 more bytes by re-arranging.

~=\(x,p=2,y=0)if(!x%%p,~(x/p,p,y+1),if(p==2&x<2,y,c(if(sum(!p%%1:p)<3&p>2|y)list(~y[!y|p>2]),if(x>1)x~p+1)))


Attempt This Online!

Outputs the number or list whose Gödel encoding is the input. Errors if no such number/list exists.

Ungolfed code:

D=function(x,p=2,y=0){
if(!x%%p)D(x/p,p,y+1) else
if(p==2&x<2)y else
c(if(is_prime(p)&p>2|y)list(D(y*(!y|p>2))),if(x>1)D(x,p+1))
}
is_prime=function(x)sum(!x%%1:x)<3

• With so may ifs first thing for me was to try assigning if to [. Looks like it does save some bytes indeed, even with all those extra (). Commented Apr 17, 2023 at 18:32
• @pajonk - Yes, thanks. I had a feeling that that might work, but didn't do it because I suspected (and still do...) that the enormous number of ifs might indicate that the code isn't very optimal, and could be more-elegantly written... but so far I haven't figured-out how... So [ it is! Commented Apr 18, 2023 at 8:23
• @pajonk - I finally got rid of enough if-elses that the [ substitution only breaks-even... Commented Apr 18, 2023 at 13:45
• Great news, well done! Commented Apr 18, 2023 at 16:29
• Also, -1 byte with another weird substitution. Commented Apr 18, 2023 at 16:36

# Vyxal, 20 bytes

λ1>[∆Ǐḣvx₌∨∧ßu›:A∧]‹


Try it Online!

Returns -1 for invalid inputs. Times out on the last test case.

# PARI/GP, 101 bytes

n->iferr(g(n),e,x)


Attempt This Online!

Returns x for invalid inputs.

# Jelly, 17 bytes

ȯ6ÆEsß€Ḣ?ḢḊ?0
ÇŒṘ


A full-program that accepts a positive integer and either:

• prints the decoded value and exits with a code of 0; or
• prints nothing to STDOUT and exits with a code of 1 (printing a traceback to STDERR).

Try it online! Or see the test-suite (in Zsh to catch the exit code).

### How?

ȯ6ÆEsß€Ḣ?ḢḊ?0 - Helper Link: positive integer, N
ȯ6            - logical OR with 6 (when N=0 use 6 - this is so that recursive calls
handle zeros in the ÆE result in a way that will
produce the error we want)
ÆE          - prime factorisation list (e.g. 56=2*2*2*7 -> [3,0,0,1])
?  - if...
Ḋ   - ...condition: dequeue (i.e. is of length 2 or more)
?     - ...then: if...
Ḣ      -          ...condition: remove and yield the head (exponent of 2)
s       0 -          ...then (i.e. non-zero): split into chunks of length zero
(this will error out)
€       -          ...else: for each (of the rest of the exponents):
ß        -                     call this Link with that number
Ḣ    - ...else: head (i.e. yield the power of two that N is)

ÇŒṘ - Main Link: positive integer, N
Ç   - call the helper Link, above
ŒṘ - print a Python representation of the result

• @lesobrod : this is 17 UTF-8 chars but 32 bytes. Jelly requires python as a back-end interpreter instead of being standalone, so unless someone can prove they have already ported python to the single byte custom code page, it needs to be counted in UTF-8 instead. If I follow the code page's mapping and send in byte 0xC1 :: \301 for Ḋ instead of 0x E1 0x B8 0x 8A :: \341\270\212 (utf8), perhaps I'm missing something, but from everything I've seen in the interpreter's source code …... Commented Oct 27, 2023 at 13:37
• @lesobrod : …….. it lacks the capability to decode UTF-8 invalid bytes like 0xC1, thus further weakening its claim it's cross-compatible w/ both UTF-8 and its custom code page. Commented Oct 27, 2023 at 13:37
• @RAREKpopManifesto The hex bytecode f1 36 0d 45 73 15 0c c5 3f c5 c1 3f 30 7f 0e 13 cc is the actual program and may be run with the f flag. See the readme, the code, and the codepage. Commented Oct 27, 2023 at 17:57
• codepage only means jack when the underlying interpreter is also running in the same environment. please show proof you have ported python to execute directly over this codepage instead of in emulation mode over UTF-8, esp since the custom codepage has also remapped 0x0A from \n in ASCII/UTF-8 to ½ Commented Oct 30, 2023 at 2:17
• @RAREKpopManifesto I am unsure what you are asserting, is there a meta consensus you can point me to that covers this? If not then maybe you should post there for people in the community that may understand you better so things can be decided. (I do not know when an interpreter wouldn't be "running in the same environment" as the program. Also, Jelly is not mine, I have contributed to it but really I just write code :p). Commented Oct 30, 2023 at 12:01

# Charcoal, 100 bytes

⊞υ⟦Ｘ³Ｎ⟧Ｆυ«≔⊟ιθ¿﹪θ²«≔²η≔⟦⟧ζＷ⊖θ¿﹪θη«≦⊕η¿⬤…²η﹪ηλ⊞ζ⁰»«⊞ζ⊕⊟ζ≧÷ηθ»Ｆζ¿∧κ¬＆⊖κκ⊞ι⊖Ｌ↨κ²«≔⟦κ⟧κ⊞ικ⊞υκ»»⊟ι»⭆¹⊟§υ⁰


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

⊞υ⟦Ｘ³Ｎ⟧


The main loop only works on lists of odd numbers, so fake it out by starting with a list of 3ⁿ.

Ｆυ«


Loop over the input and any sublists that may be generated while processing it.

≔⊟ιθ


Get the value to turn into a list.

¿﹪θ²«


If it's odd, then:

≔²η≔⟦⟧ζ


Start finding prime factor multiplicities.

Ｗ⊖θ


Repeat until the all the factors have been found.

¿﹪θη«


If the current prime is not a factor, then:

≦⊕η


Try the next integer.

¿⬤…²η﹪ηλ


If this is a prime, then...

⊞ζ⁰


... start counting its multiplicity.

»«


Otherwise:

⊞ζ⊕⊟ζ


Increment the multiplicity.

≧÷ηθ


Divide the value by the prime.

»Ｆζ


Loop over the multiplicities.

¿∧κ¬＆⊖κκ


If this is a power of 2, then...

⊞ι⊖Ｌ↨κ²«


... push its logarithm to the list, otherwise:

≔⟦κ⟧κ⊞ικ⊞υκ


... push the wrapped value to both the list and also the list of sublists to be processed.

»»⊟ι


Otherwise, crash the program, because the input is invalid.

»⭆¹⊟§υ⁰


Output the final value.

Since the above program has to find the logarithm to base 3 of 3ⁿ the slow way, here's a slightly less slow 112 byte version which special-cases inputs of powers of 2 to avoid this:

Ｎθ¿＆θ⊖θ«⊞υ⟦θ⟧Ｆυ«≔⊟ιθ¿﹪θ²«≔²η≔⟦⟧ζＷ⊖θ¿﹪θη«≦⊕η¿⬤…²η﹪ηλ⊞ζ⁰»«⊞ζ⊕⊟ζ≧÷ηθ»Ｆζ¿∧κ¬＆⊖κκ⊞ι⊖Ｌ↨κ²«≔⟦κ⟧κ⊞ικ⊞υκ»»⊟ι»⭆¹§υ⁰»Ｉ⊖Ｌ↨θ²


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

# Pyth, 32 bytes

L?sIlbslbCWneJCr8Pb.fP_ZleJ3yMhJ


Try it online!

Defines a decoding function y(b) which returns the decoded list or throws a TypeError if the input is invalid.

### Explanation

L                                   # define y(b)
?                                  # if
lb                              # log base 2 of b
sI                                # is an integer:
slb                           #   return int(log(b))
# otherwise
J                      # assign J to
Pb                 #   the list of prime factors of b
r8                   #   length encoded
C                     #   and transposed
W                         # if
eJ                      # the last element of J
n                        # is not equal to
.fP_ZleJ3        # the first length(eJ) primes (starting at 3):
C                          #   apply transposition (this will result in a TypeError)
# otherwise
yM      # apply y to every element of
hJ    # the first element of J