Hipoteza Collatza (OEIS A006577)

66

Oto hipoteza Collatza (OEIS A006577 ):

  • Zacznij od liczby całkowitej n > 1.
  • Powtórz następujące kroki:
    • Jeśli n jest parzyste, podziel je przez 2.
    • Jeśli n jest nieparzyste, pomnóż go przez 3 i dodaj 1.

Udowodniono, że dla wszystkich liczb całkowitych dodatnich do 5 * 2 60 lub około 5764000000000000000 , n ostatecznie stanie się 1 .

Twoim zadaniem jest dowiedzieć się, ile iteracji potrzeba (o połowę lub trzykrotnie plus jeden), aby osiągnąć 1 .

Odpowiednie xkcd :)

Zasady:

  • Najkrótszy kod wygrywa.
  • Jeśli wprowadzona zostanie liczba <2, liczba całkowita nie będąca liczbą całkowitą lub liczba nieparzysta, wynik nie ma znaczenia.

Przypadki testowe

2  -> 1
16 -> 4
5  -> 5
7  -> 16
code-golf  math 
— Klamka
źródło

Odpowiedzi:

15

C - 50 47 znaków

Złe małe C wymaga niestety okropnej ilości kodu dla podstawowych operacji wejścia / wyjścia, więc zwarcie tego wszystkiego sprawiło, że interfejs użytkownika jest nieco nieintuicyjny.

b;main(a){return~-a?b++,main(a&1?3*a+1:a/2):b;}

Skompiluj to na przykład gcc -o 1 collatz.c. Dane wejściowe są jednoznaczne z cyframi oddzielonymi spacją, a odpowiedź znajdziesz w kodzie wyjścia. Przykład z liczbą 17:

$> ./1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
$> echo $?
12
$>
— Fors
źródło
1
return~-a?zapisuje 1. Również przejście b++do ?skrzynki powinno oszczędzać b--.
— ugoren
Hehe, naginasz zasady tak bardzo: P +1 za kreatywność i używanie języka, który zwykle nie jest używany do gry w golfa
— Klamka
Dziękuję ugoren! Musiałem być pijany, pisząc to. :)
— Fors
12

Perl 34 (+1) znaków

$\++,$_*=$_&1?3+1/$_:.5while$_>1}{

Nadużywanie $\końcowego wyniku, jak zwykle. Uruchom z -popcją wiersza poleceń, dane wejściowe są pobierane z stdin.

Zapisano jeden bajt dzięki Eliasowi Van Ootegem . W szczególności obserwacja, że ​​następujące dwa są równoważne:

$_=$_*3+1
$_*=3+1/$_

Chociaż jeden bajt dłużej, oszczędza dwa bajty, skracając $_/2do just .5.

Przykładowe użycie:

$ echo 176 | perl -p collatz.pl
18

PHP 54 bajty

<?for(;1<$n=&$argv[1];$c++)$n=$n&1?$n*3+1:$n/2;echo$c;

Wygląda na to, że JavaScript w konkursie na drewnianą łyżkę był nieco za krótki w tym wyzwaniu. Jednak z tym problemem nie ma wiele miejsca na kreatywność. Dane wejściowe są traktowane jako argument wiersza poleceń.

Przykładowe użycie:

$ php collatz.php 176
18
— primo
źródło
1
Zajęło mi trochę czasu, aby dowiedzieć się, co robią niezrównane nawiasy kwadratowe :)
— marinus
1
Powtarzanie $_w trójskładnikowego wydaje się marnotrawstwem, można zgolić inną postać za pomocą *=tak: $\++,$_*=$_&1?3+1/$_:.5while$_>1}{. Mnożenie przez 1/$_ma taki sam efekt jak +1, więc $_*=3+1/$_działa dobrze
— Elias Van Ootegem,
@EliasVanOotegem $_*=3+1/$_jest genialny, dzięki!
— primo,
11

Matematyka (35)

If[#>1,#0@If[OddQ@#,3#+1,#/2]+1,0]&

Stosowanie:

If[#>1,#0[If[OddQ@#,3#+1,#/2]]+1,0]&@16
>> 4
— mile
źródło
To nie jest poprawna funkcja, 10.3 narzeka na nieuczciwych @ na końcu
— CalculatorFeline
@ przywołuje argument, nie wiem, dlaczego to był, tylko szybka edycja
— mile
Trzeba uważać :)
— CalculatorFeline
10

Jak zwykle, zacznę od własnych odpowiedzi.

JavaScript, 46 44 znaków (uruchamiane na konsoli)

for(n=prompt(),c=1;n>1;n=n%2?n*3+1:n/2,++c)c
— Klamka
źródło
Jaki jest sens ~~ prompt (), jeśli powiedziałeś, że wynik nie ma znaczenia, jeśli nie jest liczbą całkowitą? Możesz uratować dwie postacie, pozbywając się ~~.
— Resorath
@Resorath Ah, zapomniałem o automatycznym castowaniu JS: P dzięki
— Doorknob
9

Java, 165, 156, 154, 134, 131,129,128 , 126 (pełne języki też potrzebują trochę miłości)

class a{public static void main(String[]a){for(int x=Short.valueOf(a[0]),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y));}}

Wszystko odbywa się wewnątrz for

for(int x=Short.valueOf(a[0]),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y))

To cholernie piękny mężczyzna. Dzięki Pater Taylor !!!, a pomysł użycia pętli for został skradziony z ugoren

W skrócie zastąpiłem Integer.

— Jsedano
źródło
1
Możesz dość łatwo zapisać długość i(,++y). Możesz zaoszczędzić jeszcze dwa, używając <zamiast ==.
— Peter Taylor
@PeterTaylor masz rację, moje porównania będą krótsze z <, ale nie rozumiem części wstępnego przyrostu
— jsedano 1'13
2
Dwie strony drugiego trójskładnika są strukturalnie identyczne, więc możesz wcisnąć trójskładnik w pierwszy argument wywołania rekurencyjnego.
— Peter Taylor
1
O, MOJ BÓG,
— CZYLI BRYLANT
2
Wiem, że to było około 3,5 roku, ale nadal można go golf 5 bajtów : class a{public static void main(String[]a){for(int x=new Short(a[0]),y=0;x>1;System.out.println(++y))x=x%2<1?x/2:x*3+1;}}Zmiany dokonane: 1) Zastępuje Short.valueOf(...)się new Short(...)do -4 bajtów i 2) Mam umieścić x=x%2<1?x/2:x*3+1;w korpusie for-loop aby pozbyć się przecinek za -1 bajt .
— Kevin Cruijssen
9

Rebmu : 28

u[++jE1 AeEV?a[d2A][a1M3a]]j

W przypadku tego krótkiego i mathiego problemu GolfScript prawdopodobnie wygra o pewien procent w stosunku do Rebmu (jeśli nie jest wymagane, aby czytać pliki z Internetu lub generować pliki JPG). Jednak wydaje mi się, że większość zgodziłaby się z logiką Golfscript, która nie jest tak łatwa do naśladowania, a całkowity stos wykonywalny, który ją uruchamia, jest większy.

Chociaż twórca Rebola, Carl Sassenrath, powiedział mi, że uznał Rebmu za „nieczytelnego”, jest zajęty i nie ma czasu, aby naprawdę ćwiczyć transformację typu świnia- latynos poprzez rozproszenie . To naprawdę przekształca się w:

u [
    ++ j
    e1 a: e ev? a [
        d2 a
    ] [
        a1 m3 a
    ]
]
j

Zauważ, że miejsce było wymagane, aby uzyskać a: zamiast a . To jest „słowo-zestaw!” a oceniający zauważa ten typ symbolu, aby uruchomić przypisanie.

Gdyby zostało napisane w skrócie (ale niezręcznie napisany Rebol), dostałbyś:

until [
    ++ j
    1 == a: either even? a [
        divide a 2
    ] [
        add 1 multiply 3 a
    ]
 ]
 j

Rebol, podobnie jak Ruby, ocenia bloki do ich ostatniej wartości. Pętla UNTIL jest ciekawą formą pętli, która nie przyjmuje warunku pętli, po prostu przestaje zapętlać, gdy jej blok ocenia się na wartość NIE FAŁSZ lub BRAK. Tak więc w miejscu, 1 ==w którym wynik przypisania A (argumentu rebmu) do wyniku warunku Collatz (albo jest IF-ELSE, który ocenia wybraną gałąź) ... pętla pęka.

J i K są inicjalizowane na wartość całkowitą zero w Rebmu. I jak już wspomniano, całość ocenia się na ostatnią wartość. Tak więc odniesienie J na końcu programu oznacza liczbę iteracji.

Stosowanie:

>> rebmu/args [u[++jE1 AeEV?a[d2A][a1M3a]]j] 16
== 4
— Dr. Rebmu
źródło
8

Repl. Python, 48

Nie jestem przekonany, że nie ma krótszego wyrażenia niż n=3*n+1;n/=1+n%2*5;. Prawdopodobnie znalazłem kilkanaście różnych wyrażeń o tej samej długości ...

i=0
n=input()
while~-n:n=3*n+1;n/=1+n%2*5;i+=1
i

edytuj: Znalazłem inne rozwiązanie, które nigdy nie będzie rywalizować, ale zbyt zabawne jest, aby się nim nie dzielić.

s='s'
i=s
n=i*input()
while 1:
 while n==n[::2]+n[::2]:i+=s;n=n[::2]
 if n==s:i.rindex(s);break
 n=3*n+s
 i+=s
— boothby
źródło
1
Boli mnie teraz mózg.
— daniero
1
@daniero drugie rozwiązanie jest właśnie dla Ciebie.
— stoisko
Och wow. Jestem zaszczycony!
— daniero
4
(n//2,n*3+1)[n%2]jest krótszy.
— Evpok
1
@Evpok nie n/2działałoby tak dobrze, jak wiemy, że jest w ogóle?
— George
7

APL (31)

A←0⋄A⊣{2⊤⍵:1+3×⍵⋄⍵÷2}⍣{⍺=A+←1}⎕
— marinus
źródło
stara odpowiedź, jednak, 27:{1=⍵:0⋄2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2}
— Uriel
1
{1=⍵:0⋄1+∇⊃⍵⌽0 1+.5 3×⍵}
— ngn
7

J, 30 znaków

<:#-:`(1+3&*)`]@.(2&|+1&=)^:a:

Okazało się nieco dłużej niż pożądane

stosowanie:

   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:2
1
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:16
4
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:5
5
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:7
16
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:27
111

  • -:`(1+3&*)`]to gerunda złożona z trzech czasowników, używanych trzykrotnie. -:oznacza „zmniejsz o połowę” (1+3&*)lub (1+3*])koduje krok pomnożenia i ](tożsamość) pomaga w zakończeniu.

  • 2&|+1&=tworzy indeks do gerunda. dosłownie „reszta po podzieleniu przez dwa plus czy równa się jeden”.

  • #verb^:a:iteruje funkcję, aż wynik będzie stabilny (tutaj, wymuszony jawnie), podczas zbierania kroków, a następnie je zlicza. Skradzione z @JB . <:zmniejsza liczbę kroków o jeden, aby dostosować się do wymagań dotyczących pytania.

— John Dvorak
źródło
6
Ilekroć widzę napis J, liczę uśmieszki. To się robi całkiem dobrze: <:, #-:, :`(, &*), =), )^:.
— primo
3
@primo nice; chcesz ich wyjaśnienia? :-) <:oznacza „zmniejszenie” lub „mniejszy lub równy”, #oznacza „liczbę” lub „n razy”, -:oznacza „połowę” lub „epsilon-równość”, :`(oznacza z kolei koniec wspomnianej „połowy”, związek między dwa czasowniki w gerund i lewy nawias (używane do grupowania). &*)oznacza „coś związane z mnożeniem” (3 połączone z mnożeniem tworzy operator „razy trzy”) i koniec grupowania. =przeprowadza kontrolę równości lub, w jednoznacznym sensie, samoklasyfikację. ^:to koniunkcja mocy (iteracja czasownika). Ponieważ wiele czasowników J kończy się dwukropkiem, ... :-)
— John Dvorak
Lata później ... Ulepszony blok pętli: '- & 2 # (> & 1 * -: + 2 & | * +: +>: @ -:) ^: a:' -> -1 char. : P
— randomra
Więcej lat później ... <:#a:2&(<*|+|6&*%~)19 bajtów (-11)
— mil
6

Schemat Gambit, 106 98 znaków, 40 nawiasów

(let((f(lambda(x)(cond((= x 1) 0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))))(f(read)))

91 89 znaków z definiować bezpośrednio

(define(f x)(cond((= x 1)0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))(f(read))

— Valentin CLEMENT
źródło
Dawno mnie nie było, ale zauważyłem, że zwykle ludzie wysyłają 1 odpowiedź na język programowania.
— jsedano
Przepraszam, nie wiedziałem o tym :)
— Valentin CLEMENT
Edytowane, aby usunąć Python One.
— Valentin CLEMENT
1
Nie prawda! Ludzie mają tendencję do publikowania jednej odpowiedzi na język programowania, ale to dlatego, że starają się nie konkurować bezpośrednio z kimś innym z krótszą odpowiedzią. Ale nikt nie będzie narzekał, jeśli opublikujesz inną odpowiedź w tym samym języku.
— breadbox
@breadbox nieprawda. Wysyłam jedną odpowiedź dla każdego języka, jeśli każde rozwiązanie jest interesujące samo w sobie w porównaniu do drugiego. Jeśli oba rozwiązania są tak interesujące, jak oba razem (ten sam algorytm, brak interesujących sztuczek językowych), umieszczam je jako jedno. Zwykle nie publikuję wielu rozwiązań, ponieważ najpierw wybieram język, a następnie rozwiązuję problem w tym języku - potem zwykle jestem zbyt leniwy, aby pisać to samo w innym języku - lub wyruszam w podróż, aby nauczyć się kolejnego programowania język.
— John Dvorak,
6

PowerShell: 77 74 71 70 61

Kod do gry w golfa:

for($i=(read-host);$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x

Uwagi:

Początkowo próbowałem pobrać dane wejściowe od użytkownika, nie zmuszając go do uzyskania liczby całkowitej, ale zepsuło to w ciekawy sposób. Wszelkie nieparzyste dane wejściowe byłyby przetwarzane niedokładnie, ale nawet dane wejściowe działałyby poprawnie. Zrozumienie, co się dzieje, zajęło mi minutę.

Podczas mnożenia lub dodawania program PowerShell najpierw traktuje wpisane dane jako ciąg. Tak więc '5'*3+1staje się „5551” zamiast 16. Parzyste dane wejściowe zachowywały się dobrze, ponieważ PowerShell nie ma domyślnej akcji dzielącej ciągi znaków. Nawet parzyste dane wejściowe, które przechodziłyby przez liczby nieparzyste, działały dobrze, ponieważ zanim PowerShell osiągnął liczbę nieparzystą w pętli, zmienna była już i tak zmuszona do operacji na liczbach całkowitych.

Dzięki Danko Durbic za zwrócenie uwagi, że mogę po prostu odwrócić operację mnożenia i nie muszę rzutować read-hostna int, ponieważ PowerShell opiera swoje operacje na pierwszym obiekcie.

PowerShell Golfer's Tip: W niektórych scenariuszach, takich jak ten, switchbije if/else. Tutaj różnica wynosiła 2 znaki.

Protip dzięki uprzejmości Danko Durbic : W tym konkretnym scenariuszu zamiast tablicy można użyć tablicy switch, aby zapisać 8 kolejnych znaków!

Nie ma sprawdzania błędów dla wartości niecałkowitych lub liczb całkowitych mniejszych niż dwa.

Jeśli chcesz skontrolować skrypt, umieść go ;$ituż przed ostatnim nawiasem klamrowym w skrypcie.

Nie jestem pewien, jak dobrze PowerShell obsługuje liczby, które przechodzą w bardzo duże wartości, ale spodziewam się, że w pewnym momencie utraci się dokładność. Niestety, spodziewam się również, że niewiele można z tym zrobić bez poważnego rozdęcia scenariusza.

Nieskluczony kod z komentarzami:

# Start for loop to run Collatz algorithm.
# Store user input in $i.
# Run until $i reaches 1.
# Increment a counter, $x, with each run.
for($i=(read-host);$i-ne1;$x++)
{
    # New $i is defined based on an array element derived from old $i.
    $i=(
        # Array element 0 is the even numbers operation.
        ($i/2),
        # Array element 1 is the odd numbers operation.
        (3*$i+1)
    # Array element that defines the new $i is selected by $i%2.
    )[$i%2]
}

# Output $x when the loop is done.
$x

# Variable cleanup. Don't include in golfed code.
rv x,i

Przypadki testowe:

Poniżej kilka przykładów z włączoną kontrolą. Zredagowałem również dane wyjściowe dla większej przejrzystości, dodając etykiety do danych wejściowych i końcowych oraz wstawiając odstępy, aby rozdzielić wartości Collatz.

---
Input: 2

1

Steps: 1

---
Input: 16

8
4
2
1

Steps: 4

---
Input: 5

16
8
4
2
1

Steps: 5

---
Input: 7

22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 16

---
Input: 42

21
64
32
16
8
4
2
1

Steps: 8

---
Input: 14

7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 17

---
Input: 197

592
296
148
74
37
112
56
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 26

---
Input: 31

94
47
142
71
214
107
322
161
484
242
121
364
182
91
274
137
412
206
103
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Steps: 106

---
Input: 6174

3087
9262
4631
13894
6947
20842
10421
31264
15632
7816
3908
1954
977
2932
1466
733
2200
1100
550
275
826
413
1240
620
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Steps: 111

---
Input: 8008135

24024406
12012203
36036610
18018305
54054916
27027458
13513729
40541188
20270594
10135297
30405892
15202946
7601473
22804420
11402210
5701105
17103316
8551658
4275829
12827488
6413744
3206872
1603436
801718
400859
1202578
601289
1803868
901934
450967
1352902
676451
2029354
1014677
3044032
1522016
761008
380504
190252
95126
47563
142690
71345
214036
107018
53509
160528
80264
40132
20066
10033
30100
15050
7525
22576
11288
5644
2822
1411
4234
2117
6352
3176
1588
794
397
1192
596
298
149
448
224
112
56
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 93
---

Interesujące bity na temat liczb wejściowych, które nie pochodzą z przypadków testowych pytania:

— Iszi
źródło
2
Miły! Nadal można go nieco skrócić, zastępując switchz$i=(($i/2),($i*3+1))[$i%2]
— Danko Durbić
2
Nie musisz też konwertować read-hostna liczbę - wystarczy zmienić $i*3na 3*$i.
— Danko Durbić
Tablica zamiast przełącznika? Znakomity! I zamiana $i*3- dlaczego już o tym nie pomyślałem?
— Iszi
1
param($i)for(;$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x- zamień read-host na parametr, aby uzyskać 56 bajtów . Wypróbuj Online link
— TessellatingHeckler
6

80386, 16 bajtów

W tym przykładzie użyto składni AT&T i konwencji wywoływania fastcall, argument dotyczy ecx:

collatz:
        or $-1,%eax              # 3 bytes, eax = -1;
.Loop:  inc %eax                 # 1 byte,  eax += 1;
        lea 1(%ecx,%ecx,2),%edx  # 4 bytes, edx = 3*ecx + 1;
        shr %ecx                 # 2 bytes, CF = ecx & 1;
                                 #          ecx /= 2;
                                 #          ZF = ecx == 0;
        cmovc %edx,%ecx          # 3 bytes, if (CF) ecx = edx;
        jnz .Loop                # 2 bytes, if (!ZF) goto .Loop;
        ret                      # 1 byte,  return (eax);

Oto wynikowe 16 bajtów kodu maszynowego:

83 c8 ff 40 8d 54 49 01 d1 e9 0f 42 ca 75 f4 c3
— FUZxxl
źródło
6

Brachylog , 16 bajtów

1b|{/₂ℕ|×₃+₁}↰+₁

Wypróbuj online!

Wyjaśnienie

         Either:
  1        The input is 1.
  b        In which case we unify the output with 0 by beheading the 1
           (which removes the leading digit of the 1, and an "empty integer"
           is the same as zero).
|        Or:
  {        This inline predicate evaluates a single Collatz step on the input.
           Either:
    /₂       Divide the input by 2.
    ℕ        And ensure that the result is a natural number (which is
             equivalent to asserting that the input was even).
  |        Or:
    ×₃+₁     Multiply the input by 3 and add 1.
  }
  ↰        Recursively call the predicate on this result.
  +₁       And add one to the output of the recursive call.

Alternatywne rozwiązanie przy tej samej liczbie bajtów:

;.{/₂ℕ|×₃+₁}ⁱ⁾1∧

Wypróbuj online!

;.          The output of this is a pair [X,I] where X is the input and
            I will be unified with the output.
{/₂ℕ|×₃+₁}  This is the Collatz step predicate we've also used above.
ⁱ⁾          We iterate this predicate I times on X. Since we haven't actually
            specified I, it is still a free variable that Brachylog can backtrack
            over and it will keep adding on iterations until the next
            constraint can be satisfied.
1           Require the result of the iteration to be 1. Once this is
            satisfied, the output variable will have been unified with
            the minimum number of iterations to get here.
∧           This AND is just used to prevent the 1 from being implicitly
            unified with the output variable as well.
— Martin Ender
źródło
5

F # - 65 znaków

let rec c n=function 1->n|i->c(n+1)(if i%2=0 then i/2 else i*3+1)
— Daniel
źródło
5

Python 68 58 54 52 znaków

f=lambda n:1+(n-2and f((n/2,3*n+1)[n%2]));f(input())

Dzięki Bakuriu i stoisku za wskazówki :)

— Valentin CLEMENT
źródło
Możesz użyć, n%2and 3*n+1or n/2aby zapisać 5 znaków. Również w python2 możesz usunąć wywołanie int, zmniejszając rozmiar do 58 bajtów.
— Bakuriu
Och, można nawet dostać krótszy niż: [n/2,3*n+1][n%2].
— stoisko
To fajne!
— Valentin CLEMENT,
Czy to python 2.7? Pojawia się błąd w Pythonie 3.5.1? unsupported operand type(s) for -: 'str' and 'int'
— George
5

Siatkówka , 43 bajty

11
2
(2+)1
$1$1$0$0$0$0
2.*
$0x
)`2
1
1?x
1

Pobiera dane wejściowe i drukuje dane wyjściowe jako jednoargumentowy.

Każda linia powinna przejść do własnego pliku. 1 bajt na dodatkowy plik dodany do liczby bajtów.

Możesz uruchomić kod jako jeden plik z -sflagą. Na przykład:

> echo -n 1111111|retina -s collatz
1111111111111111

Algorytm to pętla wykonywania kroku Collatza z jednoznaczną liczbą i dodawania nowego znacznika kroku xna końcu łańcucha, jeśli liczba nie jest równa 1.

Kiedy pętla kończy się na 1, konwertujemy znaczniki na liczbę pojedynczą (usuwając wiodące 1), co jest pożądanym wyjściem.

— randomra
źródło
5

Galaretka , niekonkurująca

12 bajtów Ta odpowiedź nie konkuruje, ponieważ wyzwanie poprzedza powstanie galaretki.

×3‘$HḂ?ß0’?‘

Wypróbuj online!

Jak to działa

×3‘$HḂ?ß0’?‘  Main link. Argument: n (integer)

     Ḃ?       Yield the last bit of n is 1:
   $            Evaluate the three links to the left as a monadic chain:
×3                Multiply n by 3.
  ‘               Increment the product by 1.
    H           Else, halve n.
         ’?   If n-1 is non-zero:
       ß        Recursively call the main link.
        0     Else, yield 0.
           ‘  Increment the result by 1.
— Dennis
źródło
4

dc, 27 znaków

Zastosowanie czarnej magii boothby :

?[d3*1+d2%5*1+/d1<x]dsxxkzp

Nie jestem pewien, czy rozumiem, w jaki sposób - albo że - to działa.

Stosowanie: 
$ dc collatz.dc <<< 7
16

dc, 36 znaków

Moje własne stworzenie; nieco bardziej tradycyjne podejście, chociaż musiałem dość pokłócić się z językiem, aby przezwyciężyć brak elseczęści ifwypowiedzi:

?[2/2Q]se[dd2%[0=e3*1+]xd1<x]dsxxkzp

Wewnętrznie generuje wszystkie liczby sekwencji i zapisuje je na stosie, a następnie wyskakuje na końcu 1i wyświetla wysokość stosu.

— daniero
źródło
1
Parzystość nie jest czarną magią.
— stoisko
1
Nie, ale jest to bardzo fajna sztuczka! Sam zrobiłem podobne rzeczy, po prostu nie pomyślałem o tym w tym przypadku. Na sekundę natknąłem się na podział, ale rozumiem: dzielisz przez sześć, odwracając pierwszą operację (* = 3, + = 1) z drugą, jeśli parzystość była niepoprawna, a z powodu podziału na liczby całkowite dodawanie idzie z dala, i właściwie zrobiliśmy / = 2. Bardzo sprytne :)
— daniero
1
+1. Myślałem, że zmiażdżę to wyzwanie za pomocą prądu stałego, ale dotarłem tylko do 40. Widziałem twoją 27 odpowiedź. No cóż.
— Cyfrowa trauma
Nie widziałem tego wyzwania, ale napisałem na blogu jakiś czas temu o drukowaniu sekwencji Collatz w DC. Moje podejście jest podobne do twojego, ale traci bajt, więc tak naprawdę nie widzę powodu, aby to opublikować. Jednak, gdy patrzyłem na mój, aby zobaczyć, jak łatwo przejść od drukowania każdego kroku do drukowania liczby kroków, zauważyłem coś, co może zagrać w bajt z twojego ... Ponieważ sekwencja Collatza zawsze będzie wynosiła od 2 do 1, możesz zmienić swoje warunki 2<xi się go pozbyć k. Na wypadek, gdybyś chciał odzyskać bajt po czterech latach. : D
— brhfl
4

pieprzenie mózgu , 59 56 bajtów

,-[<->[[>]+<[-<]>>]>[-<<[++>+<]>->]<<[+>+++<]<<+>>>]<<<.

Wypróbuj online! (Lekko zmodyfikowany dla łatwości użycia)

Wejście i wyjście jako kody znaków. Jest to bardziej przydatne w przypadku komórek o dowolnym rozmiarze, ale nadal może działać z małymi wartościami w ograniczonych rozmiarach komórek.

Jak to działa

Tape Format:
Counter 0 Copy Number Binary...
^End           ^Start

,-[ Get input, decrement by 1 and start loop
  <->                  Initialises the copy of the value at -1
  [[>]+<[-<]>>]        Converts the input to binary while preserving a negative copy
  <+>>[-<<[++>+<]>->] If the last digit of the binary is 1 (n-1 is odd), divide by 2 and decrement
  <<[+>+++<]            If the last digit of the binary is 0 (n-1 is even), multiply by 3
  <<+>>>               Increment counter and end on n-1
]<<<.                 End loop and print counter
— Jo King
źródło
4

Sześciokąt , 48 44 bajtów

?(]$_)"){{?{*')}/&!/={:<$["/>&_(.<@2'%<>./>=

Wypróbuj online!

Rozszerzony:

     ? ( ] $ _
    ) " ) { { ?
   { * ' ) } / &
  ! / = . { < $ [
 " / > & _ ( . < @
  2 ' % < > : / >
   = . . . . . .
    . . . . . .
     . . . . .

Pamiętaj, że to się nie udaje z 1... hmm ... powodów . Szczerze mówiąc, nie jestem już pewien, jak to działa. Wiem tylko, że kod dla liczb nieparzystych jest uruchamiany wstecz dla liczb parzystych? Jakoś?

Nowa wersja jest znacznie czystsza od poprzedniej, ale ma kilka dodatkowych kierunków w porównaniu, a także kończy się błędem dzielenia przez zero. Jedyny przypadek, w którym nie popełni błędu, to fakt, że faktycznie obsługuje 1poprawnie.

— Jo King
źródło
If a number < 2 is input ... output does not matter.: o)
— Sok
@Sok Tak, dlatego opublikowałem to zamiast wariować próbując to naprawić
— Jo King
3

C, 70 69 znaków

Całkiem proste, żadnych sztuczek.
Odczytuje dane wejściowe ze standardowego wejścia.

a;
main(b){
    for(scanf("%d",&b);b-1;b=b%2?b*3+1:b/2)a++;
    printf("%d",a);
}
— ugoren
źródło
3

Ruby 1.9, 49 znaków

Rubyfikowana odpowiedź Valentina CLEMENT na Python , przy użyciu stabilnej składni lambda. Sqeezed to w jedną instrukcję dla dodatkowej nieczytelności.

(f=->n{n>1&&1+f[[n/2,3*n+1][n%2]]||0})[gets.to_i]

Niektóre koszty ogólne, ponieważ Ruby, w przeciwieństwie do Pythona, nie jest zadowolona z mieszania liczb z booleanami.

— daniero
źródło
3

C ++ ( 51 48)

Jest to funkcja rekurencyjna, która to robi; odczyt wejściowy jest dostarczany osobno.

int c(n){return n==1?0:1+(n%2?c(n*3+1):c(n/2));}

Jestem pewien, że mogę zrobić coś w tym rodzaju „i / lub” == 0, ale nie mam pojęcia, jak to zrobić.

— Joe Z.
źródło
Możesz usunąć ==0i zamienić boki warunkowego
— Klamka
Poza tym nie trzeba się tym zajmować, n==1ponieważ w pytaniu podałem, że liczba jest zawsze większa niż 1
— Klamka
Problem polega na tym, że n==1jest to podstawowy przypadek rekurencji. Umieszczenie n==2tam nie poprawiłoby wyniku.
— Joe Z.
Ach, wtedy możesz po prostu zastąpić to tym: return~-n?i zamienić strony warunkowe
— Klamka
. n==1== n<2.
— CalculatorFeline
3

~ - ~! (Bez komentarza) - 71 53

Ten język oczywiście nie jest najlepszy do gry w golfa, ponieważ brakuje mu dużej liczby natywnych funkcji, ale to jest jego piękno.

'=|*;~~[*,~~~-~]*/~~|:''=|'''==~[*]'''='&''':''&*+~|:

Najpierw ustaw '''dane wejściowe. Funkcja ''może być następnie wywołana za pomocą %jako, gdy jest wprowadzana i zwróci odpowiedź, tak jak:

'''=~~~~~:''&%:

To wróci ~~~~~. To faktycznie działa dla n==1(zawsze zapętla się n==0).

Jak zawsze w tym języku, niesprawdzony.

— cjfaure
źródło
3

JavaScript (ES6) - 29 znaków

f=x=>x>1?f(x%2?x*3+1:x/2)+1:0

Tworzy funkcję, fktóra akceptuje pojedynczy argument i zwraca liczbę iteracji.

JavaScript - 31 znaków

for(c=0;n>1;n=n%2?n*3+1:n/2)++c

Zakłada, że ​​dane wejściowe znajdują się w zmiennej ni tworzy zmienną, cktóra zawiera liczbę iteracji (i będzie również wysyłana cdo konsoli jako jej ostatnie polecenie).

— MT0
źródło
1
— Kudłaty
3

Perl 6, 40 bajtów

Metoda funkcji rekurencyjnej, zgodnie z Valentin CLEMENT i daniero : 40 znaków

sub f(\n){n>1&&1+f n%2??3*n+1!!n/2}(get)

Metoda listy leniwej: 32 znaki

+(get,{$_%2??$_*3+1!!$_/2}...^1)
— Mouq
źródło
3

> <>, 27 26 23 bajtów

\ln;
\::2%:@5*1+2,*+:2=?

Podobnie jak inne odpowiedzi> <>, buduje to sekwencję na stosie. Gdy sekwencja osiągnie 2, rozmiar stosu jest liczbą wykonanych kroków.

Dzięki @Hohmannfan zaoszczędzono 3 bajty dzięki bardzo sprytnej metodzie bezpośredniego obliczenia następnej wartości. Wzór zastosowany do obliczenia następnej wartości w sekwencji to:

f(n)=n⋅5(nmod2)+12+(nmod2)

Ułamek odwzorowuje liczby parzyste na 0,5, a nieparzyste na 3. Mnożenie przez ni dodawanie n%2kończy obliczenia - nie trzeba wcale wybierać następnej wartości!

Edycja 2: Oto wersja przed @ Hohmannfan:

\ln;
\:::3*1+@2,@2%?$~:2=?

Sztuką jest to, że oba 3n+1i n/2są obliczane na każdym kroku w sekwencji, a ten należy spadł z sekwencja jest wybrana później. Oznacza to, że kod nie musi rozgałęziać się, dopóki nie zostanie osiągnięty 1, a obliczenie sekwencji może istnieć w jednym wierszu kodu.

Edycja: Zignorowałem inną postać po uświadomieniu sobie, że jedyną dodatnią liczbą całkowitą, która może prowadzić do 1, jest 2. Ponieważ wyjście programu nie ma znaczenia dla danych wejściowych <2, generowanie sekwencji może zakończyć się po osiągnięciu 2, pozostawiając rozmiar stosu będąca dokładną liczbą wymaganych kroków.

Wersja poprzednia:

\~ln;
\:::3*1+@2,@2%?$~:1=?
— Sok
źródło
1
Możesz \::2%:@5*1+2,*+:2=?
— zagrać w
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.