31
\$\begingroup\$

Related but different.

Part II

Taken from the book: Marvin Minsky 1967 – Computation:
Finite and Infinite Machines, chapter 14.

Background

As the Gödel proved, it is possible to encode with a unique positive integer not just any string
but any list structure, with any level of nesting.

Procedure of encoding \$G(x)\$ is defined inductively:

  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.

Examples:

[0] → 3

[[0]] → \$3^3 =\$ 27

[1, 2, 3] → \$3^{2^1} \cdot 5^{2^2} \cdot 7^{2^3} = \$ 32427005625

[[0, 1], 1] → \$3^{3^{2^0} \cdot 5^{2^1}} \cdot 5^{2^1} = \$ 15206669692833942727992099815471532675

Task

Create a program that encoding (in this way) any given (possibly ragged) list to integer number.
This is code-golf, so the shortest code in bytes wins.

Input

Valid non-empty list.
UPD
Some considerations regarding empty lists are given here.

You may assume:

  • There are no empty sublists
  • Structure is not broken (all parentheses are paired)
  • List contains only non-negative integers

Output

Positive integer obtained by the specified algorithm

Note

Numbers can be very large, be careful! Your code must be correct in principle, but it is acceptable that it cannot print some number. However, all test cases are checked for TIO with Mathematica program and work correctly.

Test cases

[0,0,0,0,0] → 15015
[1, 1, 1] → 11025
[[1], [1]] → 38443359375
[0, [[0]], 0] → 156462192535400390625
[[[0], 0], 0] → 128925668357571406980580744739545891609191243761536322527975268535
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Wouldn't an empty list just be encoded as 1? Ah, that would be the same as the encoding of the number 0. \$\endgroup\$ Apr 12, 2023 at 22:07
  • 2
    \$\begingroup\$ I upvoted just for "the Gödel" \$\endgroup\$
    – Stef
    Apr 13, 2023 at 18:27
  • 1
    \$\begingroup\$ @Stef I dont know what you mean but I upvoted (ofc because the question is good) but also! it does remind me of Kurt Godel (which, has some related to this question right? maybe not sure) anyway, have a great day on both of you ^^ \$\endgroup\$ Apr 13, 2023 at 19:19
  • \$\begingroup\$ @PaŭloEbermann Thank you for interesting idea, I made some updates \$\endgroup\$
    – lesobrod
    Apr 14, 2023 at 18:32
  • \$\begingroup\$ @WilliamMartens Yes, Kurt Gödel's relationship to this question is that he came up with Gödel encoding. \$\endgroup\$ Oct 26, 2023 at 21:33

18 Answers 18

10
\$\begingroup\$

Jelly,  11 10 9  8 bytes

-1 thanks to Unrelated String! (Use of a dyadic chain in place of a monadic compound link avoiding the need for argument manipulation with `.)

߀Żð%¡ÆẸ

A monadic Link that accepts a ragged list of non-negative integers and yields its Gödel encoding.

Try it online! Or see the test-suite.

How?

߀Żð%¡ÆẸ - Link: non-empty list OR number, X
     ¡   - repeat...
    %    -   ...number of times: (X) modulo (X)
                                 positive ints -> 0
                                 zero -> nan*
                                 non-empty lists -> non-empty lists*
                                 * truthy non-integers are treated by ¡ as 1
   ð     -   ...action: the dyadic chain - f(X, X):
 €       -              for each E in X:
ß        -                call this Link with X=E
  Ż      -              prefix with a zero (if X=zero we get [0])
     ÆẸ  - recompose from prime exponent list
              e.g.:
                    [0,4,0,2] -> 3^4 × 7^2 = 3969
                          [0] -> 2^0 = 1
                            n -> 2^n (non-list n treated as [n])
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 8 with ð \$\endgroup\$ Apr 12, 2023 at 9:41
  • 2
    \$\begingroup\$ Pesky ` :) thanks @UnrelatedString \$\endgroup\$ Apr 12, 2023 at 16:35
5
\$\begingroup\$

Brachylog, 24 bytes

;2^₍|↰ᵐGl~lℕ₃ᵐṗᵐ≠≜;Gz^ᵐ×

Try it online!

Surely there are shorter ways to generate a list of primes…

Brachylog is based on SWI-Prolog and can deal with arbitrarily large integers, but this will quickly run out of memory for even simple lists.

Explanation

;2^₍                       Output = 2^Input
    |                      Or (if the input is not an integer)
     ↰ᵐG                   Recursive call of this predicate for all elements of the Input; call the result G
       Gl~l                Take a list with as many elements as G
           ℕ₃ᵐṗᵐ≠≜         It must be a list of primes greater than 3 and all different (it always unifies with increasing magnitudes)
                   ;Gz     Zip with G
                      ^ᵐ   Map power
                        ×  Multiply
\$\endgroup\$
5
\$\begingroup\$

Vyxal, A 23 21 11 bytes

@AndrovT cool result:

Eλ-[żǎ$vxeΠ

Try it Online!

Unfortunately, can't explain in detail. Hope one of Vyxal' experts helps...

My old version, maybe useful for beginners in Vyxal:

ƛIȧ[:L›ÞpŻ$vx¨£e|E]fΠ

Every input must be list of lists, so first test case should be [[1, 1, 1]] etc.

-2 bytes thanks @emanresu (Vyxal chat)

ƛ                       #Begin lambda map 
 Iȧ                     #Condition for If: is it list?
     [                  #Begin If
      :L›               #If list - get length and add 1
         ÞpŻ            #Get slice of given length from infinite  list of primes
            $           #Swap
             vx         #Recursively apply to list
               ¨£e      #Zip and reduce pairs with exponentiation
                  |     #Else
                   E    #If number - two power
                    ]   #End If and lambda map,
                     fΠ #Flatten and reduce by product

Try it Online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 11 \$\endgroup\$
    – AndrovT
    Apr 12, 2023 at 22:34
  • \$\begingroup\$ @AndrovT Cool, thanks! You should post your own answer! Or, please explain, how Π works correct without closed ] ? \$\endgroup\$
    – lesobrod
    Apr 13, 2023 at 3:50
  • \$\begingroup\$ there's no need to close structures in vyxal \$\endgroup\$
    – AndrovT
    Apr 13, 2023 at 13:31
5
\$\begingroup\$

R, 103 102 98 bytes

Edit: -1 byte, and then -4 more, both thanks to pajonk

`?`=\(x,p=3)`if`(sum(!p%%1:p)>2,x?p+1,`if`(is.list(x),`if`(length(x),(x[-1]?p+1)*p^?el(x),1),2^x))

Attempt This Online!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ You've got an unnecessary newline at the end, I think. \$\endgroup\$
    – pajonk
    Apr 13, 2023 at 12:03
  • \$\begingroup\$ @pajonk - Oh, thanks for spotting that! \$\endgroup\$ Apr 13, 2023 at 12:05
  • 1
    \$\begingroup\$ Another -1: x[[1]]->el(x) \$\endgroup\$
    – pajonk
    Apr 13, 2023 at 12:09
  • 1
    \$\begingroup\$ 98 bytes by renaming the recurrence function to ?. \$\endgroup\$
    – pajonk
    Apr 13, 2023 at 12:14
  • \$\begingroup\$ @pajonk - Thanks again! \$\endgroup\$ Apr 13, 2023 at 16:09
4
\$\begingroup\$

JavaScript (ES13), 82 bytes

Expects a ragged list of Bigints. Returns a Bigint.

f=(a,k=2n,t=1n)=>a.at?a.map(a=v=>(g=d=>k%d--?g(d):d)(k++)?a(v):t*=k**f(v))&&t:k**a

Attempt This Online!

Or 79 bytes without Bigints.

\$\endgroup\$
2
  • \$\begingroup\$ So we can use BigInt() in JS just adding n suffix? \$\endgroup\$
    – lesobrod
    Apr 11, 2023 at 17:43
  • \$\begingroup\$ @lesobrod Basically yes. :-) \$\endgroup\$
    – Arnauld
    Apr 11, 2023 at 18:41
3
\$\begingroup\$

Arturo, 66 bytes

f:$[x][(block? x)?[p:3∏map x=>[p^f&until->prime? p->'p+2]]->2^x]

Try it

f:$[x][                       ; a function f taking an argument x
    (block? x)?[              ; is x a block? then...
        p:3                   ; assign 3 to p
        ∏                     ; product
        map x=>[              ; map over x, assign current elt to &
            p^f&              ; p raised to the Gödel encoding of the current elt
            until->prime? p-> ; until p is prime...
                'p+2          ; add 2 to p via in-place modification
        ]                     ; end map
    ]                         ; end the 'true' part of the ternary
    ->2^x                     ; ...otherwise, if x isn't a block, take 2^x
]                             ; end function
\$\endgroup\$
1
  • \$\begingroup\$ Interesting fresh and bright language! \$\endgroup\$
    – lesobrod
    Apr 11, 2023 at 19:19
3
\$\begingroup\$

Python, 103 bytes

g=lambda n,k=1,m=1:m%k>n or-~g(n,k+1,m*k)
f=lambda l,p=3:l*0==0and 2**l or p**f(l[0])*f(l[1:]or 0,g(p))

Attempt This Online!

Method for calculating next prime is shamelessly adapted from Dennis's answer.

\$\endgroup\$
3
\$\begingroup\$

PARI/GP, 118 bytes

Modified from @Dominic van Essen's answer


Golfed version, try it online!

G(x,p=3)={if(sum(i=1,p,(p%i)==0)>2,G(x,p+1),if(type(x)=="t_VEC",if(#x,p^G(x[1])*G(vector(#x-1,i,x[i+1]),p+1),1),2^x))}

Ungolfed version

G(x, p = 3) =
{
  if (sum(i = 1, p, (p % i) == 0) > 2,
    G(x, p + 1),
    if (type(x) == "t_VEC",
      if (#x,
        p^G(x[1]) * G(vector(#x - 1, i, x[i + 1]), p + 1),
        1
      ),
      2^x
    )
  )
}


print(G(0)) \\ 1
print(G(1)) \\ 2
print(G([0,0])) \\ 15
print(G([0,1])) \\ 75
print(G([0])) \\ 3
print(G([[0]])) \\ 27
print(G([0,0,0,0,0])) \\ 15015
print(G([1,2,3])) \\ 32427005625
print(G([[0,1],1])) \\ 15206669692833942727992099815471532675
\$\endgroup\$
3
\$\begingroup\$

Julia, 68 66 bytes

!x::Int=2^x
!(x,p=2)=prod(i->(while(p+=1).%(2:p-1)∋0end;p^!i),x)

Attempt This Online!

-2 bytes by MarcMush.

Doesn't use prime built-ins, which are not in Base anyway. Feels a bit weird to include a type annotation while golfing in a language that doesn't require it, but it looks like a decent way to disambiguate between numbers and lists.

Note that this will only produce correct output within Int64. At the expense of 5 bytes, we can add a big(...) wrapper to get a version that processes all test cases as desired:

Julia, 73 71 bytes

!x::Int=big(2)^x
!(x,p=2)=prod(i->(while(p+=1).%(2:p-1)∋0end;p^!i),x)

Attempt This Online!

\$\endgroup\$
4
  • \$\begingroup\$ Kirill L. in fact program could accept single numbers. This is not quite clear point, but you can exclude special detection for numbers \$\endgroup\$
    – lesobrod
    Apr 22, 2023 at 14:18
  • \$\begingroup\$ @lesobrod Thanks, I've updated the answer to use the shorter version as the "default" one. \$\endgroup\$
    – Kirill L.
    Apr 22, 2023 at 15:52
  • 1
    \$\begingroup\$ I didn't try it but prod(f,x) might be shorter than prod(x.|>f)? \$\endgroup\$
    – MarcMush
    Apr 22, 2023 at 23:15
  • \$\begingroup\$ @MarcMush It works indeed, thanks! \$\endgroup\$
    – Kirill L.
    Apr 23, 2023 at 7:39
2
\$\begingroup\$

05AB1E, 23 19 bytes

o"Ddië®δ.VāØsmP"©.V

Also works for loose integer inputs, instead of just (ragged) lists.

Try it online or verify all test cases.

Explanation:

Recursive functions are always so verbose in 05AB1E.. :/

o            # Take 2 to the power each inner-most integer of the (implicit) input
 "..."       # Push the recursive string explained below
      ©      # Store it in variable `®`
       .V    # Evaluate and execute it as 05AB1E code
             # (after which the result is output implicitly)

D            # Duplicate the current list
 di          # If it's a single integer:
             #  (do nothing, simply keep it as is)
  ë          # Else (it's a list instead):
    δ        #  Map over each inner item:
   ® .V      #   Do a recursive call
       ā     #  Then push a list in the range [1,length] (without popping)
        Ø    #  Map index each to the 0-based prime: [3,5,7,...]
         s   #  Swap the two lists on the stack
          m  #  Take the primes to the power of the values
           P #  Take the product of this list
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 67 bytes

≔X²Aθ⊞υθFυFΦι⁺⟦⟧κ⊞υκF⮌υ«≔¹η≔²ζFι«≦⊕ζW¬⬤…²ζ﹪ζμ≦⊕ζ≧×Xζ⊟⁺⟦⁰⟧κη»⊞ιη»I⊟θ

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

≔X²Aθ

Vectorised raise 2 to the power of the input.

⊞υθFυFΦι⁺⟦⟧κ⊞υκF⮌υ«

Extract all of the sublists and loop over them in reverse.

≔¹η≔²ζ

Start with a product of 1 and a last prime of 2.

Fι«

Loop over the elements of the list.

≦⊕ζW¬⬤…²ζ﹪ζμ≦⊕ζ

Get the next prime number by trial division (1 byte shorter than Wilson's theorem).

≧×Xζ⊟⁺⟦⁰⟧κη»

Multiply the product by the prime power of the next list element (but if that's a list, then use its last element, as that's where we put the value on a previous loop iteration).

⊞ιη

Save the resulting value to the sublist.

»I⊟θ

Output the resulting value of the original list.

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

Pyth, 23 bytes

L?sIb^2b*F^V.fP_Zlb3yMb

Try it online!

Defines an encoding function y(b).

Explanation

L                          # define y(b)
 ?sIb                      # if b is invariant under s: (sums for list, int for int)
     ^2b                   #   2 ^ b
                           # else:
                    yMb    #   apply y to each element of b
            .fP_Zlb3       #   generate a list of len(b) primes starting with 3
          ^V               #   vectorized exponentiation
        *F                 #   fold over multiplication
\$\endgroup\$
1
  • \$\begingroup\$ woah. great ! respect \$\endgroup\$ Apr 12, 2023 at 14:35
2
\$\begingroup\$

Wolfram Language (Mathematica), 37 bytes

1##&@@(i=1;Prime@++i^#&/@#)&//@(2^#)&

Try it online!

                               (2^#)    numbers: x -> 2^x
                            //@         lists:
1##&@@(                /@#)               product of
       i=1;Prime@++i^#&                     prime(n+1)^x_n
\$\endgroup\$
2
\$\begingroup\$

J, 32 30 bytes

*/@(p:@#\^$:&>)`(2^x:)@.(0=L.)

Try it online!

-2 thanks to att

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think you can p:@#\ \$\endgroup\$
    – att
    Apr 17, 2023 at 6:53
  • \$\begingroup\$ Yep, and that change allows me to save another byte too. \$\endgroup\$
    – Jonah
    Apr 18, 2023 at 21:49
1
\$\begingroup\$

Factor + math.primes.lists math.unicode, 83 bytes

: g ( a -- n ) dup real? [ 2^ ] [ [ lprimes cdr lnth swap g ^ ] map-index Π ] if ;

Try it online!

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

PowerShell Core, 147 bytes

$f={$r,$p=1,2
$args|%{do{$p++;for($u,$k=1,0;++$u-$p){$k+=!($p%$u)}}while($k)$r=$r*($b=[bigint])::Pow($p,(&($f,{$b::Pow(2,$_)})[$_-is[int]]@_))}
$r}

Try it online!

Fun challenge!

Recursive function that expects the input list using splatting and returns a [bigint]

Please ignore the inconsistent output of the array in the tests result as PowerShell has a tendency to flatten them sometime.

Explanation

This part updates $p to become the next prime after $p

do{$p++;for($u,$k=1,0;++$u-$p){$k+=!($p%$u)}}while($k)

This part checks whether the current list item $_ is a number or not If it is a number, we take its power of two, otherwise, we do a recursive call.

$r=$r*($b=[bigint])::Pow($p,(&($f,{$b::Pow(2,$_)})[$_-is[int]]@_))}
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 71 bytes

Of course, answering your own challenge is a bit ridiculous, but it is rather a supplement to not break the main post.
Thanks @PaŭloEbermann for the idea!
It seems we can account for the empty lists, naively but correctly, using the next encoding:

  1. If \$x\$ is non-negative integer, \$G(x) = 2^{x+1}\$
  2. If \$x\$ is an empty list, [ ], \$G(x) = 2^0 = 1\$
  3. 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...\$

Of course, this is a purely intuitive idea without proof. But I do not see contradictions at the moment.

So here is Mathematica program that encodes any array-like structure (with possible empty lists) with a unique positive integer.

Switch[#,{},1,{__},Times@@(Prime@Range[2,Length@#+1]^#0/@#),_,2^(#+1)]&

Some related test cases:

[] → 1
[[]] → 3
[[], 1, []] → 13125
[[], [0, []], 1] → 204721573027200065553188323974609375

Try it online!

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

PARI/GP, 51 bytes

f(x)=if(x'===0,2^x,prod(i=1,#x,prime(i+1)^f(x[i])))

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.