Integer Division Loops

Question

Challenge

Given any positive integer supported by your language:

1. Take the input and divide it into two halves. For all divisions in this program, if the input is odd, round one half up and one half down (ex: 7 -> 3,4, not 7 -> 3.5,3.5).
2. Divide either number in half, then take the larger of these two new halves and add it back to the number that wasn’t split. Ex: 3,4 -> (1,2),4 -> 1,6 or 3,4 -> 3,(2,2) -> 5,2.
3. Repeat step 2 until you reach a set you have seen before. Ex: 5 -> 3,2 -> (1,2),2 -> 1,4 -> 1,(2,2) -> 3,2. Since we’ve seen 3,2 before, we may stop repeating. You may completely exhaust a stack in the process of doing this. Ex: 5 -> 3,2 -> (1,2),2 -> 1,4 -> (0,1),4 -> 0,5.
4. Output each pair in the loop (i.e. the above without the intermediate steps, from the first appearance of a pair until the second, but not including the second). Ex: 3,2 -> 1,4. If the input is included, don’t output a 0 with it - 5 -> 3,2 -> 1,4, not 0,5 -> 3,2 -> 1,4.
5. Repeat steps 1-4 by splitting the pairs differently.

I/O

Input is a positive integer larger than 1 and smaller than either the maximum integer supported by your language or the maximum integer that won’t crash the computer, whichever is smaller.

Output is the loops from above in any format you want (string, list, array, etc.). Trailing white space is allowed.

Do not output the same loop twice, nor different versions of the same loop. Ex: 2 -> 1,1 and 1,1 -> 2 are both valid loops, but they describe the same loop, beginning at different points on the loop. Likewise, two loops that are identical but go in the reverse order should not be outputted. Ex: 3 -> 1,2 -> 2,1 and 3 -> 2,1 -> 1,2 are the same loop, but they go in the opposite direction from each other.

You may use any delimiter to differentiate between the pairs, between each number in the pairs, and between each loop, provided that they are three distinct chars or strings. Above, I divided the numbers using commas, the pairs using ->’s, and the loops using boring instructions. In my examples below, I will use parentheses around each pair, commas between each number within a pair, and new lines between each loop.

Examples

Credit to @WheatWizard’s code for fixing up my examples list. As I said in an earlier draft, I was sure I was missing a few since I was doing it by hand, but boy was I missing some.

Input: 2
Output: (2)(1,1)

Input: 3
Output:

(3)(1,2)
(1,2)(2,1)
(3)(1,2)(2,1)

Input: 4
Output:

(4)(2,2)(1,3)
(1,3)(3,1)
(4)(2,2)(1,3)(3,1)
(4)(2,2)(3,1)(1,3)
(3,1)(1,3)
(4)(2,2)(3,1)

Input: 5

Output:

(5)(2,3)(1,4)
(1,4)(3,2)
(2,3)(1,4)(3,2)(4,1)
(5)(2,3)(1,4)(3,2)(4,1)
(2,3)(4,1)
(5)(2,3)(4,1)

Input: 6

Output:

(6)(3,3)(1,5)
(1,5)(4,2)(2,4)
(4,2)(2,4)
(1,5)(4,2)(5,1)(2,4)
(4,2)(5,1)(2,4)
(6)(3,3)(1,5)(4,2)(5,1)
(6)(3,3)(5,1)(2,4)(1,5)
(2,4)(1,5)(4,2)
(5,1)(2,4)(1,5)(4,2)
(2,4)(4,2)
(5,1)(2,4)(4,2)
(6)(3,3)(5,1)

Input: 7

Output:

(7)(3,4)(1,6)
(1,6)(4,3)(2,5)
(2,5)(5,2)
(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(7)(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)
(2,5)(1,6)(4,3)
(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(5,2)(2,5)
(3,4)(5,2)(6,1)
(7)(3,4)(5,2)(6,1)

Scoring

This is code-golf, so the lowest byte count wins.

---

This is my first challenge here, so any feedback would be greatly appreciated. Link to sandbox here.

Fun fact: I was bored one day and playing with random little pieces of pencil lead in this manner and eventually noticed that I could keep going in these types of loops. For some reason my first reaction was “hey, this would be a great challenge for code golf.”

Answer 1

Clean, 267 ... 167 bytes

import StdEnv
f s l|any((==)s)l=[dropWhile((<>)s)l]#[h,t:_]=s
|1>h*t=f[max h t]l=f[h/2,(h+1)/2+t](l++[s])++(f[(t+1)/2+h,t/2](l++[s]))
@n=removeDup(f[n/2,(n+1)/2][[n]])

Try it online!

Ungolfed:

loops num
    = removeDup (half (divide num) [[num]])
where
    divide num
        = [num/2, (num+1)/2]
    half [_, 0] list
        = list
    half [0, _] list
        = list
    half [a, b] list
        | isMember [a, b] list
            = [dropWhile ((<>) [a, b]) list]
        # [u, v: _]
            = divide a
        # [x, y: _]
            = divide b
        = (half [u, v+b] (list ++ [a, b])) ++ (half [a+y, x] (list ++ [a, b]))

Answer 2

Haskell, 227 203 bytes

17 bytes saved thanks to Οurous

(%)=div
u x|odd x=x%2+1|1>0=x%2
[0,b]!l=[b]!l
[b,0]!l=[b]!l
t!l|elem t l=[dropWhile(/=t)l]
t@[a,b]!l|q<-l++[t]=[a%2,u a+b]!q++[u b+a,b%2]!q
f x|q<-[x%2,u x]![[x]]=[a|(a,b)<-zip q[0..],notElem a$take b q]

Try it online!