13
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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