Гипотеза Коллатца постулирует, что если вы возьмете любое натуральное число, то повторите этот алгоритм достаточно много раз:

if number is odd, then multiply by three and add one
if number is even, then divide by two

в конечном итоге вы получите 1. Это, кажется, всегда работает, но никогда не было доказано, что это всегда работает.

Вы уже играли в гольф, рассчитывая, сколько времени потребуется, чтобы добраться до 1 , поэтому я решил немного изменить ситуацию.

Начиная с заданного положительного целого числа, рассчитайте, сколько времени потребуется, чтобы добраться до 1 (его «время остановки»). Затем найдите время остановки этого номера.

Повторяйте, пока не дойдете до 1, или пока не дойдете до совершенно произвольного предела в 100 итераций. В первом случае выведите, сколько итераций потребовалось. В последнем случае выведите «Fail» или другой согласованный вывод по вашему выбору, если он не является целым числом 1≤n≤100. Вы не можете вывести пустую строку для этой опции. Вывод целого числа вне диапазона [1, 100], однако, разрешен.

Примеры:

Input: 2
2->1
Output: 1

Input: 5
5->5->5->5->5->...
Output: Fail

Input: 10
10->6->8->3->7->16->4->2->1
Output: 8

Input: 100
100->25->23->15->17->12->9->19->20->7->16->4->2->1
Output: 13

Input: 10^100
10^100->684->126->108->113->12->9->19->20->7->16->4->2->1
Output: 13

Input: 12345678901234567890
12345678901234567890->286->104->12->9->19->20->7->16->4->2->1
Output: 11

Input: 1
--Depending on your code, one of two things may happen. Both are valid for the purposes of this question.
1
Output: 0
--Or:
1->3->7->16->4->2->1
Output: 6

Как я рассчитал 10^100и 12345678901234567890использовал язык, который поддерживает только реалы для этого размера, если ваш язык более точный, вы можете получить разные результаты для них.

счет

Поскольку это код-гольф , выигрывает ответ с кратчайшим количеством байтов.

Желе , 24 байта

×3‘$HḂ?’пL’
Ç1¹?ȷ2Сi1’

Попробуйте онлайн!

Python 2 , 70 байт

f=lambda n,k=0,j=0:n-1and-~f(k*[n/2,n*3+1][n%2]or f(j/99or n,1),k,j+1)

Возвращает 199 для ста или более итераций.

Попробуйте онлайн!

Атташе , 40 байт

`-&3@`#@PeriodicSteps[CollatzSize@Max&1]

Попробуйте онлайн!

Это новый язык, который я сделал. Я хотел найти подходящий инфиксный язык, и вот результат: подделка Mathematica. Ура?

объяснение

Это композиция из нескольких функций. Эти функции:

• PeriodicSteps[CollatzSize@Max&1]Это приводит к функции, которая применяет свой аргумент до тех пор, пока результаты не будут содержать повторяющийся элемент. Эта функция CollatzSize@Max&1применяется CollatzSizeк большей части ввода и 1, чтобы избежать неправильного ввода 0в CollatSize.
• `#является оператором в кавычках; когда применяется монадически в этом смысле, он получает размер своего аргумента
• `-&3является связанной функцией, которая связывает аргумент 3с функцией `-, которая читается как «минус 3». Это потому, что приложение PeriodicSteps выдает 0s, которые необходимо учитывать. (Он также аккуратно обрабатывает такие номера, как 5, которые сопоставляются -1.)

J , ₄₉ 45 байт

-4 байта благодаря более короткому коду последовательности Коллатца, взятому из комментария @ randomra здесь .

(2-~[:#(>&1*-:+2&|*+:+>:@-:)^:a:)^:(<101)i.1:

Выходы 101для неверных результатов.

Попробуйте онлайн!

объяснение

Неудивительно, что это объяснение быстро устарело. Я собираюсь оставить его в терминах старого 49-байтового ответа, который у меня был, который я включил ниже. Если вы хотите обновить, просто дайте мне знать. Способ, которым он находит длину рекурсивной последовательности, остается тем же самым, я только что использовал более короткий метод последовательности Коллатца.

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)^:(<101)i.1:

Нахождение длины последовательности Коллатца

Этот раздел кода является следующим

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)

Вот объяснение:

(1 -~ [: # %&2`(1+3&*)@.(2&|) ^: (1&<) ^: a:)  Given an input n
                                       ^: a:   Apply until convergence, collecting
                                                each result in an array.
                              ^: (1&<)         If n > 1 do the following, else
                                                return n.
                        (2&|)                  Take n mod 2.
           %&2                                 If n mod 2 == 0, divide by 2.
               (1+3&*)                         If n mod 2 == 1, multiply by 3 
                                                and add 1.
         #                                     Get the length of the resulting
                                                array.
 1 -~                                          Subtract 1.

К сожалению, команда apply verb ( ^:), когда сказано хранить результаты, также сохраняет начальное значение, так что это означает, что мы (как всегда) отключены на единицу. Следовательно, почему мы вычитаем 1.

Нахождение длины рекурсивной последовательности

(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:) ^: (< 101) i. 1:  Given an input n.
                                      ^: (< 101)        Apply 100 times,
                                                         collecting results
                                                         in an array.
(1-~[:#%&2`(1+3&*)@.(2&|)^:(1&<)^:a:)                   Collatz sequence length.
                                                 i. 1:  Index of first 1 (returns
                                                         101, the length of the
                                                         array if 1 not found).

C (gcc) , 75 байтов

i,j;f(n){for(j=0;(i=n)&&j++<100;)for(n=0;i-1;++n)i=i&1?i*3+1:i/2;i=!i*j-1;}

Возвращает -1для n>=100итераций.

Попробуйте онлайн!

C (gcc) , 73 байта

i,j;f(n){for(j=-1;(i=n)&&j++<99;)for(n=0;i-1;++n)i=i&1?i*3+1:i/2;i=!i*j;}

Возвращает 0для n>=100итераций.

Попробуйте онлайн!

JavaScript (ES6), 57 байт

Возвращает trueпри неудаче. Возвращает 0за 1.

f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i

Контрольные примеры

f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i

console.log(f(2))    // 1
console.log(f(5))    // fail
console.log(f(10))   // 8
console.log(f(100))  // 13
console.log(f(1))    // 0

APL (Dyalog Unicode) , 39 60 53 52 49 байтов

-3 байта благодаря @ngn

0∘{99<⍺:⋄1=⍵:0⋄1+(⍺+1)∇{1=⍵:0⋄1+∇⊃⍵⌽0 1+.5 3×⍵}⍵}

Попробуйте онлайн!

Использует код @ngn для Collatz, но ранее использовал код @ Uriel.

Вот старая версия, которая не соответствует спецификации:

{1=⍵:0⋄1+∇{1=⍵:0⋄2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2}⍵}

Perl 6 , 56 байт

{($_,{($_,{$_%2??$_*3+1!!$_/2}...1)-1}...1).head(102)-1}

Попробуйте онлайн!

Возвращает 101для бесконечной последовательности.

Шелуха , 21 байт

←€1↑101¡ȯ←€1¡?½o→*3¦2

Попробуйте онлайн! Возвращает -1при неудаче,0 при вводе1 .

объяснение

←€1↑101¡ȯ←€1¡?½o→*3¦2  Implicit input (a number).
             ?½o→*3¦2  Collatz function:
             ?     ¦2   if divisible by 2,
              ½         then halve,
               o→*3     else multiply by 3 and increment.
        ȯ←€1¡?½o→*3¦2  Count Collatz steps:
            ¡           iterate Collatz function and collect results in infinite list,
          €1            get 1-based index of 1,
        ȯ←              decrement.
       ¡               Iterate this function on input,
   ↑101                take first 101 values (initial value and 100 iterations),
←€1                    get index of 1 and decrement.

C (gcc) , 70 73 байта

g(x){x=x-1?g(x%2?3*x+1:x/2)+1:0;}f(x,m){for(m=0;(x=g(x))&&100>m++;);x=m;}

Попробуйте онлайн!

Возвращает, 101когда количество итераций превышает 100.

Чисто , 146 ... 86 байт

-11 байт благодаря Орджану Йохансену

import StdEnv
?f l n=hd[u\\1<-iterate f n&u<-l]

?(?(\b|isOdd b=3*b+1=b/2)[0..])[0..99]

Как частичная функция литерал.

Попробуйте онлайн!

Прерывает с hd of [] если число итераций превышает 100.
Выход с с Heap Fullдля входов выше ~, 2^23если вы не укажете больший размер кучи.

Python 2 , 99 98 97 байт

• Сохраненный байт, используя c and t or fвместоt if c else f .
• Сохраненный байт путем вывода -1вместо fили 'f'для не останавливающих вводов.

exec"f,F="+"lambda n,i=0:n<2and i or %s"*2%("f([n/2,3*n+1][n%2],-~i),","i>99and-1or F(f(n),-~i)")

Попробуйте онлайн!

BiwaScheme , 151 символ

(define(f n i s)(if(= s 0) 'F(if(= n 0)i(f(letrec((c(lambda(m k)(if(= m 1)k(c(if(=(mod m 2)0)(/ m 2)(+(* m 3)1))(+ k 1))))))(c n 0))(+ i 1)(- s 1)))))

Вы можете попробовать это здесь .

R , 119 107 байт

Частично использует Коллатец код Jarko Dubbeldam от сюда . Возвращает 0для> 100 итераций (сбой).

pryr::f(x,{N=n=0
while(x-1){while(x-1){x=`if`(x%%2,3*x+1,x/2);n=n+1}
x=n
n=0
N=N+1
if(N==100)return(0)}
N})

Попробуйте онлайн!

APL NARS, 115 байтов, 63 символа

{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}

Вероятно, с использованием циклов было бы более понятно ... Есть 4 функции, 2 вложенные и риксивные, и первая только для определения и инициализации = 0, переменная d, видимая из 2-й функции как счетчик глобальной переменной.

q←{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}

Эта 3-я функция будет функцией, возвращающей количество вызовов для разрешения гипотезы Коллатца для ее аргумента.

{⍵=1:d⋄99<d+←1:¯1⋄∇q⍵}

Это 2-я функция, если ее arg = 1, остановить ее рекурсию и вернуть d число раз, когда она называется самой-1; иначе, если сам вызывается более 99 раз, остановите свою рекурсию и верните -1 (сбой), иначе вычислите гипотезу Коллатца для ее аргумента и вызовите себя для значения длины последовательности Коллатца. Для меня, даже если все это кажется выполненным, запуск может быть большой проблемой, если определена глобальная переменная и одна переменная в функции с тем же именем, когда программист видит ее как локальную переменную.

  f←{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}     
  f 2
1
  f 3
5
  f 5
¯1
  f 10
8
  f 100
13
  f 12313
7
  f 1
0

(Emacs, Common, ...) Lisp, 105 байт

Возвращает t для итераций> 100

(defun f(n k c)(or(> c 100)(if(= n 1)(if(= k 0)c(f k 0(1+ c)))(f(if(oddp
n)(+ n n n 1)(/ n 2))(1+ k)c))))

Expanded:

(defun f (n k c)
  (or (> c 100)
      (if (= n 1)
          (if (= k 0) c
            (f k 0 (1+ c)))
        (f (if (oddp n) (+ n n n 1) (/ n 2))
           (1+ k) c))))
(f (read) 0 0)