Analyzing Collatz-like sequences

Question

We define a Collatz-like sequence s with 4 positive integers:

• n starting value
• d > 1 divisor
• m > 1 multiplier
• i increment

(In the original Collatz sequence d = 2 m = 3 and i = 1.)

Given these integers s will be created in the following manner:

• s(0) = n
• if k > 0 and s(k-1) mod d = 0 then s(k) = s(k-1) / d
• if k > 0 and s(k-1) mod d != 0 then s(k) = s(k-1) * m + i

An example sequence with d = 2, m = 3, i = 5 and n = 80 will be s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ....

Every sequence will either reach higher values than any given bound (i.e. the sequence is divergent) or get into an infinite loop if for some t and u (t!=u) the s(t) = s(u) equality will be true.

In our problem if the value of a sequence element is larger than 10^9 or there is no element repetition before the 1000th element the sequence is considered divergent.

The task

You should write a program or function which takes the positive integers d m and i as inputs and outputs all the different ending types of the sequences (infinite loops and divergence) which the starting values n = 1, 2, 3, ... 999, 1000 can produce.

Input details

• The input is a string or list (or closest equivalent in your language) representing (in the common way) three positive integers d, m and i in that order. d and m are at least 2. Neither number is larger than 100.

Output details

The output specification is a bit wordy. Might worth to check out the examples first.

• You should output to the standard output (or closest alternative) or return a string.
• If divergent sequence is possible the first line should be DIVERGENT.
• A unique representation of a sequence's loop is it's rotation where the smallest number is the last separated by spaces. E.g. if s = 2 1 4 2 1 4 2 1 the loop is 4 2 1.
• In every following line you should output every unique loop exactly once preceded by the word LOOP. E.g. LOOP 4 2 1
• The loops should be in ascending order in regard of their last element.
• Trailing newline is optional.

Examples:

The first lines are the inputs and the following ones until a blank line are the outputs.

2 3 1
LOOP 4 2 1

2 2 6
LOOP 8 4 2 1
LOOP 12 6 3

3 7 8
DIVERGENT
LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

3 9 1
DIVERGENT

6 9 9
DIVERGENT
LOOP 18 3 36 6 1
LOOP 27 252 42 7 72 12 2
LOOP 45 414 69 630 105 954 159 1440 240 40 369 3330 555 5004 834 139 1260 210 35 324 54 9 90 15 144 24 4
LOOP 81 738 123 1116 186 31 288 48 8
LOOP 99 900 150 25 234 39 360 60 10
LOOP 126 21 198 33 306 51 468 78 13

10 10 10
LOOP 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 9 100 10 1

93 91 92
DIVERGENT
LOOP 2185 198927 2139 23
LOOP 4278 46

Reference implementation in Python 3 on Ideone.

This is code-golf so shortest entry wins.

Answer 1

Python 3, 269 254 252 246 bytes

d,m,i=eval(input())
S=set()
for n in range(1,1001):
 T=X=()
 while len(T)**3<1e9>=n:
  T=(n,)+T;n=[n//d,n*m+i][n%d>0]
  if n in T:I=T.index;L=T[:I(n)+1];M=I(min(L));X=L[M:]+L[:M]
 S|={X}
for x in sorted(S):print(x and"LOOP"or"DIVERGENT",*x[::-1])

(Now 10 times slower to save a few bytes. Typical code golf.)

Input a list via STDIN (e.g. [2, 3, 1]). I'm thinking that there's got to be a better way of standardising the cycles...

The approach is quite straightforward — test all 1000 numbers and take only the unique outputs. However, there are two little tricks in there:

• Loops are represented by nonempty tuples, but more importantly divergence is represented by an empty tuple. This is good because:

  • It doesn't break sorted, and will even appear before all the loop tuples
  • It allows us to select a string via x and"LOOP"or"DIVERGENT"
  • *()[::-1] doesn't affect print

• The loops are built backwards to turn "sort ascending by last element" into "sort ascending by first element", which removes the need to pass a lambda into sorted.

Previous submission, 252 bytes

d,m,i=eval(input())
def f(n,T=()):
 x=[n//d,n*m+i][n%d>0];I=T.index
 if x in T:L=T[:I(x)+1];M=I(min(L));return L[M:]+L[:M]
 return()if(T[1000:]or x>1e9)else f(x,(x,)+T)
for x in sorted(set(map(f,range(1,1001)))):print(x and"LOOP"or"DIVERGENT",*x[::-1])

This one's a lot faster.