Berechnen Sie das Minimum

12

Hintergrund

Betrachten Sie die folgende Sequenz ( A051935 in OEIS):

Beginnen Sie mit dem Begriff $2$ .
Finden Sie die niedrigste ganze Zahl größer als so dass eine Primzahl ist. $n$ $2$ $2+n$
Finden Sie die niedrigste ganze Zahl größer als so dass Primzahl usw. ist. $n'$ $n$ $2 + n + n'$

Eine formalere Definition:

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

Die ersten Begriffe der Sequenz sind (bitte bezeichnen Sie diese als Testfälle):

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

Aufgabe

Ihre Aufgabe ist es, diese Sequenz auf eine der folgenden Arten zu generieren:

Geben Sie die Begriffe auf unbestimmte Zeit aus.
Bei wird ausgegeben ( Term, oder indiziert). $n$ $a_{n}$ $n^{\text{th}}$ $0$ $1$
Bei wird ausgegeben (erste Terme). $n$ $\{a_1, a_2, \dots, a_n\}$ $n$

Sie können in jeder Programmiersprache antreten und über jede Standardmethode Eingaben und Ausgaben vornehmen. Beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind. Dies ist Codegolf , daher gewinnt die kürzeste Übermittlung (in Bytes) für jede Sprache .

code-golf math sequence number-theory primes Mr. Xcoder
quelle

4

Tipps zum Vermeiden beim Schreiben von Herausforderungen: Die Primzahlen . Du hättest etwas anderes als die Ursprünglichkeit gebrauchen können.

Okx

3

@Okx Ich hatte ein paar Gründe im Hinterkopf, als ich diesmal Primalität gewählt habe: 1) Es gibt einige clevere Algorithmen, die für diese Sequenz spezifisch sind, wie die, die Dennis implementiert hat. 2) Es gibt bereits einen OEIS-Eintrag dafür

Mr. Xcoder

Antworten:

4

Brachylog , 13 Bytes

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

Probieren Sie es online!

Ausgabe ist die Liste der ersten n Terme der Sequenz.

?~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 - Setzen Sie Monica wieder ein
quelle

4

Python 2 , 63 62 Bytes

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

Probieren Sie es online!

Dennis
quelle

4

Jelly , 11 9 Bytes

0Ḥ_ÆnɗÐ¡I

Dies ist ein vollständiges Programm, das n als Argument verwendet und die ersten n Terme der Sequenz ausgibt.

Probieren Sie es online!

Wie es funktioniert

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
quelle

3

05AB1E v2 , 10 Bytes

2λλOD₁+ÅNα

Probieren Sie es online!

Dies funktioniert nur in der Nicht-Legacy-Version, dem Elixir-Rewrite. Gibt einen unendlichen Strom von ganzen Zahlen aus. Es gibt einige Fehler mit dem Primetest, die in den letzten Commits behoben wurden, aber noch nicht auf TIO live sind. Es funktioniert jedoch lokal. Hier ist ein GIF der Ausführung auf meinem Computer, das so geändert wurde, dass die ersten Begriffe und nicht der gesamte Stream ausgegeben werden.

Wie es funktioniert

2λ

$2$ λ $a(n)$ $a(0)$ $2$

λO

λ $[a(0),a(1),\dots,a(n-1)]$ O

D₁+

$a(n-1)$

ÅN

Erzeugt die niedrigste Primzahl, die strikt größer als die obige Summe ist.

α

Abschließend erhalten Sie die absolute Differenz zwischen der oben berechneten Primzahl und der ersten Kopie der zuvor berechneten Summe (der Summe aller vorherigen Iterationen).

Der Stream wird dann implizit auf unbestimmte Zeit nach STDOUT gedruckt.

Mr. Xcoder
quelle

2

Perl 6 , 45 Bytes

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

Probieren Sie es online!

Gibt eine Lazy List zurück, die die Sequenz ohne Ende generiert.

Erläuterung:

Dies verwendet ...den Sequenzoperator, der die Sequenz definiert als:

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

Scherzen
quelle

2

Ruby `-rprime` , 34 Bytes

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

Probieren Sie es online!

Ausgänge auf unbestimmte Zeit.

Kirill L.
quelle

2

JavaScript (ES6), 63 Byte

$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++))()

Probieren Sie es online!

Arnauld
quelle

2

Pyth ,12 11 Bytes

.f&P-;Z=-;Z

Probieren Sie es online!

Dank isaacg 1 Byte gespeichert.

Erzeugt die ersten nderartigen Zahlen unter Verwendung eines 1-basierten Index.

.ffindet die ersten kganzen Zahlen, die ein bestimmtes Kriterium erfüllen, beginnend mit Null. Hier ist das Kriterium, dass die zuvor berechnete Primzahl ;plus die aktuelle Zahl Zeine Primzahl ( P) ist. In diesem Fall aktualisieren wir auch die zuletzt berechnete Primzahl anhand des Kurzschlussverhaltens von Logik und Funktion ( &). Leider ist .fdie StandardvariableZ die die ein Byte im Update kostet.

Der Trick, der herausgefunden wurde, bestand darin, die Negation der letzten Primzahl zu speichern und darauf abzüglich des aktuellen Werts zu testen. Dies ist in Pyth kürzer, da die Primalitätsprüfung überlastet ist: Bei positiven Zahlen wird die Primfaktorisierung gefunden, während bei negativen Zahlen bestimmt wird, ob der positive Wert der Zahl eine Primzahl ist.

Dies bedeutet mehr oder weniger:

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
quelle

Ersetzen Sie _+mit -und +mit -für -1 Byte.

isaacg

@isaacg Das ist ziemlich schlau! Ich bearbeite das in.

FryAmTheEggman

2

MATL , 21 Bytes

O2hGq:"t0)yd0)+_Yqh]d

Probieren Sie es online!

Ausgabe sind die ersten n Terme der Sequenz.

Erläuterung:

Erstellt eine Liste von Primzahlen (mit einer anfänglichen 0) und ermittelt am Ende die Rückgabewerte der Unterschiede zwischen aufeinanderfolgenden Primzahlen in der 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 - Setzen Sie Monica wieder ein
quelle

2

Haskell , 67 Bytes

(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

Probieren Sie es online!

(1#1)2 2ist eine Funktion, die keine Eingabe annimmt und eine unendliche Liste ausgibt.

alte antwort:

Haskell , 88 83 78 76 Bytes

Der Primalitätstest stammt aus dieser Antwort und wurde von Christian Sievers (-2 Bytes) verbessert .

-5 Bytes dank 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

Probieren Sie es online!

ovs
quelle

Sie können ohne tun ^2. Das ändert das Prädikat von "Test ist Primzahl" in "Test ist Primzahl" oder "4" , was in dieser Anwendung keine Rolle spielt.

Christian Sievers

2

05AB1E (Legacy) , 12 Byte

0U[XN+DpiN,U

Probieren Sie es online!

Erläuterung

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

Es sind verschiedene 12-Byte-Lösungen möglich.
Diese bestimmte Variable hätte 10 Byte lang sein können, wenn eine verwendbare Variable mit 0 initialisiert worden wäre (anstelle von 1 und 2).

Emigna
quelle

1

Python 2 , 119 Bytes

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

Probieren Sie es online!

Nächste Prime-Funktion f () aus dieser Antwort .

Die Funktion g () nimmt eine nicht negative ganze Zahl i und gibt eine Liste aller Elemente in der Sequenz bis zu diesem Index zurück.

Triggernometrie
quelle

-7 Bytes .

Mr. Xcoder

1

Python 2 , 99 98 Bytes

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

Probieren Sie es online!

1 Byte Danke an Mr. Xcoder .

Chas Brown
quelle

1

Ich weiß ... ich weiß ... ich und meine bitweisen Tricks Pedanterie :) Aber Sie können ein Byte mit retten k=s-~v.

Mr. Xcoder

@Herr. Xcoder: Deine unheilige bitweise Zauberei wird dich noch erledigen! :)

Chas Brown

1

Haskell , 101 99 97 Bytes

Die Funktion lakzeptiert keine Argumente und gibt eine unendliche Liste zurück. Nicht so kurz wie die direktere Herangehensweise von @ovs (und ich habe offensichtlich einige Teile aus ihrer Antwort gestohlen), aber vielleicht immer noch golffähig?

Danke @ H.PWiz für -2 Bytes!

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]

Probieren Sie es online!

Fehler
quelle

1

Python 2 , 82-80 Bytes

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

Probieren Sie es online!

Dies gibt die n-te Nummer der Sequenz aus (0-basiert). Durch Bewegen des printin der Schleife kann dies geändert werden, um die ersten nElemente mit demselben bytecount auszugeben: Probieren Sie es online aus!

ovs
quelle

1

C (gcc) , 100 bis 99 Bytes

Dank ceilingcat wurde ein Byte gespeichert .

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

Probieren Sie es online!

Jonathan Frech
quelle

0

Japt, 17 Bytes

Gibt den ndritten Term mit dem Index 0 aus.

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

Zottelig
quelle