Gol

Cree un programa / función que tome una entrada N, verifique si Nlos pares aleatorios de enteros son relativamente primos y retorna sqrt(6 * N / #coprime).

TL; DR

Estos desafíos son simulaciones de algoritmos que solo requieren la naturaleza y su cerebro (y tal vez algunos recursos reutilizables) para aproximarse a Pi. Si realmente necesitas Pi durante el apocalipsis zombie, ¡estos métodos no desperdician munición ! Hay ocho desafíos más por venir. Revisa la publicación de sandbox para hacer recomendaciones.

Simulación

¿Qué estamos simulando? Bueno, la probabilidad de que dos enteros aleatorios sean relativamente primos (es decir, coprime o mcd == 1) es 6/Pi/Pi, por lo que una forma natural de calcular Pi sería recoger dos cubos (o puñados) de rocas; cuéntalos; ver si su mcd es 1; repetir. Después de hacer esto un par de veces, sqrt(6.0 * total / num_coprimes)tenderá a hacerlo Pi. Si calcular la raíz cuadrada en el mundo post-apocalíptico te pone nervioso, ¡no te preocupes! Hay un método de Newton para eso.

¿Cómo estamos simulando esto?

• Tomar entrada N
• Haz los siguientes Nhorarios:
  • Generar uniformemente enteros positivos al azar, iyj
  • Con 1 <= i , j <= 10^6
  • Si gcd(i , j) == 1:result = 1
  • Más: result = 0
• Toma la suma de los Nresultados,S
• Regreso sqrt(6 * N / S)

Especificación

• Entrada
  • Flexible, tome la entrada en cualquiera de las formas estándar (por ejemplo, parámetro de función, STDIN) y en cualquier formato estándar (por ejemplo, cadena, binario)
• Salida
  • Flexible, dé salida en cualquiera de las formas estándar (por ejemplo, devolución, impresión)
  • El espacio en blanco, el espacio en blanco al final y al final es aceptable
  • Precisión, proporcione al menos 4 decimales de precisión (es decir 3.1416)
• Tanteo
  • ¡El código más corto gana!

Casos de prueba

Es posible que su salida no se alinee con estos, debido a la posibilidad aleatoria. Pero en promedio, debe obtener esta precisión para el valor dado de N.

Input     ->  Output 
-----         ------
100       ->  3.????
10000     ->  3.1???
1000000   ->  3.14??

APL, 23 bytes

{.5*⍨6×⍵÷1+.=∨/?⍵2⍴1e6}

Explicación:

• ?⍵2⍴1e6: genera una matriz de 2 por ⍵ de números aleatorios en el rango [1..10 ⁶ ]
• 1+.=∨/: obtenga el MCD de cada par y vea cuántos son iguales a 1. Esto calcula S.
• .5*⍨6×⍵÷: (6 × ⍵ ÷ S) ^0.5

Jalea , 20 18 16 bytes

-2 bytes gracias a @ Pietu1998 (cadena y uso cuenta 1s, ċ1en lugar de menos de dos sumados <2S)

-2 bytes gracias a @Dennis (repita 1e6 varias veces antes del muestreo para evitar el encadenamiento)

Ḥȷ6xX€g2/ċ1÷³6÷½

(Extremadamente lento debido a la función aleatoria)

¿Cómo?

Ḥȷ6xX€g2/ċ1÷³6÷½ - Main link: n
 ȷ6              - 1e6
   x             - repeat
Ḥ                -     double, 2n
    X€           - random integer in [1,1e6] for each
       2/        - pairwise reduce with
      g          -     gcd
         ċ1      - count 1s
           ÷     - divide
            ³    - first input, n
             6   - literal 6
              ÷  - divide
               ½ - square root

TryItOnline

Python 2, 143 140 132 124 122 124 122 bytes

Ha pasado bastante tiempo desde que probé el golf, ¡así que puede que me haya perdido algo aquí! Se actualizará a medida que acorte esto.

import random as r,fractions as f
n,s=input(),0
k=lambda:r.randrange(1e6)+1
exec's+=f.gcd(k(),k())<2;'*n
print(6.*n/s)**.5

^{Ponme a prueba aquí!}

^{gracias a Jonathan Allan por el ahorro de dos bytes :)}

Mathematica, 49 48 51 bytes

Se guardó un byte y se corrigió un error gracias a @ LegionMammal978 .

(6#/Count[GCD@@{1,1*^6}~RandomInteger~{2,#},1])^.5&

R, 103 99 95 99 98 94 bytes

Es probable que pueda jugar un poco de golf. Reduzca 4 bytes debido a @ antoine-sac, y otros 4 bytes definiendo un alias para sample, usando en ^.5lugar de sqrty en 1e6lugar de 10^6. Se agregaron 4 bytes para garantizar que el muestreo de iy jsea ​​realmente uniforme. Se eliminó un byte después de darme cuenta de que 6*N/sum(x)es lo mismo que 6/mean(x). Se usa en pryr::flugar de function(x,y)guardar 4 bytes.

N=scan()
s=sample
g=pryr::f(ifelse(o<-x%%y,g(y,o),y))
(6/mean(g(s(1e6,N,1),s(1e6,N,1))==1))^.5

Salida de muestra:

N=100     -> 3.333333
N=10000   -> 3.137794
N=1000000 -> 3.141709

En realidad, 19 bytes

`6╤;Ju@Ju┤`nkΣß6*/√

Pruébalo en línea!

Explicación:

`6╤;Ju@Ju┤`nkΣß6*/√
`6╤;Ju@Ju┤`n         do this N times:
 6╤;                   two copies of 10**6
    Ju                 random integer in [0, 10**6), increment
      @Ju              another random integer in [0, 10**6), increment
         ┤             1 if coprime else 0
            kΣ       sum the results
              ß      first input again
               6*    multiply by 6
                 /   divide by sum
                  √  square root

MATL , 22 bytes

1e6Hi3$YrZ}Zd1=Ym6w/X^

Pruébalo en línea!

1e6      % Push 1e6
H        % Push 2
i        % Push input, N
3$Yr     % 2×N matrix of uniformly random integer values between 1 and 1e6
Z}       % Split into its two rows. Gives two 1×N arrays
Zd       % GCD, element-wise. Gives a 1×N array
1=       % Compare each entry with 1. Sets 1 to 0, and other values to 0
Ym       % Mean of the array
6w/      % 6 divided by that
X^       % Square root. Implicitly display

Pyth, 21 bytes

@*6cQ/iMcmhO^T6yQ2lN2

Pruébalo en línea.

Explicación

                Q          input number
               y           twice that
         m                 map numbers 0 to n-1:
             T                 10
            ^ 6                to the 6th power
           O                   random number from 0 to n-1
          h                    add one
        c        2         split into pairs
      iM                   gcd of each pair
     /            lN       count ones
   cQ                      divide input number by the result
 *6                        multiply by 6
@                   2      square root

Scala, 149126 bytes

val& =BigInt
def f(n: Int)={math.sqrt(6f*n/Seq.fill(n){val i,j=(math.random*99999+1).toInt
if(&(i).gcd(&(j))>1)0 else 1}.sum)}

Explicación:

val& =BigInt                //define & as an alias to the object BigInt, because it has a gcd method
def f(n:Int)={              //define a method
  math.sqrt(                //take the sqrt of...
    6f * n /                //6 * n (6f is a floating-point literal to prevent integer division)
    Seq.fill(n){            //Build a sequence with n elements, where each element is..
      val i,j=(math.random*99999+1).toInt //take 2 random integers
      if(&(i).gcd(&(j))>1)0 else 1        //put 0 or 1 in the list by calling
                                          //the apply method of & to convert the numbers to
                                          //BigInt and calling its bcd method
    }.sum                   //calculate the sum
  )
}

Raqueta 92 bytes

(λ(N)(sqrt(/(* 6 N)(for/sum((c N))(if(= 1(gcd(random 1 1000000)(random 1 1000000)))1 0)))))

Sin golf:

(define f
  (λ (N)
    (sqrt(/ (* 6 N) 
            (for/sum ((c N))
              (if (= 1
                     (gcd (random 1 1000000)
                          (random 1 1000000)))
                  1 0)
              )))))

Pruebas:

(f 100)
(f 1000)
(f 100000)

Salida:

2.970442628930023
3.188964020716403
3.144483068444827

JavaScript (ES7), 107 95 94 bytes

n=>(n*6/(r=_=>Math.random()*1e6+1|0,g=(a,b)=>b?g(b,a%b):a<2,q=n=>n&&g(r(),r())+q(n-1))(n))**.5

La versión ES6 tiene exactamente 99 bytes, pero el operador de exponenciación ES7 **ahorra 5 bytes Math.sqrt.

Sin golf

function pi(n) {
  function random() {
    return Math.floor(Math.random() * 1e6) + 1;
  }
  function gcd(a, b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
  function q(n) {
    if (n == 0)
      return 0;
    return (gcd(random(), random()) == 1 ? 1 : 0) + q(n - 1));
  }
  return Math.sqrt(n * 6 / q(n));
}

PHP, 82 77 74 bytes

for(;$i++<$argn;)$s+=2>gmp_gcd(rand(1,1e6),rand(1,1e6));echo(6*$i/$s)**.5;

Corre así:

echo 10000 | php -R 'for(;$i++<$argn;)$s+=2>gmp_gcd(rand(1,1e6),rand(1,1e6));echo(6*$i/$s)**.5;' 2>/dev/null;echo

Explicación

Hace lo que dice en la lata. Requiere PHP_GMP para gcd.

Ajustes

• Guardado 3 bytes usando $argn

Perl, 64 bytes

sub r{1+~~rand 9x6}$_=sqrt$_*6/grep{2>gcd r,r}1..$_

Requiere la opción de línea de comando -pMntheory=gcd, contada como 13. La entrada se toma de stdin.

Uso de muestra

$ echo 1000 | perl -pMntheory=gcd pi-rock.pl
3.14140431218772

R, 94 bytes

N=scan();a=replicate(N,{x=sample(1e6,2);q=1:x[1];max(q[!x[1]%%q&!x[2]%%q])<2});(6*N/sum(a))^.5

Relativamente lento pero aún funciona. Replica N veces una función que toma 2 números aleatorios (de 1 a 1e6) y comprueba si su mcd es menor que 2 (utilizando una función mcd antigua mía ).

PowerShell v2 +, 118114 bytes

param($n)for(;$k-le$n;$k++){$i,$j=0,1|%{Random -mi 1};while($j){$i,$j=$j,($i%$j)}$o+=!($i-1)}[math]::Sqrt(6*$n/$o)

Toma entrada $n, inicia un forciclo hasta que sea $kigual $n(implícito $k=0al entrar por primera vez al ciclo). En cada iteración, obtenga nuevos Randomnúmeros $iy $j(el indicador de -minimum 1asegura que estamos >=1y no permite ningún indicador de máximo [int]::MaxValue, lo cual está permitido por el OP ya que es mayor que 10e6).

Luego entramos en un bucle GCDwhile . Entonces, siempre que el GCD sea 1, $ose incrementa. Al final del forciclo, hacemos una [math]::Sqrt()llamada simple , que se deja en la tubería y la salida es implícita.

Tarda unos 15 minutos en ejecutarse con la entrada 10000en mi portátil Core i5 de ~ 1 año.

Ejemplos

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 100
3.11085508419128

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 1000
3.17820863081864

PS C:\Tools\Scripts\golfing> .\natural-pi-0-rock.ps1 10000
3.16756133579975

Java 8, 164151 bytes

n->{int c=n,t=0,x,y;while(c-->0){x=1+(int)(Math.random()*10e6);y=1+(int)(Math.random()*10e6);while(y>0)y=x%(x=y);if(x<2)t++;}return Math.sqrt(6f*n/t);}

Explicación

n->{
    int c=n,t=0,x,y;
    while(c-->0){                          // Repeat n times
        x=1+(int)(Math.random()*10e6);     // Random x
        y=1+(int)(Math.random()*10e6);     // Random y
        while(y>0)y=x%(x=y);               // GCD
        if(x<2)t++;                        // Coprime?
    }
    return Math.sqrt(6f*n/t);              // Pi
}

Arnés de prueba

class Main {
    public static interface F{ double f(int n); }
    public static void g(F s){
        System.out.println(s.f(100));
        System.out.println(s.f(1000));
        System.out.println(s.f(10000));
    }
    public static void main(String[] args) {
        g(
            n->{int c=n,t=0,y,x;while(c-->0){x=1+(int)(Math.random()*10e6);y=1+(int)(Math.random()*10e6);while(y>0)y=x%(x=y);if(x<2)t++;}return Math.sqrt(6f*n/t);}
        );
    }
}

Actualizar

• -13 [16-10-05] Gracias a @TNT y al arnés de prueba agregado

Perl 6 , 56 53 bytes

{sqrt 6*$_/(1..10⁶).roll(*).map(*gcd*==1)[^$_].sum}

Pruébalo en línea!

Frink, 84 89

r[]:=random[10^6]+1
g=n=eval[input[1]]
for a=1to n
g=g-1%gcd[r[],r[]]
println[(6*n/g)^.5]

Tuve suerte: g = n = ... guarda un byte sobre g = 0 n = ... ; y 1% gcd () da (0,1) vs (1,0) para que pueda restar. Y la mala suerte: n preasignado y un utilizaron porque las variables de bucle y sus límites son locales y no definido fuera del bucle.

Verboso

r[] := random[10^6] + 1     // function. Frink parses Unicode superscript!
g = n = eval[input[""]]     // input number, [1] works too
for a = 1 to n              // repeat n times
   g = g - 1%gcd[r[], r[]]  // subtract 1 if gcd(i, j) > 1
println[(6*n/g)^.5]         // ^.5 is shorter than sqrt[x], but no super ".", no ½

AWK , 109 bytes

func G(p,q){return(q?G(q,p%q):p)}{for(;i++<$0;)x+=G(int(1e6*rand()+1),int(1e6*rand()+1))==1;$0=sqrt(6*$0/x)}1

Pruébalo en línea!

Me sorprende que se ejecute en un tiempo razonable para 1000000.

Pyt , 37 35 bytes

←Đ0⇹`25*⁶⁺Đ1⇹ɾ⇹1⇹ɾǤ1=⇹3Ș+⇹⁻łŕ⇹6*⇹/√

Explicación:

←Đ                                              Push input onto stack twice
  0                                             Push 0
   ⇹                                            Swap top two elements of stack
    `                      ł                    Repeat until top of stack is 0
     25*⁶⁺Đ1⇹ɾ⇹1⇹ɾ                              Randomly generate two integers in the range [1,10^6]
                  Ǥ1=                           Is their GCD 1?
                     ⇹3Ș                        Reposition top three elements of stack
                        +                       Add the top 2 on the stack
                         ⇹⁻                     Swap the top two and subtract one from the new top of the stack
                            ŕ                   Remove the counter from the stack
                             ⇹                  Swap the top two on the stack
                              6*                Multiply top by 6
                                ⇹               Swap top two
                                 /              Divide the second on the stack by the first
                                  √             Get the square root

J, 27 bytes

3 :'%:6*y%+/(1:=?+.?)y#1e6'

Explicación:

3 :'                      '  | Explicit verb definition
                     y#1e6   | List of y copies of 1e6 = 1000000
            (1:=?+.?)        | for each item, generate i and j, and test whether their gcd is 1
          +/                 | Sum the resulting list
      6*y%                   | Divide y by it and multiply by six
    %:                       | Square root

Tuve mucha suerte con un 3.14157for N = 10000000, que tardó 2.44segundos.

Japt , 23 bytes

*6/UÆ1+1e6ö)j1+1e6öÃx)¬

Intentalo