Keep Decoding This Number!

Question

This challenge posed an algorithm for encoding an integer n as another integer r. What follows is a succinct explanation of that algorithm, using n=60 as an example.

The original algorithm

• First, we encode the number as a string of brackets.

  • If n = 1, return an empty string.
  • Otherwise, we take n's prime decomposition sorted ascending and replace each element with its prime index (1-indexed) in brackets. 60 = 2*2*3*5 => [1][1][2][3]
  • Do this recursively until all we have are brackets. [1][1][2][3] => [][][[1]][[2]] => [][][[]][[[1]]] => [][][[]][[[]]]

• Once we have our string of brackets, we convert that into an integer with the following process.

  • Convert each opening bracket to a 1 and each closing bracket to a 0. [][][[]][[[]]] => 10101100111000
  • Remove all trailing 0s and the final 1. 10101100111000 => 1010110011
  • Convert the final string of 0s and 1s from binary to an integer. 1010110011 => 691

Decoding this encoding

An interesting property of this algorithm is that it is not surjective. Not every integer can be the result of this encoding.

• Firstly, the binary representation of the result r, must be balance-able in that the number of 0s must never exceed the number of 1s. A short falsey test case is 4, which is 100 in binary.
• Secondly, the brackets in the binary representation must be sorted ascending when the final 1 and trailing 0s are appended once more. A short falsey test case is 12 <= 1100 <= 110010 <= (())().

However, just determining if a number is decode-able in this way would make for a short challenge. Instead, the challenge is to repeatedly decode a given input until either an un-decode-able number or a cycle is reached, and returning the resulting sequence of numbers.

The challenge

• Given a number 1 <= r <= 2**20 = 1048576, return the sequence of numbers that r successively decodes into, starting with r itself and ending with an un-decode-able number or a cycle.
• If an un-decode-able number is given as input, such as 4 or 12, will return a list containing only the input.
• A sequence ending in a cycle should be indicated in some way, either by appending or prepending a marker (pick any non-positive integer, string, list, etc. as a marker, but keep it consistent), or by repeating the cycle in some way (repeating the first element, repeating the whole cycle, repeating infinitely, etc.).
• On the off chance that any of the sequences are infinite (by increasing forever, for example), consider it undefined behavior.
• This is code golf. Smallest number of bytes wins.

A worked example of decoding

   1 -> 1 -> 1100 -> [[]] -> [2] -> 3
-> 3 -> 11 -> 111000 -> [[[]]] -> [[2]] -> [3] -> 5
-> 5 -> 101 -> 101100 -> [][[]] -> 2*[2] -> 2*3 -> 6
-> 6 -> 110 -> 110100 -> [[][]] -> [2*2] -> [4] -> 7
-> 7 -> 111 -> 11110000 -> [[[[]]]] -> [[[2]]] -> [[3]] -> [5] -> 11
-> 11 -> 1011 -> 10111000 -> [][[[]]] -> 2*[[2]] -> 2*[3] -> 2*5 -> 10
-> 10 -> 1010 -> 101010 -> [][][] -> 2*2*2 -> 8
-> 8 -> 1000  ERROR: Unbalanced string

Test cases

4 -> [4]
12 -> [12]
1 -> [1, 3, 5, 6, 7, 11, 10, 8]
2 -> [2, 4]
13 -> [13, 13]    # cycle is repeated once
23 -> [23, 22, 14, 17]
51 -> [51, 15, 31, 127, 5381]
691 -> [691, 60]
126 -> [126, 1787, 90907]
1019 -> [1019, 506683, 359087867, 560390368728]

Suggestions and feedback for this challenge are most welcome. Good luck and good golfing!

Answer 1

Python 3, 379 358 339 337 327 310 304 bytes

Conjecture: Is 13 the only number that will lead to a cycle? (There are no exceptions smaller than 10⁶.)

Fixed a bug and -7 bytes thanks to Sherlock9.
-3 byte thanks to Jonathan Frech.
-16 bytes thanks to ovs.
-6 bytes thanks to Mr. Xcoder.

If there is a cycle, it will repeat the whole cycle.

def p(a,x=0,n=1):
 while a:x+=1;a-=n%x;n*=x*x
 return x
def g(a):
 c=i=0
 for v in a:
  c+=int(v)*2-1
  if c<0:return 0,0
  if c<1:break
  i+=1
 if a:x=p(g(a[1:i])[0]);b,c=g(a[i+1:]);return(x>c>0)*(0,0)or(x*b,x)
 return 1,0
def f(a):
 x=a,
 while(x.count(a)<3)*a:a,t=g(bin(a-~a)[2:]);x+=a,
 return x[:-1]

Try it online!

Explanation:

def p(a,x=0,n=1):     # return the a-th prime
 while a:             # magical way to enumerate primes
  x+=1
  a-=n%x
  n*=x*x
 return x

def g(a):             # decode a 0/1 string
 c=i=0
 for v in a:
  c+=int(v)*2-1       # +1 if 1, -1 if 0
  if c<0: return(0,0) # c<0: unbalanced parentheses
  if c<1: break       # first outermost parentheses
  i+=1
 if a:
   x=p(g(a[1:i])[0])  # recursive solve those inside the parentheses ...
   b,c=g(a[i+1:])     # and the remaining
   if x>c and c:      # if not ascending
    return (0,0)
   return (x*b,x)     # return (result, value of first closed parentheses)
 return (1,0)         # empty string

def f(a):
 x=a,
 while a and x.count(a)<3: # detect non-decodable or cycle
  a,t=g(bin(a-~a)[2:])     # a-~a is a*2+1
  x+=a,
 return x[:-1]

Answer 2

Pyth, 62 bytes

L?b**FKme.fP_Zyd)bSIK1fTseB.u.xyvs@L,"],"\[++JjN2 1m0h-/J1/J00

Test suite

Indicates a cycle by repeating the final number.

L?b**FKme.fP_Zyd)bSIK1    Define y to decode from list format. 0 if invalid.

fTseB.u.xyvs@L,"],"\[++JjN2 1m0h-/J1/J00
     .u                                     Repeat the following until it cycles
                                            Collecting the values in a list.
                     ++JjN2 1m0h-/J1/J0     Convert the number to expanded binary
            @L,"],"\[                       Map 0 to "],", 1 to "["
           s                                Flatten to a string.
          v                                 Evaluate as a Python object.
       .x                              0    If evaluation fails, return 0.
         y                                  Otherwise decode.
  seB                                       Duplicate the final number
fT                                          Remove all 0s.