# Keep Decoding This Number!

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!

• – user202729 Dec 14 '17 at 6:52
• How does 1 give 3? – Leaky Nun Dec 14 '17 at 12:15
• @LeakyNun 1 --(append an 1 and trailing zeros)--> 1100 --> [[]] --> [[1]] --> [2] --> 3 – Colera Su Dec 14 '17 at 12:58
• 6->110->110100 which isn't valid, right? So should input 1 give [1,3,5,6]? – dylnan Dec 15 '17 at 4:55
• And for 7: 7->111->11110000->[[[[]]]]->4th prime = 7? Maybe I don't understand the algorithm – dylnan Dec 15 '17 at 5:00

# Python 3, 379358339337327310 304 bytes

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

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]


# 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.