Code Golf: Collatz Conjecture

Question 1

Inspirado em http://xkcd.com/710/ aqui está um código de golfe para ele.

O desafio

Dado um número inteiro positivo maior que 0, imprima a sequência de pedras de granizo para esse número.

A sequência de Hailstone

Veja a Wikipedia para mais detalhes.

Se o número for par, divida-o por dois.
Se o número for ímpar, triplique-o e adicione um.

Repita isso com o número produzido até chegar a 1. (se continuar depois de 1, ele fará um loop infinito de 1 -> 4 -> 2 -> 1...)

Às vezes, o código é a melhor maneira de explicar, então aqui estão alguns da Wikipedia

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

Este código funciona, mas estou adicionando um desafio extra. O programa não deve ser vulnerável a estouro de pilha . Portanto, ele deve usar iteração ou recursão de cauda.

Além disso, pontos de bônus se ele pode calcular grandes números e a linguagem ainda não o implementou. (ou se você reimplementar o suporte a grandes números usando inteiros de comprimento fixo)

Caso de teste

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

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

Além disso, o código de golfe deve incluir entrada e saída completas do usuário.

Question 2

conjunto x86, 1337 caracteres

;
; 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

Question 3

Befunge

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

Question 4

LOLCODE: 406 CHARAKTERZ

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

TESTADO UNDR JUSTIN J. MEZA'S INTERPRETR . KTHXBYE!

Question 5

Python - 95 64 51 46 char

Obviamente, não produz um estouro de pilha.

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

Question 6

Perl

Decidi ser um pouco anticompetitivo e mostrar como você normalmente codificaria esse problema em Perl.
_{Há também uma entrada de código de golfe de 46 (total) char no final.}

Todos esses três primeiros exemplos começam com este cabeçalho.

#! /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( $_ );
}

Versão recursiva simples

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 );
    }
  }
}

Versão iterativa simples

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;
  }
}

Versão iterativa otimizada

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];
}

Agora vou mostrar como você faria esse último exemplo com uma versão do Perl anterior à v5.10.0

#! /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];
  }
}

Benchmark

Em primeiro lugar, o IO sempre será a parte lenta. Portanto, se você realmente os comparou como estão, deverá obter aproximadamente a mesma velocidade de cada um.

Para testá-los, abri um identificador de arquivo para /dev/null( $null) e editei todos say $npara, em vez disso, ler say {$null} $n. Isso é para reduzir a dependência de 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;
  ...
}

Depois de executá-lo 10 vezes, aqui está uma saída de amostra representativa:

            Taxa recursiva iterativa otimizada
Recursivo 1715 / s - -27% -46%
Iterativo 2336 / s 36% - -27%
3187 / s otimizado 86% 36% -

Finalmente, uma entrada real de código de golfe:

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

46 caracteres no total

Se você não precisa imprimir o valor inicial, pode remover mais 5 caracteres.

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

41 chars totalizam
_{31 chars para a parte do código real, mas o código não funcionará sem o -nswitch. Portanto, incluo o exemplo completo em minha contagem.}

Question 7

Haskell, 62 chars 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

A entrada do usuário, a saída impressa, usa memória e pilha constantes, funciona com números inteiros arbitrariamente grandes.

Um exemplo de execução deste código, dado um número de 80 dígitos de todos os '1s (!) Como entrada, é muito divertido de olhar.

Versão original, somente função:

Haskell 51 chars

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

Quem o @ & ^ # precisa de condicionais, afinal?

(editar: eu estava sendo "inteligente" e usei o conserto. Sem ele, o código caiu para 54 caracteres. edit2: caiu para 51 por fatoração f())

Question 8

Golfscript: 20 caracteres

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

Isso é equivalente a

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;

Question 9

bc 41 chars

Acho que bcfoi inventado para esse tipo de problema :

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

Teste:

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

Código adequado:

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

bclida com números com até INT_MAXdígitos

Edit: O artigo da Wikipedia menciona que esta conjectura foi verificada para todos os valores até 20x2 ⁵⁸ (aprox. 5,76e18 ). Este programa:

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

testa 2 ^20.000 +1 (aprox. 3,98e 6.020 ) em 68 segundos, 144.404 ciclos.

Question 10

Perl: 31 caracteres

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

Editado para remover 2 espaços desnecessários.

Editado para remover 1 espaço desnecessário.

Question 11

MS Excel, 35 caracteres

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

Retirado direto da Wikipedia :

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

Bastou copiar / colar a fórmula 111 vezes para obter o resultado de um número inicial de 1000.;)

Question 12

C: 64 caracteres

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

Com suporte a grande número inteiro: 431 caracteres (necessários)

#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;}}

Nota : Não remova #include <stdlib.h>sem pelo menos prototipar malloc / realloc, pois isso não será seguro em plataformas de 64 bits (void * de 64 bits será convertido para int de 32 bits).

Este ainda não foi testado vigorosamente. Ele poderia usar um pouco de encurtamento também.

Versões prévias:

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

(removeu 12 caracteres porque ninguém segue o formato de saída ...: |)

Question 13

Outra versão do montador. Este não está limitado a números de 32 bits, ele pode lidar com números de até 10 ⁶⁵⁵³⁴ embora o formato ".com" que o MS-DOS usa esteja limitado a números de 80 dígitos. Escrito para o assembler A86 e requer uma caixa Win-XP DOS para funcionar. Monta até 180 bytes:

    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

Question 14

dc - 24 caracteres 25 28

dc é uma boa ferramenta para esta sequência:

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

dc -f collatz.dc
21
64
32
16
8
4
2
1

Também 24 caracteres usando a fórmula da entrada Golfscript :

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

57 caracteres para atender às especificações:

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

dc -f collatz-spec.dc
Número 3
Resultados: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Question 15

Esquema: 72

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

Isso usa recursão, mas as chamadas são recursivas no final, então acho que serão otimizadas para iteração. Em alguns testes rápidos, não consegui encontrar um número para o qual a pilha estourou de qualquer maneira. Por exemplo:

(C 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)

... funciona muito bem. [isso é tudo um número - eu apenas quebrei para caber na tela.]

Question 16

Mathematica, 45 50 chars

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

Question 17

Ruby, 50 caracteres, sem estouro de pilha

Basicamente, uma cópia direta da solução Python de makapuf :

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

Ruby, 45 caracteres, irá transbordar

Basicamente, uma cópia direta do código fornecido na pergunta:

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

Question 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);
    }
}

Question 19

Python 45 Char

Raspou um carvão da resposta de Makapuf.

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

Question 20

TI-BASIC

Não o mais curto, mas uma abordagem inovadora. Certamente desacelerará consideravelmente com grandes sequências, mas não deve transbordar.

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

Question 21

Haskell: 50

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

Question 22

não a mais curta, mas uma solução elegante de clojure

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

Question 23

C #: 216 caracteres

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);}}}

em formato longo:

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);
        }
    }
}

Nova versão, aceita um número como entrada fornecida através da linha de comando, sem validação de entrada. ~~173~~ 154 caracteres.

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);}}}

em formato longo:

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);
        }
    }
}

Eu sou capaz de raspar alguns caracteres retirando a ideia nesta resposta de usar um loop for em vez de um tempo. 150 caracteres.

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);}}

Question 24

Ruby, 43 caracteres

bignum suportado, com susceptibilidade de estouro de pilha:

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

... e 50 caracteres, bignum suportado, sem estouro de pilha:

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

Parabéns a Jordan. Eu não sabia sobre 'p' como um substituto para opções de venda.

Question 25

nroff ¹

Correr com 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. versão groff}

Question 26

Scala + Scalaz

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

E em ação:

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

Scala 2.8

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

Isso também inclui o 1 final.

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)

Com o seguinte implícito

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

isso pode ser encurtado para

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

Editar - 58 caracteres (incluindo entrada e saída, mas não incluindo o número inicial)

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

Pode ser reduzido em 2 se você não precisar de novas linhas ...

Question 27

F #, 90 caracteres

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; ...]

Ou, se você não estiver usando F # interativo para exibir o resultado, 102 caracteres:

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"

Question 28

Lisp comum, 141 caracteres:

(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~%"))

Execução de teste:

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

Question 29

O programa de Jerry Coffin tem overflow de inteiros, experimente este:

#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";
}

testado com

O número inferior a 100 milhões com o tempo total de parada mais longo é 63.728.127, com 949 passos.

O número menor que 1 bilhão com o tempo total de parada mais longo é 670.617.279, com 986 etapas.

Question 30

ruby, 43, possivelmente atendendo ao requisito de E / S

Correr com ruby -n hail

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

Question 31

C #: 659 caracteres com suporte BigInteger

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);}}}

Ungolfed

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 1

Inspirado em http://xkcd.com/710/ aqui está um código de golfe para ele.

O desafio

Dado um número inteiro positivo maior que 0, imprima a sequência de pedras de granizo para esse número.

A sequência de Hailstone

Veja a Wikipedia para mais detalhes.

Se o número for par, divida-o por dois.
Se o número for ímpar, triplique-o e adicione um.

Repita isso com o número produzido até chegar a 1. (se continuar depois de 1, ele fará um loop infinito de 1 -> 4 -> 2 -> 1...)

Às vezes, o código é a melhor maneira de explicar, então aqui estão alguns da Wikipedia

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

Este código funciona, mas estou adicionando um desafio extra. O programa não deve ser vulnerável a estouro de pilha . Portanto, ele deve usar iteração ou recursão de cauda.

Além disso, pontos de bônus se ele pode calcular grandes números e a linguagem ainda não o implementou. (ou se você reimplementar o suporte a grandes números usando inteiros de comprimento fixo)

Caso de teste

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

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

Além disso, o código de golfe deve incluir entrada e saída completas do usuário.

Answer 2

4

Veja também projecteuler.net/index.php?section=problems&id=14

Skilldrick

Answer 3

20

não deve ser vulnerável a estouro de pilha : você não deveria ter postado aqui então! ;)

Felix Kling

Answer 4

51

Meus amigos pararam de me ligar, isso significa que resolvi o problema?

Martin

Answer 5

18

Você está no SO, mas já teve amigos? ... como foi isso?

Aparece

Answer 6

5

A resposta do montador é legal, mas é um pouco anticódigo selecionar a resposta mais longa !

John La Rooy

Answer 7

conjunto x86, 1337 caracteres

;
; 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 8

27

x86 asm e 1337 chars. Eu choro de alegria.

ZoogieZork

Answer 9

10

Eu gosto do (ab) uso de lea para 3n + 1.

wowest

Answer 10

Obrigado por não usar int 23h.

Mike D.

Answer 11

como faço para complie no linux mal posso esperar para experimentá-lo

hidroto

Answer 12

64

Befunge

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

Josh Lee
fonte

2

Você deve ler isso em 2D. <> ^ v são setas que mudam a direção do "contador de programa". | e _ são condicionais que vão para cima / baixo ou esquerda / direita dependendo se o valor na pilha é verdadeiro ou falso. Toda a "arena do código" envolve a parte superior-inferior e a esquerda-direita.

SF.

E apenas 35 caracteres incluindo espaços em branco! Nada mal mesmo!

Potatoswatter

6

Tem certeza que não é Perl?

ijw

Answer 13

2

Você deve ler isso em 2D. <> ^ v são setas que mudam a direção do "contador de programa". | e _ são condicionais que vão para cima / baixo ou esquerda / direita dependendo se o valor na pilha é verdadeiro ou falso. Toda a "arena do código" envolve a parte superior-inferior e a esquerda-direita.

SF.

Answer 14

E apenas 35 caracteres incluindo espaços em branco! Nada mal mesmo!

Potatoswatter

Answer 15

6

Tem certeza que não é Perl?

ijw

Answer 16

LOLCODE: 406 CHARAKTERZ

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

TESTADO UNDR JUSTIN J. MEZA'S INTERPRETR . KTHXBYE!

Answer 17

51

Python - 95 64 51 46 char

Obviamente, não produz um estouro de pilha.

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

makapuf
fonte

4

Você pode querer especificar Python 2.x. IIRC, Python 3.x inputnão faz um eval.

Mike D.

5

Isso não cumpre os requisitos - não imprime o primeiro número

Ben Lings

7

por que isso é aceito? não é o mais curto e não imprime o primeiro número

Claudiu

1

Eu acho que input () ecoa os caracteres que você digita, então isso imprime o primeiro número :)

Danko Durbić

17

Você pode imprimir o primeiro número por um custo de apenas 2 bytes usandon=input()*2

John La Rooy

Answer 18

4

Você pode querer especificar Python 2.x. IIRC, Python 3.x inputnão faz um eval.

Mike D.

Answer 19

5

Isso não cumpre os requisitos - não imprime o primeiro número

Ben Lings

Answer 20

7

por que isso é aceito? não é o mais curto e não imprime o primeiro número

Claudiu

Answer 21

1

Eu acho que input () ecoa os caracteres que você digita, então isso imprime o primeiro número :)

Danko Durbić

Answer 22

17

Você pode imprimir o primeiro número por um custo de apenas 2 bytes usandon=input()*2

John La Rooy

Answer 23

Perl

Decidi ser um pouco anticompetitivo e mostrar como você normalmente codificaria esse problema em Perl.
_{Há também uma entrada de código de golfe de 46 (total) char no final.}

Todos esses três primeiros exemplos começam com este cabeçalho.

#! /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( $_ );
}

Versão recursiva simples

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 );
    }
  }
}

Versão iterativa simples

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;
  }
}

Versão iterativa otimizada

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];
}

Agora vou mostrar como você faria esse último exemplo com uma versão do Perl anterior à v5.10.0

#! /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];
  }
}

Benchmark

Em primeiro lugar, o IO sempre será a parte lenta. Portanto, se você realmente os comparou como estão, deverá obter aproximadamente a mesma velocidade de cada um.

Para testá-los, abri um identificador de arquivo para /dev/null( $null) e editei todos say $npara, em vez disso, ler say {$null} $n. Isso é para reduzir a dependência de 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;
  ...
}

Depois de executá-lo 10 vezes, aqui está uma saída de amostra representativa:

            Taxa recursiva iterativa otimizada
Recursivo 1715 / s - -27% -46%
Iterativo 2336 / s 36% - -27%
3187 / s otimizado 86% 36% -

Finalmente, uma entrada real de código de golfe:

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

46 caracteres no total

Se você não precisa imprimir o valor inicial, pode remover mais 5 caracteres.

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

41 chars totalizam
_{31 chars para a parte do código real, mas o código não funcionará sem o -nswitch. Portanto, incluo o exemplo completo em minha contagem.}

Answer 24

Sua versão otimizada, não é.

Motti

Answer 25

@Motti Esses exemplos são muito dependentes de IO. Depois de testá-los várias vezes, a versão otimizada sempre mantém uma liderança significativa.

Brad Gilbert,

Answer 26

@Brad, quando você executa Collatz em um número, a otimização é uma pessimização, pois nenhum número deve aparecer mais de uma vez (a menos que a conjectura esteja errada). A razão pela qual você está vendo uma melhoria é que você está executando muitos números (como no problema de Euler). Na verdade, eu escrevi uma postagem no blog sobre isso recentemente lanzkron.wordpress.com/2010/01/18/…

Motti

Answer 27

2

@Motti é dessa otimização que eu estava falando. Além disso, em Perl $i + 1há sempre adição (resposta à entrada do blog). Usar Sub::Call::Recurtambém é uma otimização. Caso contrário, eu usaria @_=$n;goto &Collatz. (É 10-20% mais lento se você mudar state @nextparamy @next

Brad Gilbert,

Answer 28

3

Acredito que os padrões de contagem de tacadas de golfe perl não contam as tacadas obrigatórias para invocar o intérprete nem as aspas, mas contam uma para cada bandeira ao lado de E. Usando essas regras, suas últimas entradas contam respectivamente 37 caracteres e 32 caracteres.

R. Martinho Fernandes

Answer 29

23

Haskell, 62 chars 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

A entrada do usuário, a saída impressa, usa memória e pilha constantes, funciona com números inteiros arbitrariamente grandes.

Um exemplo de execução deste código, dado um número de 80 dígitos de todos os '1s (!) Como entrada, é muito divertido de olhar.

Versão original, somente função:

Haskell 51 chars

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

Quem o @ & ^ # precisa de condicionais, afinal?

(editar: eu estava sendo "inteligente" e usei o conserto. Sem ele, o código caiu para 54 caracteres. edit2: caiu para 51 por fatoração f())

MtnViewMark
fonte

Depois de fazer minha postagem de Miranda (que é basicamente apenas o Haskell mais antigo), pelo menos em Miranda você pode cortar isso usando apenas um ponto de exclamação cada - fn = n: [[], [f (n div 2), f (3 * n + 1)]! (n mod 2)]! (1 mod n) - Funciona :)

Derek H

Oh, sim, está faltando entrada e saída.

R. Martinho Fernandes

@Martinho: Eu também, mas graças à avaliação preguiçosa, as tabelas estão ainda mais bacanas do que em outras línguas.

Dario

1

Usando a ideia de jleedev: c 1=[1];c n=n:(c$div(nmod 2*(5*n+2)+n)2)- 41 caracteres, usa o fato de que este é k * (3n + 1) + (1-k) * n / 2 onde k = n mod 2

sdcvvc

2

Excluí minha outra entrada, movi meu código aqui e incorporei ainda mais ideias desses comentários. Aumentado para 76 caracteres, mas oferece entrada e saída.

MtnViewMark

Answer 30

Depois de fazer minha postagem de Miranda (que é basicamente apenas o Haskell mais antigo), pelo menos em Miranda você pode cortar isso usando apenas um ponto de exclamação cada - fn = n: [[], [f (n div 2), f (3 * n + 1)]! (n mod 2)]! (1 mod n) - Funciona :)

Derek H

Answer 31

Oh, sim, está faltando entrada e saída.

R. Martinho Fernandes

Answer 32

@Martinho: Eu também, mas graças à avaliação preguiçosa, as tabelas estão ainda mais bacanas do que em outras línguas.

Dario

Answer 33

1

Usando a ideia de jleedev: c 1=[1];c n=n:(c$div(nmod 2*(5*n+2)+n)2)- 41 caracteres, usa o fato de que este é k * (3n + 1) + (1-k) * n / 2 onde k = n mod 2

sdcvvc

Answer 34

2

Excluí minha outra entrada, movi meu código aqui e incorporei ainda mais ideias desses comentários. Aumentado para 76 caracteres, mas oferece entrada e saída.

MtnViewMark

Answer 35

22

Golfscript: 20 caracteres

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

Isso é equivalente a

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;

KennyTM
fonte

2

"deve incluir entrada e saída completas do usuário"

F'x

2

@FX, a substituição de 21por ~fará com que o programa use um número de stdin

John La Rooy

@gnibbler: Golfscript.rb foi atualizado? Eu consegui (eval):1:in inicializar ': método indefinido leftparen' for nil:NilClass (NoMethodError)ao substituir 21por ~.

kennytm

@KennyTM, Infelizmente, GolfScript não consegue ler stdin interativamente, você tem que canalizar algo em stdin, comoecho 21 | ruby golfscript.rb collatz.gs

John La Rooy,

Answer 36

2

"deve incluir entrada e saída completas do usuário"

F'x

Answer 37

2

@FX, a substituição de 21por ~fará com que o programa use um número de stdin

John La Rooy

Answer 38

@gnibbler: Golfscript.rb foi atualizado? Eu consegui (eval):1:in inicializar ': método indefinido leftparen' for nil:NilClass (NoMethodError)ao substituir 21por ~.

kennytm

Answer 39

@KennyTM, Infelizmente, GolfScript não consegue ler stdin interativamente, você tem que canalizar algo em stdin, comoecho 21 | ruby golfscript.rb collatz.gs

John La Rooy,

Answer 40

19

bc 41 chars

Acho que bcfoi inventado para esse tipo de problema :

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

Teste:

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

Código adequado:

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

bclida com números com até INT_MAXdígitos

Edit: O artigo da Wikipedia menciona que esta conjectura foi verificada para todos os valores até 20x2 ⁵⁸ (aprox. 5,76e18 ). Este programa:

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

testa 2 ^20.000 +1 (aprox. 3,98e 6.020 ) em 68 segundos, 144.404 ciclos.

Carlos Gutiérrez
fonte

Altere 'n! = 1' para 'n> 1' para 54 caracteres.

Jerry Coffin,

4

Aqui está uma linha de comando para gerar números aleatórios de comprimento arbitrário para esta entrada (10.000 dígitos neste caso): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc

indiv

3

@indiv - Eu tive que testar :), levou 3 minutos e 12 segundos para processar o número de 10.000 dígitos. Salvei a saída em um arquivo, tem cerca de 1,2 gb de comprimento, mas sim terminou corretamente em 1. Ponto parabc

Carlos Gutiérrez

Answer 41

Altere 'n! = 1' para 'n> 1' para 54 caracteres.

Jerry Coffin,

Answer 42

4

Aqui está uma linha de comando para gerar números aleatórios de comprimento arbitrário para esta entrada (10.000 dígitos neste caso): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc

indiv

Answer 43

3

@indiv - Eu tive que testar :), levou 3 minutos e 12 segundos para processar o número de 10.000 dígitos. Salvei a saída em um arquivo, tem cerca de 1,2 gb de comprimento, mas sim terminou corretamente em 1. Ponto parabc

Carlos Gutiérrez

Answer 44

16

Perl: 31 caracteres

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

Editado para remover 2 espaços desnecessários.

Editado para remover 1 espaço desnecessário.

a'r
fonte

Você pode remover dois espaços desnecessários (depois de dizer e depois de algum tempo)

sorpigal

Tente perl -E 'dizer $ _ = 10; diga $ _ = $ _% 2? $ _ * 3 + 1: $ _ / 2 enquanto $ _> 1'

sorpigal

Achei que o usuário estaria ciente do número inicial da sequência ;-).

2010

41

Às vezes, quando encontro texto codificado em base64, às vezes confundo com o código-fonte Perl.

Martin

21

@Martin: Não consigo imaginar como você faria isso. Base64 é muito mais legível.

Jerry Coffin

Answer 45

Você pode remover dois espaços desnecessários (depois de dizer e depois de algum tempo)

sorpigal

Answer 46

Tente perl -E 'dizer $ _ = 10; diga $ _ = $ _% 2? $ _ * 3 + 1: $ _ / 2 enquanto $ _> 1'

sorpigal

Answer 47

Achei que o usuário estaria ciente do número inicial da sequência ;-).

2010

Answer 48

41

Às vezes, quando encontro texto codificado em base64, às vezes confundo com o código-fonte Perl.

Martin

Answer 49

21

@Martin: Não consigo imaginar como você faria isso. Base64 é muito mais legível.

Jerry Coffin

Answer 50

15

MS Excel, 35 caracteres

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

Retirado direto da Wikipedia :

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

Bastou copiar / colar a fórmula 111 vezes para obter o resultado de um número inicial de 1000.;)

Lance McNearney
fonte

16

Acho que é tarde demais para eu apontar que é para isso que serve a alça de preenchimento, hein? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :)

Jordan Running

Esse é um recurso muito útil que eu nem sabia que existia. Acabei de copiar a primeira célula e, em seguida, destaque todas as outras células e colei uma vez.

Lance McNearney

Aprendi sobre pasta de área aproximadamente dez anos depois de descobrir a alça de preenchimento. figuras.

Jimmy,

Answer 51

16

Acho que é tarde demais para eu apontar que é para isso que serve a alça de preenchimento, hein? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :)

Jordan Running

Answer 52

Esse é um recurso muito útil que eu nem sabia que existia. Acabei de copiar a primeira célula e, em seguida, destaque todas as outras células e colei uma vez.

Lance McNearney

Answer 53

Aprendi sobre pasta de área aproximadamente dez anos depois de descobrir a alça de preenchimento. figuras.

Jimmy,

Answer 54

C: 64 caracteres

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

Com suporte a grande número inteiro: 431 caracteres (necessários)

#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;}}

Nota : Não remova #include <stdlib.h>sem pelo menos prototipar malloc / realloc, pois isso não será seguro em plataformas de 64 bits (void * de 64 bits será convertido para int de 32 bits).

Este ainda não foi testado vigorosamente. Ele poderia usar um pouco de encurtamento também.

Versões prévias:

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

(removeu 12 caracteres porque ninguém segue o formato de saída ...: |)

Answer 55

Outra versão do montador. Este não está limitado a números de 32 bits, ele pode lidar com números de até 10 ⁶⁵⁵³⁴ embora o formato ".com" que o MS-DOS usa esteja limitado a números de 80 dígitos. Escrito para o assembler A86 e requer uma caixa Win-XP DOS para funcionar. Monta até 180 bytes:

    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 56

dc - 24 caracteres 25 28

dc é uma boa ferramenta para esta sequência:

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

dc -f collatz.dc
21
64
32
16
8
4
2
1

Também 24 caracteres usando a fórmula da entrada Golfscript :

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

57 caracteres para atender às especificações:

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

dc -f collatz-spec.dc
Número 3
Resultados: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Answer 57

Esquema: 72

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

Isso usa recursão, mas as chamadas são recursivas no final, então acho que serão otimizadas para iteração. Em alguns testes rápidos, não consegui encontrar um número para o qual a pilha estourou de qualquer maneira. Por exemplo:

(C 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)

... funciona muito bem. [isso é tudo um número - eu apenas quebrei para caber na tela.]

Answer 58

8

Mathematica, 45 50 chars

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

Pillsy
fonte

Contei 58 caracteres. E você pode substituir OddQ[#]por OddQ@#para economizar 1 caractere.

kennytm

2

50 caracteres:c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&]

Michael Pilat

Answer 59

Contei 58 caracteres. E você pode substituir OddQ[#]por OddQ@#para economizar 1 caractere.

kennytm

Answer 60

2

50 caracteres:c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&]

Michael Pilat

Answer 61

7

Ruby, 50 caracteres, sem estouro de pilha

Basicamente, uma cópia direta da solução Python de makapuf :

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

Ruby, 45 caracteres, irá transbordar

Basicamente, uma cópia direta do código fornecido na pergunta:

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

Jordan Running
fonte

Que versão de Ruby é essa? Eu n.odd??não fico definido. Além disso, é vulnerável a estouros de pilha com grandes números.

Earlz

Isso é interessante. Eu tenho 1.8.7. Adicionar um espaço entre os pontos de interrogação deve corrigir isso. E você está certo sobre o estouro da pilha. Vou editar minha resposta para tomar nota disso.

Jordan Running

3

Você pode salvar quatro personagens comp n=[n/2,n*3+1][n%2]

Wayne Conrad,

Answer 62

Que versão de Ruby é essa? Eu n.odd??não fico definido. Além disso, é vulnerável a estouros de pilha com grandes números.

Earlz

Answer 63

Isso é interessante. Eu tenho 1.8.7. Adicionar um espaço entre os pontos de interrogação deve corrigir isso. E você está certo sobre o estouro da pilha. Vou editar minha resposta para tomar nota disso.

Jordan Running

Answer 64

3

Você pode salvar quatro personagens comp n=[n/2,n*3+1][n%2]

Wayne Conrad,

Answer 65

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 66

50

Java: a linguagem onde você deve usar BigIntegers apenas para contar o número de caracteres no código da solução.

Jared Updike,

Answer 67

3

@Jared Concordo totalmente que Java é prolixo. Você tem que admitir que a solução apresentada a) atende aos requisitos b) é muito mais longa do que o realmente necessário ec) brinca com o sistema tipo java de uma forma agradável

wowest

Answer 68

7

Python 45 Char

Raspou um carvão da resposta de Makapuf.

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

GuillaumeDufay
fonte

uso muito inteligente do operador ~. Tive que pesquisar para ver o que acontecia (tento evitar operadores binários em Python, então não estou muito familiarizado com eles).

Ponkadoodle

Answer 69

uso muito inteligente do operador ~. Tive que pesquisar para ver o que acontecia (tento evitar operadores binários em Python, então não estou muito familiarizado com eles).

Ponkadoodle

Answer 70

TI-BASIC

Não o mais curto, mas uma abordagem inovadora. Certamente desacelerará consideravelmente com grandes sequências, mas não deve transbordar.

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 71

4

Haskell: 50

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

Josh Lee
fonte

Usando a ideia de jkff: c 1=[1];c n=n:(c$[ndiv 2,3*n+1]!!(nmod 2)), 44 chars

sdcvvc

Answer 72

Usando a ideia de jkff: c 1=[1];c n=n:(c$[ndiv 2,3*n+1]!!(nmod 2)), 44 chars

sdcvvc

Answer 73

não a mais curta, mas uma solução elegante de clojure

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

Answer 74

C #: 216 caracteres

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);}}}

em formato longo:

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);
        }
    }
}

Nova versão, aceita um número como entrada fornecida através da linha de comando, sem validação de entrada. ~~173~~ 154 caracteres.

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);}}}

em formato longo:

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);
        }
    }
}

Eu sou capaz de raspar alguns caracteres retirando a ideia nesta resposta de usar um loop for em vez de um tempo. 150 caracteres.

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 75

Você deve mencionar que seu código aceita mais de uma entrada. Ou tire isso e raspe alguns resíduos.

R. Martinho Fernandes

Answer 76

Você poderia encurtar Action <object> e possivelmente mais para dinâmico em C # 4.

Dykam,

Answer 77

@Dykam: Apenas verifiquei: falha com "erro CS0428: Não é possível converter o grupo de métodos 'Gravar' para o tipo não delegado 'dinâmico'. Você pretendia invocar o método?".

R. Martinho Fernandes

Answer 78

Oh, claro ... conversão implícita em delegados ... requer denotar o delegado. Que

chatice

Answer 79

Ruby, 43 caracteres

bignum suportado, com susceptibilidade de estouro de pilha:

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

... e 50 caracteres, bignum suportado, sem estouro de pilha:

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

Parabéns a Jordan. Eu não sabia sobre 'p' como um substituto para opções de venda.

Answer 80

4

nroff ¹

Correr com 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. versão groff}

DigitalRoss
fonte

2

Assustador! Ainda assim, pelo menos a saída deve ser bem formatada.

Jonathan Leffler,

3

Ei, execute-o como groff -U hail.ge você obterá PostScript! :-)

DigitalRoss

Answer 81

2

Assustador! Ainda assim, pelo menos a saída deve ser bem formatada.

Jonathan Leffler,

Answer 82

3

Ei, execute-o como groff -U hail.ge você obterá PostScript! :-)

DigitalRoss

Answer 83

Scala + Scalaz

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

E em ação:

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

Scala 2.8

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

Isso também inclui o 1 final.

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)

Com o seguinte implícito

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

isso pode ser encurtado para

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

Editar - 58 caracteres (incluindo entrada e saída, mas não incluindo o número inicial)

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

Pode ser reduzido em 2 se você não precisar de novas linhas ...

Answer 84

F #, 90 caracteres

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; ...]

Ou, se você não estiver usando F # interativo para exibir o resultado, 102 caracteres:

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 85

Lisp comum, 141 caracteres:

(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~%"))

Execução de teste:

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 86

Quase. Não há cabeçalho para a 2ª linha. Eu poderia ter raspado 3 caracteres ignorando a seta, outros 3-4 eliminando espaços desnecessários, mas estou feliz com um múltiplo de 3.

Vatine

Answer 87

O programa de Jerry Coffin tem overflow de inteiros, experimente este:

#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";
}

testado com

O número inferior a 100 milhões com o tempo total de parada mais longo é 63.728.127, com 949 passos.

O número menor que 1 bilhão com o tempo total de parada mais longo é 670.617.279, com 986 etapas.

Answer 88

Qualquer tipo de número inteiro finito não pode impedir o estouro de número inteiro. Nem mesmo unsigned long long.

kennytm,

Answer 89

3

ruby, 43, possivelmente atendendo ao requisito de E / S

Correr com ruby -n hail

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

DigitalRoss
fonte

Answer 90

C #: 659 caracteres com suporte BigInteger

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);}}}

Ungolfed

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);
        }
    }
}

Code Golf: Collatz Conjecture

Respostas:

conjunto x86, 1337 caracteres

Befunge

Python - 95 64 51 46 char

Perl

Benchmark

Haskell, 62 chars 63 76 83 , 86 , 97 , 137

Golfscript: 20 caracteres

bc 41 chars

Perl: 31 caracteres

C: 64 caracteres

Com suporte a grande número inteiro: 431 caracteres (necessários)

dc - 24 caracteres 25 28

Mathematica, 45 50 chars

Ruby, 50 caracteres, sem estouro de pilha

Ruby, 45 caracteres, irá transbordar

TI-BASIC

Haskell: 50

Ruby, 43 caracteres

nroff 1

F #, 90 caracteres

ruby, 43, possivelmente atendendo ao requisito de E / S

C #: 659 caracteres com suporte BigInteger

nroff ¹