Расчет Коллац Кузены

21

Определите функцию f (n) для натурального числа n следующим образом:

  • n / 2 , если n четное
  • 3 * n + 1 , если n нечетно

Если вы неоднократно применяете эту функцию к любому n, большему 0, результат всегда кажется сходящимся к 1 (хотя пока никто не смог доказать это). Это свойство известно как гипотеза Коллатца .

Определите время остановки целого числа как количество раз, которое вы должны пройти через функцию Коллатца f, прежде чем оно достигнет 1. Вот время остановки первых 15 целых чисел:

1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

Давайте назовем любой набор чисел с одинаковым временем остановки двоюродных братьев Коллатц . Например, 5 и 32 - двоюродные братья Коллатц, время остановки 5.

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

вход

Неотрицательное целое число S, заданное через STDIN, ARGV или аргумент функции.

Выход

Список всех чисел, время остановки которых S, отсортировано в порядке возрастания . Список может быть выведен вашей программой или возвращен или выведен вашей функцией. Формат вывода гибкий: разделенный пробелами, разделенный новой строкой или любой стандартный формат списка вашего языка подходит, если числа легко отличимы друг от друга.

Требования

Ваше представление должно давать правильные результаты для любого S ≤ 30. Оно должно заканчиваться в секундах или минутах, а не часах или днях.

Примеры

0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

Вот суть вывода для S = 30 .

Это : выигрывает самая короткая программа в байтах. Удачи!

DLosc
источник
Какой из циклов? Я не видел упоминания об избежании цикла. Потому что для S = 5 есть 3 значения [4, 5, 32], потому что вы можете пойти «1 - 2 - 4 - 1 - 2-4»
JPMC
1
@JPMC Предотвращение цикла подразумевается определением времени остановки. Время остановки 4 равно 2, а не 5, потому что 2 - это «сколько раз вы проходили через функцию Коллатца, прежде чем она достигнет 1».
DLosc
Ах, прости меня. Я думал, что число может иметь несколько времен остановки, так как несколько путей могут привести к нему. Но это было в отношении наращивания с 1, а не работы с Н. Извините за это.
JPMC
1
@DLosc Pyth, конечно.
Исаак
1
Связанные, но не игра в гольф: math.stackexchange.com/q/470782/20792 и math.stackexchange.com/q/1243841/20792
Pureferret

Ответы:

7

Pyth, 26 24 21 байт

Su+yMG-/R3fq4%T6G1Q]1

Этот код работает мгновенно для S=30. Попробуйте сами: демонстрация

Спасибо @isaacg за сохранение 5 байтов.

объяснение

Мой код начинается с 1отмены функции Collatz. Он отображает все номера dна S-1шаг к 2*dи (d-1)/3. Последний в не всегда действителен все же.

                        implicit: Q = input number
                   ]1   start with G = [1]
 u                Q     apply the following function Q-times to G:
                          update G by
   yMG                      each number in G doubled
  +                       +
          fq4%T6G           filter G for numbers T, which satisfy 4==T%6
       /R3                  and divide them by 3
      -          1          and remove 1, if it is in the list
                            (to avoid jumping from 4 to 1)
S                       sort the result and print
Jakube
источник
Это прекрасное использование -F.
Исаак
1
Если вы помещаете - ... 1сумму в сумму уменьшения, вам не нужно уменьшать, чтобы быть .u, ни -Fснаружи. Спасает 2 персонажа.
Исаак
@isaacg Спасибо. Я действительно имел это в предыдущей версии, но удалил это во время отладки ошибки.
Якуб
3
Я позаимствовал @ isaacg для моего собственного ответа. Я часами пытался найти самый короткий код для удаления дубликатов, но это, безусловно, самое элегантное решение. Кроме того, мне действительно нравится использование вами кортежа для отбрасывания недействительных отношений. К сожалению, у CJam нет кортежей, но мне удалось отобразить недействительные коэффициенты в 1.
Деннис
@Jakube q4%d6эквивалентно !%hhd6, но на 1 символ короче.
Исаак
8

Mathematica, 98 92 89 байт

Это решение решает S = 30сразу:

(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

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

Алгоритм - это простой поиск в ширину. Двоюродными братьями Коллатц для данного Sявляются все целые числа, которые могут быть получены из двоюродных братьев Коллатц для S-1через 2*nили нечетных чисел, которые могут быть достигнуты через (n-1)/3. Нам также нужно убедиться, что мы производим только те целые числа, которые были достигнуты впервые после Sшагов, поэтому мы отслеживаем всех предыдущих двоюродных братьев pи удаляем их из результата. Так как мы делаем это в любом случае, мы можем сэкономить несколько байтов, вычисляя шаги от всех предыдущих двоюродных братьев (не только от двоих S-1), чтобы сохранить несколько байтов (что делает его немного медленнее, но не заметно для требуемого S).

Вот немного более читаемая версия:

(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &
Мартин Эндер
источник
5

Python 2, 86 83 75 73 71 байт

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

Звоните как f(30). n = 30почти мгновенно

(Спасибо @DLosc за идею рекурсивного преобразования kв число, а не в список двоюродных братьев и сестер и несколько байтов. Спасибо @isaacg за удаление ~-.)

Этот вариант намного короче, но, к сожалению, занимает слишком много времени из-за экспоненциального ветвления:

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))
Sp3000
источник
Интересно - мое оригинальное решение очень похоже, но ( с парой оптимизаций от вас) выходит 2 байт короче: f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]. Это менее эффективно с вызовами функций, но все равно работает n = 30менее чем за секунду.
DLosc
1
@DLosc Мне понравилась ваша идея, и она стала лучше :)
Sp3000
Ницца! Вот еще 2 байта:f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))
DLosc
@DLosc Ахаха, спасибо. Я все еще клянусь, что должен быть лучший способ короткого замыкания ...
Sp3000
Я думаю, что ~-это не нужно, потому что вы используете целочисленное деление.
Исаак
5

CJam, 29 26 байт

Xari{{2*_Cmd8=*2*)}%1-}*$p

Благодарность принадлежит @isaacg за его идею удалять 1 после каждой итерации, что позволило мне сэкономить два байта напрямую и один косвенно.

Попробуйте онлайн в интерпретаторе CJam (должен закончиться менее чем за секунду).

Как это устроено

Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient 
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))
Деннис
источник
4

CJam, 35 байт

1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p

Объяснение в ближайшее время. Это гораздо более быстрая версия, чем «довольно прямой» подход (см. Его в истории редактирования).

Попробуйте онлайн здесь, для N = 30которого в считанные секунды запускается онлайн-версия и мгновенно в компиляторе Java

оптимизатор
источник
Сколько времени это займет для больших входов? It should finish in seconds or minutes, not hours or days.
DLosc
Ах я вижу. Версия для Python, которую я написал, выглядела примерно 5 часов для N = 30.
DLosc
Последняя версия запускается практически мгновенно.
Оптимизатор
6
В вашем коде есть ошибка. Тест-кейс S=15не работает.
Якуб
3

Java 8, 123

x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray()

Когда x30, программа занимает 15 минут и 29 секунд.

расширенный

class Collatz {
    static IntFunction<long[]> f =
            x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> {
                int n = 0;
                for (; i > 1; n++)
                    i = i % 2 < 1 ? i / 2 : 3 * i + 1;
                return n == x;
            }).toArray();

    public static void main(String[] args) {
        System.out.println(Arrays.toString(f.apply(15)));
    }
}
Ypnypn
источник
Просто любопытно, сколько времени это займет для S = 30?
Geobits
Это работает только в Java 8, правильно? Использование javac 1.7.0_79в Ubuntu дало мне много синтаксических ошибок.
DLosc
@DLosc Correct; Я упомяну это в посте.
Ypnypn
Ограничение состояния терминала цикла i > 1 && ++n <= x(вы также можете отбросить n++) кажется еще более быстрым только для 5 дополнительных символов ... около 3 минут для S = 30 для меня. Это будет безопасно выбрито за минуту, если я .parallel()тоже
включу
1

Python 2, 118 байт

Что ж, я подумал, что не достигну лучшего результата Python, увидев решение @ Sp3000. Но это выглядело как забавная маленькая проблема, поэтому я все равно хотел попробовать независимое решение:

s={1}
for k in range(input()):
 p,s=s,set()
 for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3)
print sorted(s)

То же самое перед удалением пробелов:

s={1}
for k in range(input()):
    p,s=s,set()
    for t in p:
        s.add(2 * t)
        t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3)
print sorted(s)

Это очень прямая реализация поиска в ширину. На каждом шаге мы имеем набор с временем остановки kи получаем набор с временем остановки k + 1, добавляя возможных предшественников каждого значения tв наборе из шага k:

  • 2 * t всегда возможный предшественник.
  • Если tможно записать как 3 * u + 1, где uнечетное число, которого нет 1, то uи предшественник тоже.

N = 30На моем MacBook Pro требуется около 0,02 секунды .

Рето Коради
источник
В общем, s.add(x)в гольфе нет необходимости, так как вы можете сделать это s|={x}вместо этого. Кроме того, использование ~-xвместо (x+1)сохранения на скобках. Но в остальном хорошая работа :)
Sp3000
@ Sp3000 Спасибо. Я не могу легко заменить второе, s.add()потому что оно становится присваиванием и больше не может быть частью выражения. Это работает для первого. В forпетле на основе счетчиков всегда вид многословный , а также. Я думал, что смогу сократить его, используя whileцикл, но он оказался точно такой же длины.
Рето Коради
Вместо forцикла, так как вы не используете ввод каким-либо другим способом, вы, вероятно, можете использовать exec"..."*input()вместо этого :)
Sp3000
1

PHP 5.4+, 178 байт

Функция

function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

Тест и вывод

echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

S (30) выполняется за 0,24 секунды * , возвращает 732 элемента. Пара

86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

* Чтобы сэкономить на байтах, мне приходилось добавлять ksortи array_keysна каждом шагу. Единственный другой выбор, который у меня был, - сделать небольшую функцию-обертку, которая вызывает, c()а затем вызывает array_keysи ksortодин раз результат. Но из-за времени, которое все еще было прилично быстрым, я решил взять удар производительности за малое количество байтов. Без надлежащей сортировки и обработки время в среднем составляет 0,07 секунды для S (30).

Если у кого-нибудь есть какие-нибудь умные способы получить правильную обработку только один раз без слишком большого количества дополнительных байтов, пожалуйста, дайте мне знать! (Я храню свои числа в виде ключей массива, поэтому я использую array_keysи ksort)

JPMC
источник
0

Язык C

#include <stdio.h>
#include <limits.h>    
const int s = 30;

bool f(long i)
{
    int r = 0;
    for(;;)
        if (i < 0 || r > s) return false;
        else if (i == 1) break;
        else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
    return (r==s);
}

void main(){
    for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}
ветреный
источник
5
Привет и добро пожаловать в PPCG! Поскольку это соревнование по коду для игры в гольф , вы должны сделать свой код максимально коротким. Также, пожалуйста, укажите название языка в своем посте.
Алекс А.
Вы можете нажать {}кнопку, чтобы отформатировать ваш код, что я и сделал для вас. Но, как говорит Алекс, пожалуйста, добавьте название языка (C?) И попробуйте сыграть в гольф :) Но добро пожаловать!
Sp3000
@ Sp3000 спасибо за помощь в форматировании кода
ветрено
Функция fне работает должным образом. С s=5, я получаю кучу неверных результатов. if (r == s)return true;должно быть return (r==s), так fкак не вернет ничего значащего, когда (r < s). Кроме того , я думаю , вы должны объявить iв fкачестве long, так как он будет переполнение довольно быстро для некоторых значений.
Деннис
@ Денис спасибо :) это должно бытьreturn (r==s);
ветрено