Calculez le minimum

12

Contexte

Considérez la séquence suivante ( A051935 dans OEIS):

Commencez par le terme . $2$
Trouvez le plus petit entier supérieur à tel que est premier. $n$ $2$ $2+n$
Trouver le plus petit entier supérieur à tel que est premier, etc. $n'$ $n$ $2 + n + n'$

Une définition plus formelle:

a_{n} = {\begin{cases} 2 & if n = 0 \\ min {x \in N ∣ x > a_{n - 1} and (x + \sum_{i = 0}^{n - 1} a_{i}) is prime} & otherwise \end{cases}

$a_n=\begin{cases}2 & \text{if }n=0 \\ \min\{x\in\Bbb{N}\mid x>a_{n-1} \text{ and }\left(x+\sum_{i=0}^{n-1}a_i\right) \text{ is prime}\} & \text{otherwise}\end{cases}$

Les premiers termes de la séquence sont (veuillez les appeler des cas de test):

2, 3, 6, 8, 10, 12, 18, 20, 22, 26, 30, 34, 36, 42, 44, 46, 50, 52, 60, 66, 72, 74, ...

Tâche

Votre tâche consiste à générer cette séquence de l'une des manières suivantes:

Sortir ses termes indéfiniment.
Étant donné $n$ , $a_{n}$ (terme $n^{\text{th}}$ , $0$ ou $1$ indexé).
Étant donné $n$ , sortez $\{a_1, a_2, \dots, a_n\}$ ( premiers $n$ termes).

Vous pouvez concurrencer dans n'importe quel langage de programmation et pouvez prendre des entrées et fournir des sorties par n'importe quelle méthode standard , tout en prenant note que ces failles sont interdites par défaut. C'est du code-golf , donc la soumission la plus courte (en octets) pour chaque langue l' emporte.

code-golf math sequence number-theory primes M. Xcoder
la source

4

Conseils à éviter lors de la rédaction de défis: les nombres premiers . Vous auriez pu utiliser autre chose que la primauté.

Okx

3

@Okx J'avais plusieurs raisons à l'esprit lorsque je choisis la primalité cette fois: 1) Il existe des algorithmes intelligents spécifiques à cette séquence, comme celui mis en œuvre par Dennis 2) Il existe déjà une entrée OEIS pour cela

M. Xcoder

Réponses:

4

Brachylog , 13 octets

~l.<₁a₀ᵇ+ᵐṗᵐ∧

Essayez-le en ligne!

La sortie est la liste des n premiers termes de la séquence.

?~l.<₁a₀ᵇ+ᵐṗᵐ∧    Full code (? at beginning is implicit)

?~l.              Output is a list whose length is the input
    <₁            Output is an increasing list
      a₀ᵇ+ᵐ       And the cumulative sum of the output
           ṗᵐ     Consists only of prime numbers
             ∧    No further constraints on output

Explanation for a₀ᵇ+ᵐ:
a₀ᵇ               Get the list of all prefixes of the list
                  Is returned in increasing order of length
                  For eg. [2, 3, 6, 8] -> [[2], [2, 3], [2, 3, 6], [2, 3, 6, 8]]
   +ᵐ             Sum each inner list  -> [2, 5, 11, 19]

Sundar - Rétablir Monica
la source

4

Python 2 , 63 62 octets

n=f=a=b=1
while 1:
 f*=n;n+=1;a+=1
 if~f%n<a-b:print a;b=a;a=0

Essayez-le en ligne!

Dennis
la source

4

Gelée , 11 9 octets

0Ḥ_ÆnɗÐ¡I

Il s'agit d'un programme complet qui prend n comme argument et affiche les n premiers termes de la séquence.

Essayez-le en ligne!

Comment ça fonctionne

0Ḥ_ÆnɗÐ¡I  Main link. Argument: n

0          Set the return value to 0.
      Ð¡   Accumulating iterate. When acting on a dyadic link d and called with
           arguments x and y, the resulting quicklink executes
           "x, y = d(x, y), x" n times, returning all intermediate values of x.
           Initially, x = 0 and  y = n.
     ɗ       Drei; combine the three links to the left into a dyadic chain.
 Ḥ             Unhalve; double the left argument.
  _            Subtract the right argument.
   Æn          Compute the next prime.
           This computes the partial sums of the sequence a, starting with 0.
        I  Increments; compute the forward differences.

Dennis
la source

3

05AB1E v2 , 10 octets

2λλOD₁+ÅNα

Essayez-le en ligne!

Cela ne fonctionne que dans la version non héritée, la réécriture Elixir. Génère un flux infini d'entiers. Il y a quelques bugs avec le test principal qui ont été corrigés dans les derniers commits, mais qui ne sont pas encore en direct sur TIO. Cela fonctionne cependant localement. Voici un GIF de son exécution sur ma machine, modifié pour sortir les premiers termes plutôt que le flux entier.

Comment ça fonctionne

2λ

Définit une séquence infinie récursive avec le cas de base . La structure fait partie des nouvelles fonctionnalités très intéressantes de 05AB1E. En bref, il prend une fonction , mettant l'argument entier donné, dans ce cas . $2$ λ $a(n)$ $a(0)$ $2$

λO

Dans cette partie du code, λle rôle de est différent. Déjà dans un environnement récursif, il génère à la place , la liste de tous les résultats précédents. Ensuite, les résume. $[a(0),a(1),\dots,a(n-1)]$ O

D₁+

Dupliquez la somme pour une utilisation ultérieure et ajoutez à la deuxième copie. $a(n-1)$

ÅN

Génère le plus petit nombre premier strictement supérieur à la somme ci-dessus.

α

Enfin, récupérez la différence absolue entre le premier calculé ci-dessus et la première copie de la somme calculée précédemment (la somme de toutes les itérations précédentes).

Le flux est ensuite implicitement imprimé dans STDOUT indéfiniment.

M. Xcoder
la source

2

Perl 6 , 45 octets

2,{first (*+@_.sum).is-prime,@_[*-1]^..*}...*

Essayez-le en ligne!

Renvoie une liste paresseuse qui génère la séquence sans fin.

Explication:

Celui-ci utilise l'opérateur Sequence ...qui définit la séquence comme:

2,  # The first element is 2
  {  # The next element is:
    first  # The first value that:
          (*+@_.sum).is-prime,  # When added to the sum is a prime
          @_[*-1]^..*  # And is larger than the previous element
  }
...*  # And continue the sequence indefinitely

Jo King
la source

2

Rubis `-rprime` , 34 octets

2.step{|i|$.+=p(i)if($.+i).prime?}

Essayez-le en ligne!

Sorties indéfiniment.

Kirill L.
la source

2

JavaScript (ES6), 63 octets

Renvoie le terme, indexé sur 1. $n^{th}$

n=>(k=0,s=1,g=d=>s%d?g(d-1):d<2?--n?g(s-=k-(k=s)):s-k:g(s++))()

Essayez-le en ligne!

Arnauld
la source

2

Pyth ,12 11 octets

.f&P-;Z=-;Z

Essayez-le en ligne!

1 octet enregistré grâce à isaacg.

Génère les premiers de nces nombres, en utilisant un index basé sur 1.

.ftrouve les premiers kentiers qui satisfont un critère particulier à partir de zéro. Ici, le critère est que le premier précédent que nous avons calculé ;, plus le nombre actuel Z, est premier ( P). Si c'est le cas, nous mettons également à jour le dernier nombre premier calculé en utilisant le comportement de court-circuitage de la logique et de la fonction ( &). Malheureusement, .fla variable par défaut est celle Zqui coûte un octet dans la mise à jour.

L'astuce qui isaacg a compris était de stocker la négation du dernier nombre premier et de tester sur celle moins la valeur actuelle. Ceci est plus court en Pyth car le contrôle de primalité est surchargé: sur les nombres positifs, il trouve la factorisation première tandis que sur les nombres négatifs, il détermine si la valeur positive du nombre est premier.

Cela se traduit plus ou moins par:

to_find = input()
last_prime = 0
current = 0
results = []
while to_find > 0:
    if is_prime( current + last_prime ):
        results.append( current )
        to_find -= 1
        last_prime += current
    current += 1
print results

FryAmTheEggman
la source

Remplacez _+par -et +par -pour -1 octet.

isaacg

@isaacg C'est assez intelligent! Je vais le modifier.

FryAmTheEggman

2

MATL , 21 octets

O2hGq:"t0)yd0)+_Yqh]d

Essayez-le en ligne!

La sortie est les n premiers termes de la séquence.

Explication:

Construit une liste de nombres premiers (avec un 0 initial), et à la fin trouve les retours des différences entre les nombres premiers successifs dans la liste.

              % Implicit input, say n
O2h           % Push P = [0, 2] on the stack 
Gq:"          % for loop: 1 to n-1
  t0)           % Take the last element of P
                %  Stack: [[0, 2], [2]] (in first iteration)
  yd0)          % Take the difference between the last
                %   two elements of P
                %  Stack: [[0, 2], [2], [2]]
  +             % Add those up
                %  Stack: [[0, 2], [4]]
  _Yq           % Get the next prime higher than that sum
                %  Stack: [[0, 2], [5]]
  h             % Concatenate that to the list P
                %  Stack: [[0, 2, 5]]
]             % End for loop
d             % Get the differences between successive elements of
              %   the final list P

Sundar - Rétablir Monica
la source

2

Haskell , 67 octets

(1#1)2 2
(p#n)s k|p`mod`n>0,n-s>k=k:(p#n)n(n-s)|w<-p*n=(w#(n+1))s k

Essayez-le en ligne!

(1#1)2 2est une fonction qui ne prend aucune entrée et génère une liste infinie.

ancienne réponse:

Haskell , 88 83 78 76 octets

Le test de primalité est issu de cette réponse et amélioré par Christian Sievers (-2 octets).

-5 octets grâce à WW .

2#2
(p#s)n|n<1=p|w<-until(\m->mod(product[1..m-1])m>0)(+1)$s+p+1=(w-s)#w$n-1

Essayez-le en ligne!

ovs
la source

Vous pouvez vous en passer ^2. Cela changera le prédicat de testing is prime à testing is prime ou 4 , ce qui n'a pas d'importance dans cette application.

Christian Sievers

2

05AB1E (hérité) , 12 octets

0U[XN+DpiN,U

Essayez-le en ligne!

Explication

0U              # initialize X as 0
  [             # start an infinite loop
   XN+          # add X to N (the current iteration number)
      Dpi       # if the sum is prime:
         N,     #   print N
           U    #   and store the sum in X

Il existe plusieurs solutions différentes sur 12 octets.
Celui-ci aurait pu être de 10 octets si nous avions une variable utilisable initialisée à 0 (au lieu de 1 et 2).

Emigna
la source

1

Python 2 , 119 octets

f=lambda n,k=1,m=1:m%k*k>n or-~f(n,k+1,m*k*k)
def g(i):
 r=[2]
 for j in range(i):r+=[f(sum(r)+r[-1])-sum(r)]
 return r

Essayez-le en ligne!

Fonction Prime suivante f () tirée de cette réponse .

La fonction g () prend un entier non négatif i et retourne une liste de tous les éléments de la séquence jusqu'à cet index.

Triggernométrie
la source

-7 octets .

M. Xcoder

1

Python 2 , 99 98 octets

def f(n,s=2,v=2):
 k=s-~v
 while any(k%i<1for i in range(2,k)):k+=1
 return n and f(n-1,k,k-s)or v

Essayez-le en ligne!

1 octet merci à M. Xcoder .

Chas Brown
la source

1

Je sais ... Je sais ... Moi et mon pédantisme de trucs au niveau du bit :) Mais vous pouvez économiser un octet avec k=s-~v.

M. Xcoder

@Monsieur. Xcoder: Votre sorcellerie impie au niveau du bit sera encore la fin de vous! :)

Chas Brown

1

Haskell , 101 99 97 octets

La fonction lne prend aucun argument et renvoie une liste infinie. Pas aussi court que l' approche plus directe de @ovs (et j'ai évidemment volé certaines parties de leur réponse), mais peut-être quand même jouable au golf?

Merci @ H.PWiz pour -2 octets!

import Data.List
p m=mod(product[1..m-1])m>0
l=2:[until(p.(+sum a))(+1)$last a+1|a<-tail$inits l]

Essayez-le en ligne!

flawr
la source

1

Python 2 , 82 80 octets

s=p=2
i=input()
P=n=1
while i:
 P*=n;n+=1
 if P%n>0<n-s-p:p=n-s;s=n;i-=1
print p

Essayez-le en ligne!

Ceci sort le nième numéro de la séquence (basé sur 0). En déplaçant le printdans la boucle, cela peut être modifié pour sortir les premiers néléments au même bytecount: Essayez-le en ligne!

ovs
la source

1

C (gcc) , 100 99 octets

Enregistré un octet grâce au plafond .

p(r,i,m,a,l){for(l=m=a=0;a-r;)m+=i=p(a++);while(r*!l)for(++i,l=a=2;a-m-i;)l=(m+i)%a++?l:0;r=r?i:2;}

Essayez-le en ligne!

Jonathan Frech
la source

0

Japt, 17 octets

Produit le ne terme, indexé sur 0.

@_+T j}aXÄT±X}g2ì

Hirsute
la source