Gödel encoding - Part II (decoding)

Question

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

Answer 1

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!

Answer 2

R, 168 149 132 117 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

Answer 3

Vyxal, 20 bytes

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

Try it Online!

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

Answer 4

PARI/GP, 101 bytes

n->iferr(g(n),e,x)
g(n)=if(n==2^q=logint(n,2),q,primes(1+#t=factor(n)~)[^1]-t[1,],0/0,apply(g,t[2,]))

Attempt This Online!

Returns x for invalid inputs.

Answer 5

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

Answer 6

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.

Answer 7

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