language-agnostic - 代码高尔夫：科拉茨猜想

Question

受http://xkcd.com/710/的启发，这里有一个代码高尔夫。

挑战

给定一个大于 0 的正整数，打印出该数字的冰雹序列。

冰雹序列

有关更多详细信息，请参见维基百科。

• 如果是偶数，则除以二。
• 如果数字是奇数，则将其增加三倍并加一。

对产生的数字重复此操作，直到它达到 1。（如果它在 1 之后继续，它将进入无限循环1 -> 4 -> 2 -> 1...）

有时代码是最好的解释方式，所以这里有一些来自维基百科

function collatz(n)
  show n
  if n > 1
    if n is odd
      call collatz(3n + 1)
    else
      call collatz(n / 2)

这段代码有效，但我增加了一个额外的挑战。程序不能容易受到堆栈溢出的影响。所以它必须要么使用迭代，要么使用尾递归。

此外，如果它可以计算大数字并且该语言尚未实现它，则可以加分。（或者如果您使用固定长度整数重新实现大数字支持）

测试用例

Number: 21
Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

此外，代码 Golf 必须包含完整的用户输入和输出。

Answer 1

x86 程序集，1337 个字符

;
; To assemble and link this program, just run:
;
; >> $ nasm -f elf collatz.asm && gcc -o collatz collatz.o
;
; You can then enjoy its output by passing a number to it on the command line:
;
; >> $ ./collatz 123
; >> 123 --> 370 --> 185 --> 556 --> 278 --> 139 --> 418 --> 209 --> 628 --> 314
; >> --> 157 --> 472 --> 236 --> 118 --> 59 --> 178 --> 89 --> 268 --> 134 --> 67
; >> --> 202 --> 101 --> 304 --> 152 --> 76 --> 38 --> 19 --> 58 --> 29 --> 88
; >> --> 44 --> 22 --> 11 --> 34 --> 17 --> 52 --> 26 --> 13 --> 40 --> 20 --> 10
; >> --> 5 --> 16 --> 8 --> 4 --> 2 --> 1
; 
; There's even some error checking involved:
; >> $ ./collatz
; >> Usage: ./collatz NUMBER
;
section .text
global main
extern printf
extern atoi

main:

  cmp dword [esp+0x04], 2
  jne .usage

  mov ebx, [esp+0x08]
  push dword [ebx+0x04]
  call atoi
  add esp, 4

  cmp eax, 0
  je .usage

  mov ebx, eax
  push eax
  push msg

.loop:
  mov [esp+0x04], ebx
  call printf

  test ebx, 0x01
  jz .even

.odd:
  lea ebx, [1+ebx*2+ebx]
  jmp .loop

.even:

  shr ebx, 1
  cmp ebx, 1
  jne .loop

  push ebx
  push end
  call printf

  add esp, 16
  xor eax, eax
  ret

.usage:
  mov ebx, [esp+0x08]
  push dword [ebx+0x00]
  push usage
  call printf
  add esp, 8
  mov eax, 1
  ret

msg db "%d --> ", 0
end db "%d", 10, 0
usage db "Usage: %s NUMBER", 10, 0

Answer 2

贝芬吉

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+

Answer 3

LOLCODE：406 字符

HAI
BTW COLLATZ SOUNDZ JUS LULZ

CAN HAS STDIO?

I HAS A NUMBAR
BTW, I WANTS UR NUMBAR
GIMMEH NUMBAR

VISIBLE NUMBAR

IM IN YR SEQUENZ
  MOD OF NUMBAR AN 2
  BOTH SAEM IT AN 0, O RLY?
    YA RLY, NUMBAR R QUOSHUNT OF NUMBAR AN 2
    NO WAI, NUMBAR R SUM OF PRODUKT OF NUMBAR AN 3 AN 1
  OIC
  VISIBLE NUMBAR
  DIFFRINT 2 AN SMALLR OF 2 AN NUMBAR, O RLY?
    YA RLY, GTFO
  OIC
IM OUTTA YR SEQUENZ

KTHXBYE

经JUSTIN J. MEZA 口译员测试。再见！

Answer 4

蟒蛇 - 95 64 51 46 字符

显然不会产生堆栈溢出。

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n

Answer 5

Haskell, 62 个字符63 76 83 , 86 , 97 , 137

c 1=[1]
c n=n:c(div(n`mod`2*(5*n+2)+n)2)
main=readLn>>=print.c

用户输入，打印输出，使用常量内存和堆栈，使用任意大的整数。

这个代码的示例运行，给定一个 80 位数的所有 '1' (!) 作为输入，看起来很有趣。

---

原始，仅功能版本：

Haskell 51个字符

f n=n:[[],f([n`div`2,3*n+1]!!(n`mod`2))]!!(1`mod`n)

无论如何，@&^# 谁需要条件？

（编辑：我很“聪明”并使用了修复。没有它，代码下降到 54 个字符。edit2：通过分解下降到 51 f()）

Answer 6

Perl

我决定有点反竞争，并展示您通常如何在 Perl 中编写此类问题。
_{最后还有一个 46（总）字符代码高尔夫条目。}

前三个示例都以此标题开头。

#! /usr/bin/env perl
use Modern::Perl;
# which is the same as these three lines:
# use 5.10.0;
# use strict;
# use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}

• 简单的递归版本

  use Sub::Call::Recur;
  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;
    die 'Integer values only' unless $n == int $n;
    say $n;
    given( $n ){
      when( 1 ){}
      when( $_ % 2 != 0 ){ # odd
        recur( 3 * $n + 1 );
      }
      default{ # even
        recur( $n / 2 );
      }
    }
  }
  

• 简单的迭代版本

  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;
    die 'Integer values only' unless $n == int $n;
    say $n;
    while( $n > 1 ){
      if( $n % 2 ){ # odd
        $n = 3 * $n + 1;
      } else { #even
        $n = $n / 2;
      }
      say $n;
    }
  }
  

• 优化迭代版本

  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;
    die 'Integer values only' unless $n == int $n;
    #
    state @next;
    $next[1] //= 0; # sets $next[1] to 0 if it is undefined
    #
    # fill out @next until we get to a value we've already worked on
    until( defined $next[$n] ){
      say $n;
      #
      if( $n % 2 ){ # odd
        $next[$n] = 3 * $n + 1;
      } else { # even
        $next[$n] = $n / 2;
      }
      #
      $n = $next[$n];
    }
    say $n;
    # finish running until we get to 1
    say $n while $n = $next[$n];
  }
  

---

现在我将展示如何使用 v5.10.0 之前的 Perl 版本来完成最后一个示例

#! /usr/bin/env perl
use strict;
use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}
{
  my @next = (0,0); # essentially the same as a state variable
  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;

    # fill out @next until we get to a value we've already worked on
    until( $n == 1 or defined $next[$n] ){
      print $n, "\n";

      if( $n % 2 ){ # odd
        $next[$n] = 3 * $n + 1;
      } else { # even
        $next[$n] = $n / 2;
      }
      $n = $next[$n];
    }
    print $n, "\n";

    # finish running until we get to 1
    print $n, "\n" while $n = $next[$n];
  }
}

---

基准

首先，IO 总是很慢的部分。因此，如果您实际上按原样对它们进行基准测试，您应该从每个测试中获得大致相同的速度。

然后为了测试这些，我打开了/dev/null( $null) 的文件句柄，并编辑了每个文件say $n以改为读取say {$null} $n. 这是为了减少对IO的依赖。

#! /usr/bin/env perl
use Modern::Perl;
use autodie;

open our $null, '>', '/dev/null';

use Benchmark qw':all';

cmpthese( -10,
{
  Recursive => sub{ Collatz_r( 31 ) },
  Iterative => sub{ Collatz_i( 31 ) },
  Optimized => sub{ Collatz_o( 31 ) },
});

sub Collatz_r{
  ...
  say {$null} $n;
  ...
}
sub Collatz_i{
  ...
  say {$null} $n;
  ...
}
sub Collatz_o{
  ...
  say {$null} $n;
  ...
}

运行 10 次后，这是一个有代表性的示例输出：

            速率递归迭代优化
递归 1715/s -- -27% -46%
迭代 2336/s 36% -- -27%
优化 3187/s 86% 36% --

---

最后，一个真正的代码高尔夫条目：

perl -nlE'say;say$_=$_%2?3*$_+1:$_/2while$_>1'

共 46 个字符

如果您不需要打印起始值，则可以再删除 5 个字符。

perl -nE'say$_=$_%2?3*$_+1:$_/2while$_>1'

实际代码部分共有 41 个字符，总共31 个字符，但如果没有_{开关
，代码将无法工作。-n因此，我将整个示例包括在我的计数中。}

Answer 7

Golfscript : 20 个字符

  ~{(}{3*).1&5*)/}/1+`
# 
# Usage: echo 21 | ruby golfscript.rb collatz.gs

这相当于

stack<int> s;
s.push(21);
while (s.top() - 1) {
  int x = s.top();
  int numerator = x*3+1;
  int denominator = (numerator&1) * 5 + 1;
  s.push(numerator/denominator);
}
s.push(1);
return s;

Answer 8

公元前 41 个字符

我想这种问题是bc发明的：

for(n=read();n>1;){if(n%2)n=n*6+2;n/=2;n}

测试：

bc1 -q collatz.bc
21
64
32
16
8
4
2
1

正确的代码：

for(n=read();n>1;){if(n%2)n=n*3+1else n/=2;print n,"\n"}

bc处理最多INT_MAX位数的数字

编辑：维基百科文章提到这个猜想已经检查了所有高达20x2 ⁵⁸的值（aprox. 5.76e18）。这个程序：

c=0;for(n=2^20000+1;n>1;){if(n%2)n=n*6+2;n/=2;c+=1};n;c

在68秒、144,404个周期内测试2 ^20,000 +1（大约 3.98e6,020 ）。

Answer 9

Perl：31 个字符

perl -nE 'say$_=$_%2?$_*3+1:$_/2while$_>1'
#         123456789 123456789 123456789 1234567

编辑删除 2 个不必要的空格。

编辑删除 1 个不必要的空间。

Answer 10

MS Excel，35 个字符

=IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)

直接取自维基百科：

In cell A1, place the starting number.
In cell A2 enter this formula =IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1) 
Drag and copy the formula down until 4, 2, 1

只需复制/粘贴公式 111 次即可获得起始数字为 1000 的结果。;)

Answer 11

C : 64 个字符

main(x){for(scanf("%d",&x);x>=printf("%d,",x);x=x&1?3*x+1:x/2);}

支持大整数：431（必要）字符

#include <stdlib.h>
#define B (w>=m?d=realloc(d,m=m+m):0)
#define S(a,b)t=a,a=b,b=t
main(m,w,i,t){char*d=malloc(m=9);for(w=0;(i=getchar()+2)/10==5;)
B,d[w++]=i%10;for(i=0;i<w/2;i++)S(d[i],d[w-i-1]);for(;;w++){
while(w&&!d[w-1])w--;for(i=w+1;i--;)putchar(i?d[i-1]+48:10);if(
w==1&&*d==1)break;if(*d&1){for(i=w;i--;)d[i]*=3;*d+=1;}else{
for(i=w;i-->1;)d[i-1]+=d[i]%2*10,d[i]/=2;*d/=2;}B,d[w]=0;for(i=0
;i<w;i++)d[i+1]+=d[i]/10,d[i]%=10;}}

注意：不要#include <stdlib.h>在没有至少原型 malloc/realloc 的情况下删除，因为这样做在 64 位平台上是不安全的（64 位 void* 将转换为 32 位 int）。

这个还没有经过激烈的测试。它也可以使用一些缩短。

---

之前的版本：

main(x){for(scanf("%d",&x);printf("%d,",x),x-1;x=x&1?3*x+1:x/2);} // 66

（删除了 12 个字符，因为没有人遵循输出格式...：|）

Answer 12

另一个汇编器版本。这个不限于 32 位数字，它可以处理高达 10 ⁶⁵⁵³⁴的数字，尽管 MS-DOS 使用的“.com”格式仅限于 80 位数字。为 A86 汇编程序编写，需要 Win-XP DOS 框才能运行。汇编为 180 字节：

    mov ax,cs
    mov si,82h
    add ah,10h
    mov es,ax
    mov bh,0
    mov bl,byte ptr [80h]
    cmp bl,1
    jbe ret
    dec bl
    mov cx,bx
    dec bl
    xor di,di
 p1:lodsb
    sub al,'0'
    cmp al,10
    jae ret
    stosb
    loop p1
    xor bp,bp
    push es
    pop ds
 p2:cmp byte ptr ds:[bp],0
    jne p3
    inc bp
    jmp p2
    ret
 p3:lea si,[bp-1]
    cld
 p4:inc si
    mov dl,[si]
    add dl,'0'
    mov ah,2
    int 21h
    cmp si,bx
    jne p4
    cmp bx,bp
    jne p5
    cmp byte ptr [bx],1
    je ret
 p5:mov dl,'-'
    mov ah,2
    int 21h
    mov dl,'>'
    int 21h
    test byte ptr [bx],1
    jz p10
    ;odd
    mov si,bx
    mov di,si
    mov dx,3
    dec bp
    std
 p6:lodsb
    mul dl
    add al,dh
    aam
    mov dh,ah
    stosb
    cmp si,bp
    jnz p6
    or dh,dh
    jz p7
    mov al,dh
    stosb
    dec bp
 p7:mov si,bx
    mov di,si
 p8:lodsb
    inc al
    xor ah,ah
    aaa
    stosb
    or ah,ah
    jz p9
    cmp si,bp
    jne p8
    mov al,1
    stosb
    jmp p2
 p9:inc bp
    jmp p2
    p10:mov si,bp
    mov di,bp
    xor ax,ax
p11:lodsb
    test ah,1
    jz p12
    add al,10
p12:mov ah,al
    shr al,1
    cmp di,bx
    stosb
    jne p11
    jmp p2

Answer 13

dc - 24 个字符25 28

dc是这个序列的好工具：

?[d5*2+d2%*+2/pd1<L]dsLx

dc -f collat​​z.dc
21
64
32
16
8
4
2
1

使用Golfscript条目中的公式还有 24 个字符：

?[3*1+d2%5*1+/pd1<L]dsLx

符合规格的57 个字符：

[Number: ]n?[Results: ]ndn[d5*2+d2%*+2/[ -> ]ndnd1<L]dsLx

dc -f collat​​z-spec.dc
数量：3
结果：3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Answer 14

方案：72

(define(c n)(if(= n 1)`(1)(cons n(if(odd? n)(c(+(* n 3)1))(c(/ n 2))))))

这使用递归，但调用是尾递归的，所以我认为它们会针对迭代进行优化。在一些快速测试中，我始终无法找到堆栈溢出的数字。举个例子：

(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)

...运行得很好。[这都是一个数字——我刚刚把它弄坏了，以适应屏幕。]

Answer 15

数学，4550字符

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&

Answer 16

Python 45 Char

Shaved a char off of makapuf's answer.

n=input()
while~-n:n=(n/2,n*3+1)[n%2];print n

Answer 17

Ruby，50 个字符，没有堆栈溢出

基本上是makapuf 的 Python 解决方案的直接翻录：

def c(n)while n>1;n=n.odd?? n*3+1: n/2;p n end end

Ruby，45 个字符，会溢出

基本上是问题中提供的代码的直接翻录：

def c(n)p n;n.odd?? c(3*n+1):c(n/2)if n>1 end

Answer 18

import java.math.BigInteger;
public class SortaJava {

    static final BigInteger THREE = new BigInteger("3");
    static final BigInteger TWO = new BigInteger("2");

    interface BiFunc<R, A, B> {
      R call(A a, B b);
    }

    interface Cons<A, B> {
      <R> R apply(BiFunc<R, A, B> func);
    }

    static class Collatz implements Cons<BigInteger, Collatz> {
      BigInteger value;
      public Collatz(BigInteger value) { this.value = value; }
      public <R> R apply(BiFunc<R, BigInteger, Collatz> func) {
        if(BigInteger.ONE.equals(value))
          return func.call(value, null);
        if(value.testBit(0))
          return func.call(value, new Collatz((value.multiply(THREE)).add(BigInteger.ONE)));
        return func.call(value, new Collatz(value.divide(TWO)));
      }
    }

    static class PrintAReturnB<A, B> implements BiFunc<B, A, B> {
      boolean first = true;
      public B call(A a, B b) {
        if(first)
          first = false;
        else
          System.out.print(" -> ");
        System.out.print(a);
        return b;
      }
    }

    public static void main(String[] args) {
      BiFunc<Collatz, BigInteger, Collatz> printer = new PrintAReturnB<BigInteger, Collatz>();
      Collatz collatz = new Collatz(new BigInteger(args[0]));
      while(collatz != null)
        collatz = collatz.apply(printer);
    }
}

Answer 19

TI-BASIC

不是最短的，而是一种新颖的方法。大序列肯定会大大减慢速度，但它不应该溢出。

PROGRAM:COLLATZ
:ClrHome
:Input X
:Lbl 1
:While X≠1
:If X/2=int(X/2)
:Then
:Disp X/2→X
:Else
:Disp X*3+1→X
:End
:Goto 1
:End

Answer 20

红宝石，43 个字符

支持 bignum，具有堆栈溢出敏感性：

def c(n)p n;n%2>0?c(3*n+1):c(n/2)if n>1 end

...和 ​​50 个字符，支持 bignum，没有堆栈溢出：

def d(n)while n>1 do p n;n=n%2>0?3*n+1:n/2 end end

向乔丹致敬。我不知道“p”可以代替puts。

Answer 21

诺夫¹

运行nroff -U hail.g

.warn
.pl 1
.pso (printf "Enter a number: " 1>&2); read x; echo .nr x $x
.while \nx>1 \{\
.  ie \nx%2 .nr x \nx*3+1
.  el .nr x \nx/2
\nx
.\}

---

^{1. groff 版本}

Answer 22

C#：216 个字符

using C=System.Console;class P{static void Main(){var p="start:";System.Action<object> o=C.Write;o(p);ulong i;while(ulong.TryParse(C.ReadLine(),out i)){o(i);while(i > 1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}o("\n"+p);}}}

长篇：

using C = System.Console;
class P
{
    static void Main()
    {
        var p = "start:"; 
        System.Action<object> o = C.Write; 
        o(p); 
        ulong i; 
        while (ulong.TryParse(C.ReadLine(), out i))
        {
            o(i); 
            while (i > 1)
            {
                i = i % 2 == 0 ? i / 2 : i * 3 + 1; 
                o(" -> " + i);
            } 
            o("\n" + p);
        }
    }
}

新版本，接受一个数字作为通过命令行提供的输入，没有输入验证。173 154 个字符。

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;var i=ulong.Parse(a[0]);o(i);while(i>1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}}}

长篇：

using System;
class P
{
    static void Main(string[]a)
    {
        Action<object>o=Console.Write;
        var i=ulong.Parse(a[0]);
        o(i);
        while(i>1)
        {
            i=i%2==0?i/2:i*3+1;
            o(" -> "+i);
        }
    }
}

我可以通过在这个答案中扯掉这个想法来使用 for 循环而不是一段时间来削减一些字符。150 个字符。

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;for(var i=ulong.Parse(a[0]);i>1;i=i%2==0?i/2:i*3+1)o(i+" -> ");o(1);}}

Answer 23

哈斯克尔：50

c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)

Answer 24

斯卡拉 + 斯卡拉兹

import scalaz._
import Scalaz._
val collatz = 
   (_:Int).iterate[Stream](a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) // This line: 61 chars

在行动中：

scala> collatz(7).toList
res15: List[Int] = List(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2)

斯卡拉 2.8

val collatz = 
   Stream.iterate(_:Int)(a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) :+ 1

这也包括尾随的 1。

scala> collatz(7)
res12: scala.collection.immutable.Stream[Int] = Stream(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

具有以下隐式

implicit def intToEven(i:Int) = new {
  def ~(even: Int=>Int, odd: Int=>Int) = { 
    if (i%2==0) { even(i) } else { odd(i) }
  }
}

这可以缩短为

val collatz = Stream.iterate(_:Int)(_~(_/2,3*_+1)).takeWhile(1<) :+ 1

编辑 - 58 个字符 （包括输入和输出，但不包括初始数字）

var n=readInt;while(n>1){n=Seq(n/2,n*3+1)(n%2);println(n)}

如果您不需要换行符，可以减少 2...

Answer 25

不是最短的，而是优雅的 clojure 解决方案

(defn collatz [n]
 (print n "")
 (if (> n 1)
  (recur
   (if (odd? n)
    (inc (* 3 n))
    (/ n 2)))))

Answer 26

PHP

function Collatz($n)
{
        $i = 0;
    while($n>1)
    {
        if($n % 2)
        {
            $n = (3*$n) + 1;
            $i++;
            echo "step $i:  $n <br/>";
        }

        else 
        {
            $n = $n/2;
            $i++;
            echo "step $i:  $n <br/>";
        }
    }

}

Answer 27

JavaScript - 68 个字符

与其他 JS（和大多数其他语言）不同，这个实际上遵循->输出中的 。

for(s='',c=' -> ',i=readline();i>1;i=i%2?i*3+1:i/2)s+=i+c
print(s+1)

如果我们避免这种情况，这是一个53 字符的替代方案，每行打印一个数字：

for(p=print,i=readline(),p(i);i>1;)p(i=i%2?i*3+1:i/2)

打算与 SpiderMonkey 一起运行：

echo 21 | js thisfile.js

21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Answer 28

F#，90 个字符

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))

> c 21;;
val it : seq<int> = seq [21; 64; 32; 16; ...]

或者，如果您不使用 F# 交互来显示结果，则为 102 个字符：

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))>>printf"%A"

Answer 29

C#：支持 BigInteger 的 659 个字符

using System.Linq;using C=System.Console;class Program{static void Main(){var v=C.ReadLine();C.Write(v);while(v!="1"){C.Write("->");if(v[v.Length-1]%2==0){v=v.Aggregate(new{s="",o=0},(r,c)=>new{s=r.s+(char)((c-48)/2+r.o+48),o=(c%2)*5}).s.TrimStart('0');}else{var q=v.Reverse().Aggregate(new{s="",o=0},(r, c)=>new{s=(char)((c-48)*3+r.o+(c*3+r.o>153?c*3+r.o>163?28:38:48))+r.s,o=c*3+r.o>153?c*3+r.o>163?2:1:0});var t=(q.o+q.s).TrimStart('0').Reverse();var x=t.First();q=t.Skip(1).Aggregate(new{s=x>56?(x-57).ToString():(x-47).ToString(),o=x>56?1:0},(r,c)=>new{s=(char)(c-48+r.o+(c+r.o>57?38:48))+r.s,o=c+r.o>57?1:0});v=(q.o+q.s).TrimStart('0');}C.Write(v);}}}

不打高尔夫球

using System.Linq;
using C = System.Console;
class Program
{
    static void Main()
    {
        var v = C.ReadLine();
        C.Write(v);
        while (v != "1")
        {
            C.Write("->");
            if (v[v.Length - 1] % 2 == 0)
            {
                v = v
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = r.s + (char)((c - 48) / 2 + r.o + 48), o = (c % 2) * 5 })
                    .s.TrimStart('0');
            }
            else
            {
                var q = v
                    .Reverse()
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = (char)((c - 48) * 3 + r.o + (c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 28 : 38 : 48)) + r.s, o = c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 2 : 1 : 0 });
                var t = (q.o + q.s)
                    .TrimStart('0')
                    .Reverse();
                var x = t.First();
                q = t
                    .Skip(1)
                    .Aggregate(
                        new { s = x > 56 ? (x - 57).ToString() : (x - 47).ToString(), o = x > 56 ? 1 : 0 }, 
                        (r, c) => new { s = (char)(c - 48 + r.o + (c + r.o > 57 ? 38 : 48)) + r.s, o = c + r.o > 57 ? 1 : 0 });
                v = (q.o + q.s)
                    .TrimStart('0');
            }
            C.Write(v);
        }
    }
}

Answer 30

Frm Jerry Coffin 的程序有整数溢出，试试这个：

#include <iostream>

int main(unsigned long long i)
{
    int j = 0;
    for(  std::cin>>i; i>1; i = i&1? i*3+1:i/2, ++j)
        std::cout<<i<<" -> ";

    std::cout<<"\n"<<j << " iterations\n";
}

用

总停止时间最长的小于1亿的数字是63,728,127，有949步。

总停止时间最长的小于 10 亿的数字是 670,617,279，有 986 个步骤。

Answer 31

Windows cmd - 68 个字符

@set/pd=
:l 
@set/ad=(d+d%%2*(d*5+2))/2&echo %d%&if %d% NEQ 1 goto:l

Answer 32

Common Lisp，141 个字符：

(defun c ()
  (format t"Number: ")
  (loop for n = (read) then (if(oddp n)(+ 1 n n n)(/ n 2))
     until (= n 1)
     do (format t"~d -> "n))
  (format t"1~%"))

测试运行：

Number: 171
171 -> 514 -> 257 -> 772 -> 386 -> 193 -> 580 -> 290 -> 145 -> 436 ->
218 -> 109 -> 328 -> 164 -> 82 -> 41 -> 124 -> 62 -> 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 

Answer 33

ruby，43，可能满足 I/O 要求

---

运行ruby -n hail

n=$_.to_i
(n=n%2>0?n*3+1: n/2
p n)while n>1

Answer 34

PHP，78 72 67 个字符

实际上，我大约在两年前编写了这个程序，当时我在一本 Pickover 书中读到了这个序列。我把它清理了一下，这是我能做的最小的，仍然有用户输入和一个很好的、可读的输出：

<?$n=fgets(STDIN);while($n!=1){$n=(($n&1)==0)?($n/2):(($n*3)+1);echo"$n\n";}?>

必须假设启用了短标签，我不确定输入是否适用于所有控制台。但它在我的 Windows 机器上运行良好。

---

更新：通过在数学上作弊，我们可以去掉一些字符：

<?$n=fgets(STDIN);while($n!=1){$n=(($n&1)==0)?$n/2:$n*3+1;echo"$n\n";}?>

---

更新：

• 鉴于$n&1返回1or 0，我们可以利用 PHP 的松散类型并删除更多字符。
• 此外，结合下面 Christian 的评论（稍作改动以防止无限循环），我们可以再删除一个。
• 最后，由于 PHP 脚本不需要终止符?>，我们可以去掉另外两个字符：

最终结果：

<?$n=fgets(STDIN);while($n>1){$n=(!($n&1))?$n/2:$n*3+1;echo"$n\n";}

Answer 35

Fortran：71 个字符

n=1
1 if(n==1)read*,n
n=merge(n/2,3*n+1,mod(n,2)==0)
print*,n
goto1
end

---

因为有人必须这样做:)

该计数包括所需的换行符。完全符合 Fortran 95（及更高版本）的代码。包括完整的 I/O，并且可以根据需要执行多次！

编辑：使用 goto 少一个字符（风格要点！）

Answer 36

红宝石，41 个字符

n=gets.to_i
p n=[n/2,n*3+1][n%2]while n>1

Answer 37

MATLAB 7.8.0 (R2009a)：58 个字符

n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2;disp(n);end

测试用例：

>> n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2;disp(n);end
21
    64
    32
    16
     8
     4
     2
     1

Answer 38

Javascript，67 56 个字符

for(a=[i=prompt()];i-1;a.push(i=i%2?i*3+1:i/2));alert(a)

Answer 39

由于似乎对 LOLCODE 解决方案有点兴趣，我想我会比较这种语言中两种解决方案方法（迭代和尾递归）的实现。

首先，有203个字符的迭代解：

HAI 1.2
    I HAS A n
    GIMMEH n
    IM IN YR l
        VISIBLE n
        BOTH SAEM 1 BIGGR OF 1 n
        O RLY?
            YA RLY
                GTFO
        OIC
        MOD OF n 2
        WTF?
            OMG 0
                n R QUOSHUNT OF n 2
                GTFO
            OMG 1
                n R SUM OF 1 PRODUKT OF 3 n
        OIC
    IM OUTTA YR l
KTHXBYE

为您提供正在发生的事情的要点：

• GIMMEH使用关键字从 STDIN 读取输入
• IM IN YR <loopname>在andIM OUTTA YR <loopname>语句之间进行循环
• VISIBLE用于打印到 STDOUT
• 、O RLY?和语句处理条件 If YA RLY/ OICThen/Else 逻辑
• 、WTF?和语句处理条件 Switch OMG <expression>/ OICCase 逻辑
• 分配是使用<variable> R <value>
• GTFO 从循环或条件 Switch/Case 中断

然后是尾递归解决方案，它设法削减了 2 个额外的字符，最终计数为 201：

HAI 1.2
    HOW DUZ I c YR n
        VISIBLE n
        DIFFRINT 1 BIGGR OF 1 n
        O RLY?
            YA RLY
                MOD OF n 2
                WTF?
                    OMG 0
                        c QUOSHUNT OF n 2
                        GTFO
                    OMG 1
                        c SUM OF 1 PRODUKT OF 3 n
                OIC
        OIC
    IF U SAY SO
    I HAS A i
    GIMMEH i
    c i
KTHXBYE

这里的区别在于HOW DUZ I <funcname> YR <args>andIF U SAY SO语句之间的函数定义。用 调用函数<funcname> <args>。

Answer 40

Bash, 130 including spaces and newlines:

#!/bin/bash
if [ $1 == 1 ]; then echo $1
else if [ $(($1%2)) == 0 ]; then n=$(($1/2))
else n=$(($1*3+1))
fi
echo "$1 -> `c $n`"
fi

This assumes that c is the name of the script file, and it is in the path of the user who's running the script.

Answer 41

微软小型基础版

TextWindow.Write( "Number: " )
n = TextWindow.ReadNumber()
TextWindow.Write( "Results: " )
While ( n > 1 )
  TextWindow.Write( n + " -> " )
  If Math.Remainder( n, 2 ) = 0  Then
    n = n / 2
  Else
    n = n * 3 + 1
  EndIf 
EndWhile
TextWindow.WriteLine(1) 

您可以在以下位置运行它： http ://smallbasic.com/program/?ZZR544

Answer 42

GW-BASIC - 54 个字符

1INPUT N
2N=(N+(N*5+2)*(N MOD 2))/2:?N:IF N>1GOTO 2

Answer 43

Python：

def collatz(n):
    if (n%2) == 0:
        return n/2
    else:
        return 3*n+1
def do_collatz(n):
    while n > 1:
        print n
        n = collatz(n)
    print n
do_collatz(int(input("Start number: ")))

不易受到堆栈溢出的影响，但不会在不收敛于 1 的序列上终止。（编辑：忘记输入部分）

Answer 44

Perl，59 个字符：

sub c{print my$x="@_\n";@_=$x&1?$x*3+1:$x/2,goto&c if$x!=1}

Answer 45

F# 82 字符

let rec f n=printfn "%A" n;if n>1I then if n%2I=0I then f(n/2I)else f(3I*n+1I)

Answer 46

VB.Net，约 180 个字符

Sub Main()
    Dim q = New Queue(Of Integer)
    q.Enqueue(CInt(Console.ReadLine))
    Do
        q.Enqueue(CInt(If(q.Peek Mod 2 = 0, q.Dequeue / 2, q.Dequeue * 3 + 1)))
        Console.WriteLine(q.Peek)
    Loop Until q.Peek = 1
End Sub

有趣的是将此代码转换为 c# 创建更多字符

使其在空的 .vb 文件中工作（大约 245 个字符）

Imports System.Collections.Generic
Imports System
Module m
    Sub Main()
        Dim q = New Queue(Of Integer)
        q.Enqueue(CInt(Console.ReadLine))
        Do
            q.Enqueue(CInt(If(q.Peek Mod 2 = 0, q.Dequeue / 2, q.Dequeue * 3 + 1)))
            Console.WriteLine(q.Peek)
        Loop Until q.Peek = 1
    End Sub
End Module

Answer 47

J，45 个字符

(-: * 0&=@(2&|)) + (1 + 3&*) * -.@(0&=@(2&|))

我不是 J 方面的专家。由于 mean 的函数是 +/%#，我相信这可以缩短。

Answer 48

php。69 个字符

感谢 Danko Durbić 的 fgets(STDIN)，希望你不要介意 :)

<?$i=fgets(STDIN);while($i!=1){echo ($i=$i%2?$i*3+1:$i/=2),"\r\n";}?>

Answer 49

VBScript: 105 Characters

Apparently I'm a glutton for punishment.

c(InputBox("?"))
Public Sub c(i)
msgbox(i)
If i>1 Then
If i mod 2=0 Then
c(i/2)
Else
c(3*i+1)
End If
End If
End Sub

Answer 50

C: 63 个字符

main(x){scanf("%d",&x);while(x>printf("%d ",x=x&1?3*x+1:x/2));}

这是基于 KennyTM 的回答。将 for 循环更改为 while 循环，并将代码带入 while。

Answer 51

Josl - 58 个字符

由于尾递归，此版本不会堆栈溢出。

c dup println dup 1 > if dup odd? if 3 * 1+ else 2 / end c

利用：

main 21 c

或者，其他示例：

main 
  21 c
  63,728,127 c

Answer 52

Powershell：80 个字符

单线：

"Results: $(for($x=read-host Number;1%$x;$x=@($x/2;3*$x+1)[$x%2]){""$x ->""}) 1"

印刷精美：

"Results: $( for( $x = read-host Number; 1%$x; $x = @( $x/2; 3*$x+1 )[ $x%2 ] )
             { 
                 ""$x ->"" 
             }
           ) 1"

没有输入提示和输出格式 - 44 个字符：

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

Answer 53

C++ 113 100 95

#include <iostream>
int main(int i){for(std::cin>>i;i>1;i=i&1?i*3+1:i/2)std::cout<<i<<" -> ";}

Answer 54

米兰达（101 个字符）

c n=" 1",if n=1
   =" "++shownum(n)++c(n*3+1),if n mod 2=1
   =" "++shownum(n)++c(n div 2),otherwise

（空格在语法上很重要）

Answer 55

二郎，120个字符

-module (f).
-export ([f/1]).
f(1)->1;
f(N)->
    io:format("~p ",[N]),
    if N rem 2 =:= 0
        ->f(trunc(N/2));
        true->f(3*N+1)
end.

测试：

f:f(171).

171 514 257 772 386 193 580 290 145 436 218 109 328 164 82 41 124 62 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

Answer 56

狂欢 57/61/60

另一个 bash 条目。不执行无限精度数学，它可能会溢出。

#!/bin/bash
x=$1;echo $x;((x>1))&&$0 $((x%2?x*3+1:x/2))

不应该溢出的版本可能是

#!/bin/bash
x=$1;echo $x;((x>1))&&exec $0 $((x%2?x*3+1:x/2))

（编辑）还有一个迭代版本：

#!/bin/bash
for((x=$1;x>1;x=x%2?x*3+1:x/2));do echo $x;done

Answer 57

Fortran - 60 个字符

read*,n
1 if(n/2*2<n)n=6*n+2
n=n/2
print*,n
if(n>1)goto1
end

Answer 58

因素：

不打高尔夫球

USE: math
: body ( n -- n ) >integer dup . "->" . dup odd? = [ 3 * 1 + ] [ 2 / ] if ;
: hailstone ( n --  ) dup 1 > [ body hailstone ] [ . ] if  ;
21 hailstone

打高尔夫球：

21 [ dup 1 > ] [ >integer dup . "->" . dup 2 mod 1 = [ 3 * 1 + ] [ 2 / ] if ] while .

输出：

21
"->"
64
"->"
32
"->"
16
"->"
8
"->"
4
"->"
2
"->"
1

Answer 59

Smalltalk，103 个字符

[:n||l|l:=OrderedCollection with:1.[n>1]whileTrue:[l addLast:n.n:=n odd ifTrue:[3*n+1]ifFalse:[n/2]].l]

通过向它发送消息 #value: 来调用它，并带有所需的参数：

[:n||l|l:=OrderedCollection with:1.[n>1]whileTrue:[l addLast:n.n:=n odd ifTrue:[3*n+1]ifFalse:[n/2]].l] value: 123

或者，更理智地说：

[:n | | result |
        result := OrderedCollection with: 1.
        [n > 1] whileTrue: [
                result addLast: n.
                n := n odd ifTrue: [3*n + 1] ifFalse: [n / 2]].
        result] value: 123

（正确的方法是将上述定义为 Integer 上的方法，因此您会说“123 collat​​z”，而不是匿名闭包。）

Answer 60

Grooovy - 59 个字符

int n=args[0] as int
while(n>1){println n=n%2==0?n/2:n*3+1}

例子

$ ./collatz.groovy 5
16
8
4
2
1

---

输出更漂亮（66个字符）

int n=args[0] as int
while(n>1){print " -> ${n=n%2==0?n/2:n*3+1}"}

例子

$ ./collatz.groovy 5
-> 16 -> 8 -> 4 -> 2 -> 1

Answer 61

JavaScript，61 70 个字符，带输入

迭代，精度取决于 JS 限制

var i=prompt('');while(i>1){console.log(i);i=(i%2)?3*i+1:i/2}

Answer 62

Clojure - 70 个字符

((fn[n](prn n)(if(> n 1)(recur(if(odd? n)(+(* 3 n)1)(/ n 2)))))(read))

或者，使用适当的空格和缩进：

((fn [n]
  (prn n)
  (if (> n 1)
    (recur
      (if (odd? n)
        (+ (* 3 n) 1)
        (/ n 2)))))
  (read))

recur强制 Clojure 使用尾调用递归，因此没有堆栈溢出。适用于任意大的数字。包括输入和输出，但如果输入非数字会崩溃:)。


注意：发布我的答案后不久，我注意到另一个具有几乎相同算法的 Clojure 实现。但是，由于那个人并没有试图简短，所以我会在这里留下我的答案，因为它的价值。

Answer 63

基于 ar 的代码，这是一个 perl 版本，它实际上符合输出要求

perl -E 'print"Number: ";$_=<STDIN>;chomp;print"Results: $_";$_=$_%2?$_*3+1:$_/2,print" -> ",$_ while$_!=1;say""'

长度：114 计算 perl 调用和引号，104 没有

我相信一些有经验的高尔夫球手可以进一步减少这种粗糙的版本。

Answer 64

C#，我认为是 88 个字符。递归的

void T(int i,string s){Console.Write("{0}{1}",s,i);if(i!=1)T(i%2==0?i/2:(i*3)+ 1,"->");}

加上这个最初的电话

T(171, "");

这是一种非递归方法，我认为是 107 个字符

void T2(int i){string s="";while(i>=1){Console.Write("{0}{1}",s,i);i=i==1?-1:i=i%2==0?i/2:(i*3)+1;s="->";}}

Answer 65

去吧，130个字符

package main
import(."os"
."strconv")
func main(){n,_:=Atoi(Args[1])
println(n)
for n>1{if n%2!=0{n=n*3+1}else{n/=2}
println(n)}}

例子

./collatz 3
3
10
5
16
8
4
2
1

Answer 66

红宝石 55 个字符

n=gets.to_i
while(n>1) do n=((n%2)==1)?3*n+1:n/2;p n end

Answer 67

J，31 个字符

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

用法：

-:`(>:@(3&*))`1:@.(1&=+2&|)^:a: 9
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Answer 68

Common Lisp，76 74 个字符

(defun c(n)(if (eql n 1)'(1)(cons n(if(oddp n)(c(1+(* 3 n)))(c(/ n 2))))))

或者，写得正确，

(defun collatz (n)
  (if (eql n 1)
      '(1)
    (cons n (if (oddp n)
                (collatz (1+ (* 3 n)))
                (collatz (/ n 2))))))

Answer 69

Perl，59 个字符

$n=shift;for($i=1;$n>1;$i++){$n=$n%2==0?$n/2:$n*3+1;printf"%002s: %s\n",$i,$n;}

但是，我更喜欢这个 79 个字符（不包括空格）的版本，因为它会打印行号和迭代值：

$n = shift; for($i = 1; $n > 1; $i++){ $n = $n % 2 == 0 ? $n / 2 : $n*3 + 1; printf "%002s: %s\n", $i, $n;}

$n = shift; 

for($i = 1; $n > 1; $i++){ 
    $n = $n % 2 == 0 ? $n / 2 : $n*3 + 1; 
    printf "%002s: %s\n", $i, $n;
}

Answer 70

使用HQ9+的扩展（我还没有编写），称为 HQ9+C，其中 C 在从标准输入中获取的数字上打印 Collat​​z 序列。

C

:P