Code Golf: Conjetura de Collatz

Question 1

Inspirado por http://xkcd.com/710/ aquí hay un código de golf para ello.

El reto

Dado un número entero positivo mayor que 0, imprima la secuencia de granizo para ese número.

La secuencia del granizo

Consulte Wikipedia para obtener más detalles.

Si el número es par, divídelo por dos.
Si el número es impar, triplícalo y suma uno.

Repita esto con el número producido hasta que llegue a 1. (si continúa después de 1, irá en un bucle infinito de 1 -> 4 -> 2 -> 1...)

A veces, el código es la mejor manera de explicarlo, así que aquí hay algo de 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, pero estoy agregando un desafío adicional. El programa no debe ser vulnerable a desbordamientos de pila . Por lo tanto, debe usar iteración o recursión de cola.

Además, puntos de bonificación si puede calcular números grandes y el idioma aún no lo tiene implementado. (o si vuelve a implementar el soporte de números grandes utilizando enteros de longitud fija)

Caso de prueba

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

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

Además, el código golf debe incluir la entrada y salida completa del usuario.

Question 2

ensamblado 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

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

Question 5

Python - 95 64 51 46 caracteres

Obviamente no produce un desbordamiento de pila.

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

Question 6

Perl

Decidí ser un poco anticompetitivo y mostrar cómo codificaría normalmente ese problema en Perl.
_{También hay una entrada de golf de código de 46 caracteres (total) al final.}

Estos tres primeros ejemplos comienzan todos con este encabezado.

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

Versión recursiva simple

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

Versión iterativa simple

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

Versión iterativa optimizada

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

Ahora voy a mostrar cómo haría ese último ejemplo con una versión de Perl anterior a la 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];
  }
}

Punto de referencia

Primero, el IO siempre será la parte lenta. Entonces, si realmente los comparó como están, debería obtener aproximadamente la misma velocidad de cada uno.

Para probarlos, abrí un identificador de archivo en /dev/null( $null) y edité cada say $npara leer say {$null} $n. Esto es para reducir la dependencia 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;
  ...
}

Después de ejecutarlo 10 veces, aquí hay una salida de muestra representativa:

            Calificar iterativo recursivo optimizado
Recursivo 1715 / s - -27% -46%
Iterativo 2336 / s 36% - -27%
Optimizado 3187 / s 86% 36% -

Finalmente, una entrada de código de golf real:

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

46 caracteres en total

Si no necesita imprimir el valor inicial, puede eliminar 5 caracteres más.

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

41 caracteres en total
_{31 caracteres para la parte del código real, pero el código no funcionará sin el -ninterruptor. Así que incluyo el ejemplo completo en mi recuento.}

Question 7

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

Entrada de usuario, salida impresa, utiliza memoria y pila constantes, trabaja con enteros arbitrariamente grandes.

Una ejecución de muestra de este código, dado un número de 80 dígitos de todos los '1' (!) Como entrada, es bastante divertido de ver.

Versión original, solo función:

Haskell 51 caracteres

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

De todas formas, ¿quién @ & ^ # necesita condicionales?

(editar: estaba siendo "inteligente" y usé la corrección. Sin él, el código se redujo a 54 caracteres. edit2: se redujo a 51 al factorizar f())

Question 8

Golfscript: 20 caracteres

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

Esto es 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 caracteres

Supongo que este tipo de problemas es para lo que bcse inventó:

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

Prueba:

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

Código adecuado:

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

bcmaneja números con hasta INT_MAXdígitos

Editar: El artículo de Wikipedia menciona que esta conjetura ha sido verificada para todos los valores hasta 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

pruebas 2 ^20,000 +1 (aprox. 3.98e6,020 ) en 68 segundos, 144,404 ciclos.

Question 10

Perl: 31 caracteres

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

Editado para eliminar 2 espacios innecesarios.

Editado para eliminar 1 espacio innecesario.

Question 11

MS Excel, 35 caracteres

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

Tomado directamente de 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

Solo fue necesario copiar / pegar la fórmula 111 veces para obtener el resultado para un 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);}

Con soporte para enteros grandes: 431 caracteres (necesarios)

#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 : No elimine #include <stdlib.h>sin al menos crear un prototipo de malloc / realloc, ya que hacerlo no será seguro en plataformas de 64 bits (void * de 64 bits se convertirá a int de 32 bits).

Este todavía no ha sido probado vigorosamente. También le vendría bien un poco de manteca.

Versión anterior:

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

(se eliminaron 12 caracteres porque nadie sigue el formato de salida ...: |)

Question 13

Otra versión de ensamblador. Éste no está limitado a números de 32 bits, puede manejar números hasta 10 ⁶⁵⁵³⁴ aunque el formato ".com" que usa MS-DOS está limitado a números de 80 dígitos. Escrito para ensamblador A86 y requiere una caja DOS de Win-XP para ejecutarse. Se ensambla a 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 es una buena herramienta para esta secuencia:

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

dc -f collatz.dc
21
64
32
dieciséis
8
4
2
1

También 24 caracteres usando la fórmula de la entrada de Golfscript :

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

57 caracteres para cumplir con las especificaciones:

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

dc -f collatz-spec.dc
Numero 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))))))

Esto usa recursividad, pero las llamadas son recursivas al final, así que creo que estarán optimizadas para la iteración. En algunas pruebas rápidas, no he podido encontrar un número para el que la pila se desborde de todos modos. Solo por ejemplo:

(c)

... funciona bien. [eso es todo un número; lo acabo de romper para que quepa en la pantalla].

Question 16

Mathematica, 45 50 caracteres

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

Question 17

Ruby, 50 caracteres, sin desbordamiento de pila

Básicamente una copia directa de la solución Python de makapuf :

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

Ruby, 45 caracteres, se desbordará

Básicamente, una copia directa del código proporcionado en la pregunta:

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

Afeitó un carboncillo de la respuesta de makapuf.

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

Question 20

TI-BASIC

No es el enfoque más corto, pero sí novedoso. Seguro que se ralentizará considerablemente con secuencias grandes, pero no debería desbordarse.

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

no es la más corta, pero sí una elegante solución 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);}}}

en forma larga:

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

Nueva versión, acepta un número como entrada proporcionada a través de la línea de comando, sin validación de entrada. ~~173154~~ 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);}}}

en forma larga:

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

Puedo recortar algunos caracteres al copiar la idea en esta respuesta para usar un bucle for en lugar de un tiempo. 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

compatible con bignum, con susceptibilidad de desbordamiento de pila:

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

... y 50 caracteres, compatible con bignum, sin desbordamiento de pila:

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

Felicitaciones a Jordan. No conocía la 'p' como reemplazo de las opciones de venta.

Question 25

nroff ¹

Corre con 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. versión 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

Y en acción:

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

Esto también incluye el 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)

Con lo siguiente implícito

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

esto se puede acortar a

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

Editar: 58 caracteres (incluida la entrada y la salida, pero sin incluir el número inicial)

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

Podría reducirse en 2 si no necesita nuevas líneas ...

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

O si no está usando F # interactivo para mostrar el 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

Common Lisp, 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~%"))

Prueba de funcionamiento:

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

El programa de Jerry Coffin tiene un desbordamiento de enteros, pruebe 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";
}

probado con

El número de menos de 100 millones con el tiempo de parada total más largo es 63,728,127, con 949 pasos.

El número de menos de mil millones con el tiempo de parada total más largo es 670,617,279, con 986 pasos.

Question 30

ruby, 43, posiblemente cumpliendo con el requisito de E / S

Corre con 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 con soporte 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);}}}

Sin golf

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 por http://xkcd.com/710/ aquí hay un código de golf para ello.

El reto

Dado un número entero positivo mayor que 0, imprima la secuencia de granizo para ese número.

La secuencia del granizo

Consulte Wikipedia para obtener más detalles.

Si el número es par, divídelo por dos.
Si el número es impar, triplícalo y suma uno.

Repita esto con el número producido hasta que llegue a 1. (si continúa después de 1, irá en un bucle infinito de 1 -> 4 -> 2 -> 1...)

A veces, el código es la mejor manera de explicarlo, así que aquí hay algo de 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, pero estoy agregando un desafío adicional. El programa no debe ser vulnerable a desbordamientos de pila . Por lo tanto, debe usar iteración o recursión de cola.

Además, puntos de bonificación si puede calcular números grandes y el idioma aún no lo tiene implementado. (o si vuelve a implementar el soporte de números grandes utilizando enteros de longitud fija)

Caso de prueba

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

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

Además, el código golf debe incluir la entrada y salida completa del usuario.

Answer 2

4

También vea projecteuler.net/index.php?section=problems&id=14

Skilldrick

Answer 3

20

no debe ser vulnerable a desbordamientos de pila : ¡entonces no debería haberlo publicado aquí! ;)

Felix Kling

Answer 4

51

Mis amigos dejaron de llamarme, ¿eso significa que resolví el problema?

Martin

Answer 5

18

¿Estás en SO, pero alguna vez tuviste amigos? ... ¿como fue eso?

Pops

Answer 6

5

La respuesta del ensamblador es genial, ¡pero es un poco anti-código-golf seleccionar la respuesta más larga !

John La Rooy

Answer 7

ensamblado 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

asm x86 y 1337 caracteres. Lloro de alegría.

ZoogieZork

Answer 9

10

Me gusta el uso (ab) de lea para 3n + 1.

wowest

Answer 10

Gracias por no usar int 23h.

Mike D.

Answer 11

¿Cómo puedo cumplir en linux? No puedo esperar para probarlo

hidroto

Answer 12

64

Befunge

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

Josh Lee
fuente

2

Deberías leer esto en 2D. <> ^ v son flechas que cambian la dirección en la que se desplaza el "contador de programa". | y _ son condicionales que van hacia arriba / abajo o hacia la izquierda / derecha dependiendo de si el valor en la pila es verdadero o falso. Todo el "campo del código" se envuelve de arriba a abajo y de izquierda a derecha.

SF.

¡Y solo 35 caracteres, incluidos los espacios en blanco! ¡No está mal!

Potatoswatter

6

¿Estás seguro de que no es Perl?

ijw

Answer 13

2

Deberías leer esto en 2D. <> ^ v son flechas que cambian la dirección en la que se desplaza el "contador de programa". | y _ son condicionales que van hacia arriba / abajo o hacia la izquierda / derecha dependiendo de si el valor en la pila es verdadero o falso. Todo el "campo del código" se envuelve de arriba a abajo y de izquierda a derecha.

SF.

Answer 14

¡Y solo 35 caracteres, incluidos los espacios en blanco! ¡No está mal!

Potatoswatter

Answer 15

6

¿Estás seguro de que no es 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

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

Answer 17

51

Python - 95 64 51 46 caracteres

Obviamente no produce un desbordamiento de pila.

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

makapuf
fuente

4

Es posible que desee especificar Python 2.x. IIRC, Python 3.x inputno hace un eval.

Mike D.

5

Esto no cumple con los requisitos - no imprime el primer número

Ben Lings

7

¿Por qué se acepta esto? no es el más corto y no imprime el primer número

Claudiu

1

Supongo que input () hace eco de los caracteres que escribe, así que imprime el primer número :)

Danko Durbić

17

Puede imprimir el primer número por un costo de solo 2 bytes usandon=input()*2

John La Rooy

Answer 18

4

Es posible que desee especificar Python 2.x. IIRC, Python 3.x inputno hace un eval.

Mike D.

Answer 19

5

Esto no cumple con los requisitos - no imprime el primer número

Ben Lings

Answer 20

7

¿Por qué se acepta esto? no es el más corto y no imprime el primer número

Claudiu

Answer 21

1

Supongo que input () hace eco de los caracteres que escribe, así que imprime el primer número :)

Danko Durbić

Answer 22

17

Puede imprimir el primer número por un costo de solo 2 bytes usandon=input()*2

John La Rooy

Answer 23

Perl

Decidí ser un poco anticompetitivo y mostrar cómo codificaría normalmente ese problema en Perl.
_{También hay una entrada de golf de código de 46 caracteres (total) al final.}

Estos tres primeros ejemplos comienzan todos con este encabezado.

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

Versión recursiva simple

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

Versión iterativa simple

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

Versión iterativa optimizada

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

Ahora voy a mostrar cómo haría ese último ejemplo con una versión de Perl anterior a la 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];
  }
}

Punto de referencia

Primero, el IO siempre será la parte lenta. Entonces, si realmente los comparó como están, debería obtener aproximadamente la misma velocidad de cada uno.

Para probarlos, abrí un identificador de archivo en /dev/null( $null) y edité cada say $npara leer say {$null} $n. Esto es para reducir la dependencia 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;
  ...
}

Después de ejecutarlo 10 veces, aquí hay una salida de muestra representativa:

            Calificar iterativo recursivo optimizado
Recursivo 1715 / s - -27% -46%
Iterativo 2336 / s 36% - -27%
Optimizado 3187 / s 86% 36% -

Finalmente, una entrada de código de golf real:

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

46 caracteres en total

Si no necesita imprimir el valor inicial, puede eliminar 5 caracteres más.

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

41 caracteres en total
_{31 caracteres para la parte del código real, pero el código no funcionará sin el -ninterruptor. Así que incluyo el ejemplo completo en mi recuento.}

Answer 24

Tu versión optimizada, no lo es.

Motti

Answer 25

@Motti Estos ejemplos dependen mucho de IO. Después de haberlos probado varias veces, la versión optimizada siempre mantiene una ventaja significativa.

Brad Gilbert

Answer 26

@Brad, cuando ejecuta Collatz en un número, la optimización es una pesimización, ya que ningún número debería aparecer más de una vez (a menos que la conjetura sea incorrecta). La razón por la que está viendo una mejora es que está ejecutando muchos números (como en el problema de Euler), de hecho, escribí una publicación de blog sobre esto recientemente lanzkron.wordpress.com/2010/01/18/…

Motti

Answer 27

2

@Motti, esa es la optimización de la que estaba hablando. Además, en Perl $i + 1es siempre la suma (respuesta a la entrada del blog). Usar Sub::Call::Recurtambién es una optimización. De lo contrario, usaría @_=$n;goto &Collatz. (Es un 10-20% más lento si cambia state @nextamy @next

Brad Gilbert

Answer 28

3

Creo que los estándares de recuento de golpes de golf de Perl no cuentan los golpes obligatorios para invocar al intérprete ni las citas, pero sí cuentan uno para cada bandera al lado de E. Usando esas reglas, sus últimas entradas cuentan respectivamente 37 caracteres y 32 caracteres.

R. Martinho Fernandes

Answer 29

23

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

Entrada de usuario, salida impresa, utiliza memoria y pila constantes, trabaja con enteros arbitrariamente grandes.

Una ejecución de muestra de este código, dado un número de 80 dígitos de todos los '1' (!) Como entrada, es bastante divertido de ver.

Versión original, solo función:

Haskell 51 caracteres

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

De todas formas, ¿quién @ & ^ # necesita condicionales?

(editar: estaba siendo "inteligente" y usé la corrección. Sin él, el código se redujo a 54 caracteres. edit2: se redujo a 51 al factorizar f())

MtnViewMark
fuente

Después de hacer mi publicación de Miranda (que es básicamente un Haskell más antiguo), al menos en Miranda puedes reducir eso usando solo un signo de exclamación cada uno: fn = n: [[], [f (n div 2), f (3 * n + 1)]! (n mod 2)]! (1 mod n) - Funciona :)

Derek H

Oh, sí, te faltan entradas y salidas.

R. Martinho Fernandes

@Martinho: Yo también, pero gracias a la evaluación perezosa, las tablas son mucho más geniales que en otros idiomas.

Dario

1

Usando la idea de jleedev: c 1=[1];c n=n:(c$div(nmod 2*(5*n+2)+n)2)- 41 caracteres, esto usa el hecho de que esto es k * (3n + 1) + (1-k) * n / 2 donde k = n mod 2

sdcvvc

2

Eliminé mi otra entrada, moví mi código aquí e incorporé aún más ideas de estos comentarios. Incrementado a 76 caracteres, pero tiene entrada y salida.

MtnViewMark

Answer 30

Después de hacer mi publicación de Miranda (que es básicamente un Haskell más antiguo), al menos en Miranda puedes reducir eso usando solo un signo de exclamación cada uno: fn = n: [[], [f (n div 2), f (3 * n + 1)]! (n mod 2)]! (1 mod n) - Funciona :)

Derek H

Answer 31

Oh, sí, te faltan entradas y salidas.

R. Martinho Fernandes

Answer 32

@Martinho: Yo también, pero gracias a la evaluación perezosa, las tablas son mucho más geniales que en otros idiomas.

Dario

Answer 33

1

Usando la idea de jleedev: c 1=[1];c n=n:(c$div(nmod 2*(5*n+2)+n)2)- 41 caracteres, esto usa el hecho de que esto es k * (3n + 1) + (1-k) * n / 2 donde k = n mod 2

sdcvvc

Answer 34

2

Eliminé mi otra entrada, moví mi código aquí e incorporé aún más ideas de estos comentarios. Incrementado a 76 caracteres, pero tiene entrada y salida.

MtnViewMark

Answer 35

22

Golfscript: 20 caracteres

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

Esto es 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
fuente

2

"debe incluir la entrada y salida completa del usuario"

F'x

2

@FX, reemplazar el 21con ~hará que el programa use un número de stdin

John La Rooy

@gnibbler: ¿Golfscript.rb está actualizado? Obtuve (eval):1:in initialize ': método indefinido leftparen' for nil:NilClass (NoMethodError)al reemplazar 21con ~.

kennytm

@KennyTM, lamentablemente GolfScript no puede leer stdin de forma interactiva, tienes que canalizar algo en stdin, comoecho 21 | ruby golfscript.rb collatz.gs

John La Rooy

Answer 36

2

"debe incluir la entrada y salida completa del usuario"

F'x

Answer 37

2

@FX, reemplazar el 21con ~hará que el programa use un número de stdin

John La Rooy

Answer 38

@gnibbler: ¿Golfscript.rb está actualizado? Obtuve (eval):1:in initialize ': método indefinido leftparen' for nil:NilClass (NoMethodError)al reemplazar 21con ~.

kennytm

Answer 39

@KennyTM, lamentablemente GolfScript no puede leer stdin de forma interactiva, tienes que canalizar algo en stdin, comoecho 21 | ruby golfscript.rb collatz.gs

John La Rooy

Answer 40

19

bc 41 caracteres

Supongo que este tipo de problemas es para lo que bcse inventó:

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

Prueba:

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

Código adecuado:

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

bcmaneja números con hasta INT_MAXdígitos

Editar: El artículo de Wikipedia menciona que esta conjetura ha sido verificada para todos los valores hasta 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

pruebas 2 ^20,000 +1 (aprox. 3.98e6,020 ) en 68 segundos, 144,404 ciclos.

Carlos Gutiérrez
fuente

Cambie 'n! = 1' a 'n> 1' para 54 caracteres.

Jerry Coffin

4

Aquí hay una línea de comando para generar números aleatorios de longitud arbitraria para esta entrada (10000 dígitos en este caso): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc

indiv

3

@indiv - Tuve que probarlo :), me tomó 3 minutos y 12 segundos procesar el número de 10,000 dígitos. Guardé la salida en un archivo, tiene aproximadamente 1,2 gb de largo, pero sí, terminó correctamente en 1. Punto parabc

Carlos Gutiérrez

Answer 41

Cambie 'n! = 1' a 'n> 1' para 54 caracteres.

Jerry Coffin

Answer 42

4

Aquí hay una línea de comando para generar números aleatorios de longitud arbitraria para esta entrada (10000 dígitos en este caso): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc

indiv

Answer 43

3

@indiv - Tuve que probarlo :), me tomó 3 minutos y 12 segundos procesar el número de 10,000 dígitos. Guardé la salida en un archivo, tiene aproximadamente 1,2 gb de largo, pero sí, terminó correctamente en 1. Punto parabc

Carlos Gutiérrez

Answer 44

16

Perl: 31 caracteres

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

Editado para eliminar 2 espacios innecesarios.

Editado para eliminar 1 espacio innecesario.

a'r
fuente

Puede eliminar dos espacios innecesarios (después de decir y después de un tiempo)

sorigal

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

sorigal

Supuse que el usuario conocería el número inicial de la secuencia ;-).

2010

41

A veces, cuando me encuentro con texto codificado en base64, a veces lo confundo con el código fuente de Perl.

Martin

21

@Martin: No puedo imaginar cómo harías eso. Base64 es mucho más legible.

Jerry Coffin

Answer 45

Puede eliminar dos espacios innecesarios (después de decir y después de un tiempo)

sorigal

Answer 46

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

sorigal

Answer 47

Supuse que el usuario conocería el número inicial de la secuencia ;-).

2010

Answer 48

41

A veces, cuando me encuentro con texto codificado en base64, a veces lo confundo con el código fuente de Perl.

Martin

Answer 49

21

@Martin: No puedo imaginar cómo harías eso. Base64 es mucho más legible.

Jerry Coffin

Answer 50

15

MS Excel, 35 caracteres

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

Tomado directamente de 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

Solo fue necesario copiar / pegar la fórmula 111 veces para obtener el resultado para un número inicial de 1000.;)

Lance McNearney
fuente

16

Supongo que es demasiado tarde para señalar que para esto es el controlador de llenado, ¿eh? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :)

Jordan Running

Esa es una característica bastante útil que ni siquiera sabía que existía. Simplemente copié la primera celda y luego resalté todas las demás celdas y las pegué una vez.

Lance McNearney

Aprendí sobre la pasta de área aproximadamente diez años después de descubrir el mango de relleno. cifras.

Jimmy

Answer 51

16

Supongo que es demasiado tarde para señalar que para esto es el controlador de llenado, ¿eh? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :)

Jordan Running

Answer 52

Esa es una característica bastante útil que ni siquiera sabía que existía. Simplemente copié la primera celda y luego resalté todas las demás celdas y las pegué una vez.

Lance McNearney

Answer 53

Aprendí sobre la pasta de área aproximadamente diez años después de descubrir el mango de relleno. cifras.

Jimmy

Answer 54

C: 64 caracteres

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

Con soporte para enteros grandes: 431 caracteres (necesarios)

#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 : No elimine #include <stdlib.h>sin al menos crear un prototipo de malloc / realloc, ya que hacerlo no será seguro en plataformas de 64 bits (void * de 64 bits se convertirá a int de 32 bits).

Este todavía no ha sido probado vigorosamente. También le vendría bien un poco de manteca.

Versión anterior:

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

(se eliminaron 12 caracteres porque nadie sigue el formato de salida ...: |)

Answer 55

Otra versión de ensamblador. Éste no está limitado a números de 32 bits, puede manejar números hasta 10 ⁶⁵⁵³⁴ aunque el formato ".com" que usa MS-DOS está limitado a números de 80 dígitos. Escrito para ensamblador A86 y requiere una caja DOS de Win-XP para ejecutarse. Se ensambla a 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 es una buena herramienta para esta secuencia:

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

dc -f collatz.dc
21
64
32
dieciséis
8
4
2
1

También 24 caracteres usando la fórmula de la entrada de Golfscript :

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

57 caracteres para cumplir con las especificaciones:

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

dc -f collatz-spec.dc
Numero 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))))))

Esto usa recursividad, pero las llamadas son recursivas al final, así que creo que estarán optimizadas para la iteración. En algunas pruebas rápidas, no he podido encontrar un número para el que la pila se desborde de todos modos. Solo por ejemplo:

(c)

... funciona bien. [eso es todo un número; lo acabo de romper para que quepa en la pantalla].

Answer 58

8

Mathematica, 45 50 caracteres

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

Pillsy
fuente

Conté 58 caracteres. Y puede reemplazar OddQ[#]con OddQ@#para guardar 1 carácter.

kennytm

2

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

Michael Pilat

Answer 59

Conté 58 caracteres. Y puede reemplazar OddQ[#]con OddQ@#para guardar 1 carácter.

kennytm

Answer 60

2

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

Michael Pilat

Answer 61

7

Ruby, 50 caracteres, sin desbordamiento de pila

Básicamente una copia directa de la solución Python de makapuf :

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

Ruby, 45 caracteres, se desbordará

Básicamente, una copia directa del código proporcionado en la pregunta:

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

Jordan Running
fuente

¿Qué versión de Ruby es esa? No n.odd??me definen. Además, eso es vulnerable a desbordamientos de pila con grandes números.

Earlz

Eso es interesante. Tengo 1.8.7. Agregar un espacio entre los signos de interrogación debería arreglar eso. Y tienes razón sobre el desbordamiento de la pila. Editaré mi respuesta para tomar nota de eso.

Jordan Running

3

Puedes salvar cuatro personajes conp n=[n/2,n*3+1][n%2]

Wayne Conrad

Answer 62

¿Qué versión de Ruby es esa? No n.odd??me definen. Además, eso es vulnerable a desbordamientos de pila con grandes números.

Earlz

Answer 63

Eso es interesante. Tengo 1.8.7. Agregar un espacio entre los signos de interrogación debería arreglar eso. Y tienes razón sobre el desbordamiento de la pila. Editaré mi respuesta para tomar nota de eso.

Jordan Running

Answer 64

3

Puedes salvar cuatro personajes conp 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: el lenguaje donde tienes que usar BigIntegers solo para contar la cantidad de caracteres en el código de la solución.

Jared Updike

Answer 67

3

@Jared Estoy totalmente de acuerdo en que Java es detallado. Debe admitir que la solución presentada a) cumple con los requisitos b) es mucho más larga de lo realmente necesario yc) juega con el sistema de tipo Java de una manera agradable

wowest

Answer 68

7

Python 45 Char

Afeitó un carboncillo de la respuesta de makapuf.

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

GuillaumeDufay
fuente

uso muy inteligente del operador ~. Tuve que buscarlo para ver qué hacía (trato de evitar los operadores binarios en Python, así que no estoy muy familiarizado con ellos).

Ponkadoodle

Answer 69

uso muy inteligente del operador ~. Tuve que buscarlo para ver qué hacía (trato de evitar los operadores binarios en Python, así que no estoy muy familiarizado con ellos).

Ponkadoodle

Answer 70

TI-BASIC

No es el enfoque más corto, pero sí novedoso. Seguro que se ralentizará considerablemente con secuencias grandes, pero no debería desbordarse.

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
fuente

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

sdcvvc

Answer 72

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

sdcvvc

Answer 73

no es la más corta, pero sí una elegante solución 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);}}}

en forma larga:

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

Nueva versión, acepta un número como entrada proporcionada a través de la línea de comando, sin validación de entrada. ~~173154~~ 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);}}}

en forma larga:

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

Puedo recortar algunos caracteres al copiar la idea en esta respuesta para usar un bucle for en lugar de un tiempo. 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

Debe mencionar que su código acepta más de una entrada. O elimínelo y elimine algunos caracteres.

R. Martinho Fernandes

Answer 76

Puede acortar Action <object> y posiblemente más a dynamic en C # 4.

Dykam

Answer 77

@Dykam: Acabo de marcarlo: falla con el "error CS0428: No se puede convertir el grupo de métodos 'Escribir' al tipo no delegado 'dinámico'. ¿Tenía la intención de invocar el método?".

R. Martinho Fernandes

Answer 78

Oh, por supuesto ... la conversión implícita a delegados ... requiere denotar al delegado. Bummer ...

Dykam

Answer 79

Ruby, 43 caracteres

compatible con bignum, con susceptibilidad de desbordamiento de pila:

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

... y 50 caracteres, compatible con bignum, sin desbordamiento de pila:

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

Felicitaciones a Jordan. No conocía la 'p' como reemplazo de las opciones de venta.

Answer 80

4

nroff ¹

Corre con 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. versión groff}

DigitalRoss
fuente

2

¡De miedo! Aún así, al menos la salida debería tener un buen formato.

Jonathan Leffler

3

¡Ejecútelo como groff -U hail.gy obtendrá PostScript! :-)

DigitalRoss

Answer 81

2

¡De miedo! Aún así, al menos la salida debería tener un buen formato.

Jonathan Leffler

Answer 82

3

¡Ejecútelo como groff -U hail.gy obtendrá 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

Y en acción:

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

Esto también incluye el 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)

Con lo siguiente implícito

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

esto se puede acortar a

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

Editar: 58 caracteres (incluida la entrada y la salida, pero sin incluir el número inicial)

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

Podría reducirse en 2 si no necesita nuevas líneas ...

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

O si no está usando F # interactivo para mostrar el 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

Common Lisp, 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~%"))

Prueba de funcionamiento:

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

Casi. No hay encabezado para la segunda línea. Podría haberme afeitado 3 caracteres ignorando la flecha, otros 3-4 eliminando espacios innecesarios, pero estoy contento con un múltiplo de 3.

Vatine

Answer 87

El programa de Jerry Coffin tiene un desbordamiento de enteros, pruebe 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";
}

probado con

El número de menos de 100 millones con el tiempo de parada total más largo es 63,728,127, con 949 pasos.

El número de menos de mil millones con el tiempo de parada total más largo es 670,617,279, con 986 pasos.

Answer 88

Cualquier tipo de entero finito no puede evitar el desbordamiento de enteros. Ni siquiera unsigned long long.

kennytm

Answer 89

3

ruby, 43, posiblemente cumpliendo con el requisito de E / S

Corre con ruby -n hail

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

DigitalRoss
fuente

Answer 90

C #: 659 caracteres con soporte 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);}}}

Sin golf

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: Conjetura de Collatz

Respuestas:

ensamblado x86, 1337 caracteres

Befunge

Python - 95 64 51 46 caracteres

Perl

Punto de referencia

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

Golfscript: 20 caracteres

bc 41 caracteres

Perl: 31 caracteres

C: 64 caracteres

Con soporte para enteros grandes: 431 caracteres (necesarios)

dc - 24 caracteres 25 28

Mathematica, 45 50 caracteres

Ruby, 50 caracteres, sin desbordamiento de pila

Ruby, 45 caracteres, se desbordará

TI-BASIC

Haskell: 50

Ruby, 43 caracteres

nroff 1

F #, 90 caracteres

ruby, 43, posiblemente cumpliendo con el requisito de E / S

C #: 659 caracteres con soporte BigInteger

nroff ¹