Un generador principal natural

42

Hay una gran cantidad de funciones generadoras principales. Casi todos están construidos y se basan en el tamiz de Eratóstenes, la función de Möbius o el teorema de Wilson y, en general, no son factibles de calcular en la práctica. Pero también hay generadores, que tienen una estructura muy fácil y se encontraron por accidente.

En 2003, Stephen Wolfram exploró una clase de ecuaciones de recurrencia anidadas en un experimento de computadora en vivo en la Escuela de Verano de NKS. Un grupo de personas alrededor de Matthew Frank siguió con experimentos adicionales y descubrió una propiedad interesante de la simple recurrencia.

a(n) = a(n-1) + gcd(n,a(n-1))

con el valor inicial de a(1) = 7. La diferencia a(n) - a(n-1) = gcd(n,a(n-1))siempre parecía ser 1 o primo. Las primeras diferencias son ( OEIS A132199 ):

1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, ...

Si solo omitimos los 1s, obtenemos la siguiente secuencia ( OEIS A137613 ):

5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 
941, 3, 7, 1889, 3, 3779, 3, 7559, 3, 13, 15131, 3, 53, 3, 7, 30323, 3, ...

Eric S. Rowland demostró la importancia de cada elemento en esta lista unos años más tarde. Como puede ver, los números primos se mezclan y algunos de ellos aparecen varias veces. También se ha demostrado que la secuencia incluye infinitos primos distintos. Además, se conjetura que aparecen todos los números primos impares.

Debido a que este generador principal no se construyó sino que simplemente se encontró por accidente, el generador principal se llama "natural". Pero tenga en cuenta que en la práctica este generador también es bastante inviable de calcular. Como resultado, un p principal aparece solo después de (p–3)/21s consecutivos. Sin embargo, implementar este generador principal será su tarea.

Reto:

Escriba una función o un programa que imprima los primeros nelementos de la secuencia A137613(la secuencia sin los 1). Puede leer el número de entrada a n >= 0través de STDIN, argumento de línea de comandos, indicador de solicitud o argumento de función. Envíe los primeros nelementos en cualquier formato legible a STDOUT, o devuelva una matriz o una lista con estos valores.

Este es el código de golf. Por lo tanto, el código más corto gana.

Tabla de clasificación:

Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma. Para asegurarse de que su respuesta se muestre, comience con un título, utilizando la siguiente plantilla de Markdown:

# Language Name, N bytes

donde N es el tamaño de su envío. Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Mostrar fragmento de código

code-golf number sequence primes number-theory Jakube
fuente
1
Si bien el generador principal no está construido, está implementando efectivamente una división de prueba utilizando la recursividad.
orlp
Si a (1) = 7, ¿por qué la secuencia no comienza con 7?
feersum
3
@feersum porque la secuencia que nos preocupa esa(n)-a(n-1)
Maltysen
Puede nser cero?
Sp3000
1
@jrenk No estoy seguro. Tal vez lo cuente como 2 bytes (ya que está eliminando 2 caracteres //) y explíquelo en su envío. Si alguien no está de acuerdo contigo, siempre puedes editar tu publicación.
Jakube

Respuestas:

19

Pyth, 14 13 bytes

meaYhP+sY-5dQ

Usos a(n) = Lpf(6 - n + sum(a(i) for i in range(1, n))donde Lpfsignifica menos factor primo.

Pruébalo aquí en línea.

orlp
fuente
7

Python 3.5.0b1 +, 95 93 bytes

Enlace a Python 3.5.0b1 + versión

import math
def f(k,n=2,a=7,L=[]):x=math.gcd(n,a);return k and f(k-1%x,n+1,a+x,L+1%x*[x])or L

Una implementación directa de la recurrencia, que incluye:

  • Nuestro buen amigo 1%xy
  • math.gcd, a diferencia de fractions.gcd.
Sp3000
fuente
¿Qué 1%xhacer? Pregunta secundaria: ¿dónde encuentro documentación del historial de revisiones de Python que incluye betas? Editar: No importa, lo encontré al final del historial de revisiones .
mbomb007
@ mbomb007 Dado que x >= 1, 1%xdevuelve 0 si x == 1, 1 de lo contrario (se usa para decidir si se agrega xa la lista)
Sp3000
5

Julia, 110 bytes

n->(a(n)=(n≥1&&(n==1?7:a(n-1)+gcd(n,a(n-1))));i=2;j=0;while j<n x=a(i)-a(i-1);x>1&&(j+=1;println(x));i+=1end)

Sin golf:

function a(n::Int)
    n ≥ 1 && (n == 1 ? 7 : a(n-1) + gcd(n, a(n-1)))
end

function f(n::Int)
    i = 2;
    j = 0;
    while j < n
        x = a(i) - a(i-1)
        if x > 1
            j += 1
            println(x)
        end
        i += 1
    end
end
Alex A.
fuente
Wow, un perfecto 8k, agradable: D
Beta Decay
1
Usar en n<2lugar de n==1. Además, si mira hacia adelante en lugar de hacia atrás, puede usar i=1y x=a(i)-a(i+=1), y luego println(-x)y -x>1para corregir la negatividad, evitando así la necesidad de un incremento separado de i. Y ≥es tres bytes, mientras que >=es dos ... pero luego, puede usar en n<1||()lugar de n>=1&&()... y, sin embargo, ni siquiera es necesario en primer lugar (descarte el condicional, n nunca será menor que 1). Tampoco necesita los corchetes más externos al definir un (n). Con estos cambios, al menos debería bajar a 97 bytes.
Glen O
5

PHP, 101 96 99 98 77 72 bytes

<?for(;2>$t=gmp_strval(gmp_gcd(~++$i,7+$e+=$t))or$argv[1]-=print"$t ";);


Uso:
llame a la secuencia de comandos con un argumento: php -d error_reporting=0 script.php 30
si desea probarlo, debe descomentarlo ;extension=php_gmp.dllen su php.ini
-> extension=php_gmp.dll
¿Debo agregar la extensión a mi recuento de bytes? ¿Alguna idea?


Registro:
Guardado 3 bytes gracias a Ismael Miguel.
Guardado 26 bytes gracias a primo.

jrenk
fuente
1
Puede acortar su etiqueta de apertura <?y eliminar la definición de $j.
Ismael Miguel
1
Si cuenta. Pero puedes eliminar esa nueva línea. Lo que ahorrará 1-2 bytes, dependiendo de cómo haya contado el tamaño de su código.
Ismael Miguel
1
Pequeñas mejoras: Uso <en $j<=$argv[1](imprime demasiadas) (-1). Deje sin $einicializar, use $e+7en su lugar (-3). Use en for(;;)lugar de while(), haciendo uso de las expresiones pre y post (-2). Reemplace echo$t.' ';$j++con $j+=print"$t ", suelte los soportes (-3). Reemplazar if($t>1)con 2>$t||(-2). Combine la asignación a $tcon el condicional, cambie ||por or, suelte los corchetes (-5). Muévase $argv[1]al $jincremento, mueva toda la expresión al forcondicional (-2). Cambiar >=$j+=printa -=print(-3). Paso a paso: codepad.org/s6LNSPSM
primo
1
@primo gracias por la buena explicación! No sabía que podía hacer todo eso.
jrenk
1
Algunos más: combinar $e+7con $e+=$t(-2). Deje sin $iinicializar, use ~++$ien su lugar (-3). codepad.org/fDIImajp
primo
4

Haskell, 51 bytes

d=zipWith gcd[2..]$scanl(+)7d
f=($filter(>1)d).take

Tenga en cuenta que fes una función que devolverá los primeros n elementos.

En lugar de calcular a(n)y luego resolver las diferencias, calculamos las diferencias d(n)y las sumamos para obtener a(n). (Aquellos que no estén familiarizados con Haskell pueden protestar que necesitamos a(n)primero para llegar d(n), ¡pero, por supuesto, la evaluación perezosa nos ayuda a resolver este problema!

Sin golf:

a = scanl (+) 7 d        -- yielding a(n) = 7 + d(1) + d(2) + ... + d(n-1)
d = zipWith gcd [2..] a  -- yielding d(n) = gcd(n+1, a(n))

f n = take n $ filter (> 1) d -- get rid of 1s and take the first n
Artelius
fuente
4

Pyth, 30 bytes

Muy mal golf, se puede reducir considerablemente. Define la función recursiva en la parte delantera, filtra .fprimero y luego asigna la diferencia.

L?tb+KytbibK7m-yhdyd.ft-yhZyZQ

Pruébalo aquí en línea .

Maltysen
fuente
Esto da la salida incorrecta paran = 0
Sp3000
2
@ Sp3000 que es un error en Pyth. Pondré una solicitud de extracción.
Maltysen
Error encontrado y corregido: el parche se implementará una vez que github deje de ser DDoS'd.
isaacg
1
Aquí está: meta.codegolf.stackexchange.com/questions/5318/… . Personalmente, consideraría la solución de errores en los lenguajes de programación como respuesta
Thomas Weller
2
@ThomasWeller Algo así logró todo el lenguaje ...
isaacg
4

Julia, 69 67 bytes

n->(i=1;a=7;while n>0 x=gcd(i+=1,a);a+=x;x>1&&(n-=1;println(x))end)

Esta es una solución iterativa simple al problema. xes la diferencia (que es el gcd), y luego actualizo aagregando x.

Glen O
fuente
Creo que imprime A231900 .
alephalpha
@alephalpha - Creo que veo el error. Fácilmente arreglado. Incluso recortó dos bytes en el proceso.
Glen O
3

JavaScript (ES6), 91

MCD recursivo, función principal iterativa. No tan rapido.

Nota habitual: pruebe ejecutar el fragmento en cualquier navegador compatible con EcmaScript 6 (en particular, no Chrome ni MSIE. Probé en Firefox, Safari 9 podría funcionar) 

F=m=>{
  for(G=(a,b)=>b?G(b,a%b):a,o=[],p=7,n=1;m;d>1&&(o.push(d),--m))
    p+=d=G(++n,p);
  return o
}

O.innerHTML=F(+I.value)
<input id=I value=10><button onclick='O.innerHTML=F(+I.value)'>-></button>
<pre id=O></pre>
Expandir fragmento

edc65
fuente
3

Haskell, 74 71 66 bytes

f=($filter(>1)$tail>>=zipWith(-)$scanl(\x->(x+).gcd x)7[2..]).take

Usé el truco aquí: https://codegolf.stackexchange.com/a/39730/43318 , y se hizo sin puntos.

(Anterior: 71 bytes)

a=scanl(\x->(x+).gcd x)7[2..]
f m=take m$filter(>1)$zipWith(-)(tail a)a

Primero haga la secuencia de a, y luego tome las diferencias.

(Anterior: 74 bytes)

f m=take m$filter(>1)$map snd$scanl(\(x,d)->(\y->(x+y,y)).gcd x)(7,1)[2..]

Funciones de lista estándar, más el uso inteligente de la función lambda. Tenga en cuenta que esto es 1 byte más corto que el más obvio

g m=take m$filter(>1)$map snd$scanl(\(x,d)n->(x+gcd x n,gcd x n))(7,1)[2..]

Si no contamos las importaciones, puedo reducir esto a 66.

import Data.List
h m=take m$filter(>1)$snd$mapAccumL(\x->(\y->(x+y,y)).gcd x)7[2..]
Holden Lee
fuente
3

PARI / GP, 60 bytes

a(n)=a=7;i=1;while(n,if(1<d=gcd(i+=1,a),n-=1;print(d));a+=d)

Tomado más o menos directamente de la definición a (n) - a (n-1) = mcd (n, a (n-1))

Salida para a(20):

5
3
11
3
23
3
47
3
5
3
101
3
7
11
3
13
233
3
467
3
primo
fuente
2

C ++, 193 182 180 172 bytes

Gracias @Jakube: ahorré 8 bytes en la salida. 

int g(int a,int b){return a==b?a:a>b?g(b,a-b):g(a,b-a);}void f(int *r,int n){int m=1,i=0,a=7,b;while(i<n){b=g(a,++m);if(b>1){r[i]=b;++i;}a+=b;}}int main(){int r[6];f(r,6);}
EvgeniyZh
fuente
Probablemente pueda guardar algunos bytes definiendo una función f, que devuelve una matriz con los resultados. De esta forma, puede eliminar la inclusión, el scanf y la impresión.
Jakube
2

Mathematica, 59 bytes

For[i=j=1;a=7,i<=#,,d=GCD[++j,a];If[d>1,Print@d;i++];a+=d]&
alephalpha
fuente