# 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 → 
4 → 2
5 → None
6 → None
7 → None
8 → 3
9 → 
10 → None
666 → None
729 → None
1024 → 10
1215 → None
3375 → [, ]
77777 → None
5859375 → [0, ]
666777666 → None
2210236875 → [3, 2, 1, 0]
7625597484987 → [[]]
1111111111111111111111111111 → None

• Suggested test cases: 729, 1215. I think they're both invalid. Apr 17 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.) Apr 17 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 Apr 17 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? Apr 18 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. Apr 19 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 Apr 17 at 16:22
• I think the output for '8' should be '3'... Apr 18 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. Apr 19 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 (). Apr 17 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! Apr 18 at 8:23
• @pajonk - I finally got rid of enough if-elses that the [ substitution only breaks-even... Apr 18 at 13:45
• Great news, well done! Apr 18 at 16:29
• Also, -1 byte with another weird substitution. Apr 18 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


# 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