Suchen Sie eine Rocco-Nummer

12

Diese Frage wurde mir in einem Interview gestellt, aber ich konnte keine Lösung finden. Ich weiß nicht, ob die Frage richtig war oder nicht. Ich habe viel versucht, konnte aber keine Lösung finden. Ehrlich gesagt kam mir nichts in den Sinn.

Rocco-Nummern

Eine positive ganze Zahl n ist eine Rocco-Zahl, wenn sie entweder als n=p(p+14) oder n=p(p-14) , wobei p eine Primzahl ist.

Die ersten 10 Rocco-Nummern sind:

32,51,95,147,207,275,351,435,527,627

Aufgabe

Ihr Code muss eine positive Ganzzahl als Eingabe akzeptieren und bestimmen, ob es sich um eine Rocco-Nummer handelt oder nicht.

Pluspunkte

  • Schreiben Sie eine Funktion, die die Anzahl der Rocco-Zahlen kleiner oder gleich 1 Million berechnet und druckt.
  • Schreiben Sie eine Funktion, die die Anzahl der Rocco-Zahlen aus der Bonusfrage (über einer) berechnet und druckt, die Primzahlen sind.
vijayscode
quelle
5
Hallo und willkommen bei PPCG. Wir veranstalten Herausforderungen (Ihre sehen sehr interessant aus), die objektive Punkte und Gewinnkriterien haben. Versuchen Sie, Ihren Beitrag zu bearbeiten, um dies einzuschließen. Ich empfehle Code-Golf als Ziel, da es am einfachsten ist, das Richtige zu finden. Außerdem möchten Sie diese Boni vermeiden. Konzentrieren Sie sich nur auf eine klare Aufgabe.
Adám
3
output wäre eine ganze Zahl : Meinst du nicht einen Booleschen Wert für die Eingabe einer Rocco-Zahl oder nicht?
Adám
5
Bonus 2: print 0. Alle Rocco-Zahlen sind zusammengesetzt (n*..), also keine Primzahlen in irgendeinem Bereich.
TFeld
4
Die "Bonuspunkte" können einfach fest codierte Werte sein und kommen der Herausforderung überhaupt nicht zugute. Ich empfehle sie zu entfernen.
Erik der Outgolfer
5
Ich habe die Frage und die Tags bearbeitet. Wenn Sie nicht einverstanden sind, können Sie das Rollback oder die Bearbeitung fortsetzen. Wie @EriktheOutgolfer sagte, denke ich, dass die Prämien entfernt werden sollten.
Arnauld

Antworten:

10

05AB1E , 8 Bytes

Gibt 1 wenn n eine Rocco-Zahl ist, oder sonst 0 .

fDŠ/α14å

Probieren Sie es online!

Wie?

Bei einer positiven ganzen Zahl n testen wir, ob ein Primfaktor p von existiertn so dass:

|p-np|=14

Kommentiert

fDŠ/α14å  # expects a positive integer n as input       e.g. 2655
f         # push the list of unique prime factors of n  -->  2655, [ 3, 5, 59 ]
 D        # duplicate it                                -->  2655, [ 3, 5, 59 ], [ 3, 5, 59 ]
  Š       # moves the input n between the two lists     -->  [ 3, 5, 59 ], 2655, [ 3, 5, 59 ]
   /      # divide n by each prime factor               -->  [ 3, 5, 59 ], [ 885, 531, 45 ]
    α     # compute the absolute differences
          # between both remaining lists                -->  [ 882, 526, 14 ]
     14å  # does 14 appear in there?                    -->  1
Arnauld
quelle
11

JavaScript (ES7), 55 Byte

n=>(g=k=>k>0&&n%--k?g(k):k==1)(n=(49+n)**.5-7)|g(n+=14)

Probieren Sie es online!

Wie?

Gegeben eine positive ganze Zahl n , wir suchen ein erstklassigen x , so daß x(x+14)=n oder x(x-14)=n .

Daher die folgenden quadratischen Gleichungen:

(1)x2+14x-n=0
(2)x2-14x-n=0

Die positive Wurzel von (1) ist:

x0=49+n-7

und die positive Wurzel von (2) ist:

x1=49+n+7

Daher ist das Problem gleichbedeutend mit dem Testen, ob entweder x0 oder x1 eine Primzahl ist.

Dazu verwenden wir die klassische Funktion für den rekursiven Primalitätstest und einen zusätzlichen Test, um sicherzustellen, dass keine Endlosschleife erfolgt, wenn als Eingabe eine irrationale Zahl angegeben wird.

g = k =>    // k = explicit input; this is the divisor
            // we assume that the implicit input n is equal to k on the initial call
  k > 0 &&  // abort if k is negative, which may happen if n is irrational
  n % --k ? // decrement k; if k is not a divisor of n:
    g(k)    //   do a recursive call
  :         // else:
    k == 1  //   returns true if k is equal to 1 (n is prime)
            //   or false otherwise (n is either irrational or a composite integer)

Hauptverpackungsfunktion:

n => g(n = (49 + n) ** .5 - 7) | g(n += 14)
Arnauld
quelle
6

Perl 6 , 45 28 Bytes

((*+49)**.5+(7|-7)).is-prime

Probieren Sie es online!

n+49±7n

Erläuterung:

 (*+49)**.5                   # Is the sqrt of input+49
           +(7|-7)            # Plus or minus 7
(                 ).is-prime  # Prime?
Scherzen
quelle
6

Regex (ECMAScript), 64 62 Bytes

einein+14n=ein(ein+14)einein+14 Primzahl ist. Das ist es!

Dies verwendet eine Variante des Multiplikationsalgorithmus, der kurz in einem Absatz meines Postings mit vielen regulären Zahlen beschrieben wird . Das ist ein Spoiler . So lesen keine weiteren , wenn Sie nicht einige erweiterte einstellige regex Magie für Sie verwöhnen wollen . Wenn Sie versuchen möchten, diese Magie selbst herauszufinden, empfehle ich dringend, zunächst einige Probleme in der Liste der in diesem früheren Beitrag mit Spoiler-Tags gekennzeichneten empfohlenen Probleme zu lösen und zu versuchen, die mathematischen Erkenntnisse unabhängig voneinander zu entwickeln.

Der Multiplikationsalgorithmus wird hier anders implementiert, weil wir annehmen, dass zwei bekannte Werte, die zusammen multipliziert werden, einem anderen bekannten Wert entsprechen (wie auch in der alternativen Version des regulären Ausdrucks in diesem Beitrag , um zu testen , ob eine Zahl ein perfektes Quadrat ist). In den meisten meiner bisherigen Antworten auf reguläre Ausdrücke wird die Multiplikation als Berechnung (begrifflich keine Behauptung) implementiert, bei der das Ziel darin besteht, das Produkt aus zwei bekannten Zahlen zu finden. Beide Methoden funktionieren unter beiden Umständen, aber in Bezug auf das Golfen sind sie schlechter, wenn sie sich gegenseitig unterstützen.

^(?=(x((x{14})(x+)))(?=(\1*)\4\2*$)(\1*$\5))\6\3?(?!(xx+)\7+$)

Probieren Sie es online!


 # For the purposes of these comments, the input number = N.
 ^
 # Find two numbers A and A+14 such that A*(A+14)==N.
 (?=
     (x((x{14})(x+)))   # \1 = A+14; \2 = \1-1; \3 = 14; \4 = A-1; tail -= \1
     (?=                # Assert that \1 * (\4+1) == N.
         (\1*)\4\2*$    # We are asserting that N is the smallest number satisfying
                        # two moduli, thus proving it is the product of A and A+14
                        # via the Chinese Remainder Theorem. The (\1*) has the effect
                        # of testing every value that satisfies the "≡0 mod \1"
                        # modulus, starting with the smallest (zero), against "\4\2*$",
                        # to see if it also satisfies the "≡\4 mod \2" modulus; if any
                        # smaller number satisfied both moduli, (\1*) would capture a
                        # nonzero value in \5. Note that this actually finds the
                        # product of \4*\1, not (\4+1)*\1 which what we actually want,
                        # but this is fine, because we already subtracted \1 and thus
                        # \4*\1 is the value of tail at the start of this lookahead.
                        # This implementation of multiplication is very efficient
                        # golf-wise, but slow, because if the number being tested is
                        # not even divisible by \1, the entire test done inside this
                        # lookahead is invalid, and the "\1*$" test below will only
                        # fail after this useless test has finished.
     )
     (\1*$\5)           # Assert that the above test proved \1*(\4+1)==N, by
                        # asserting that tail is divisible by \1 and that \5==0;
                        # \6 = tool to make tail = \1
 )
 # Assert that either A or A+14 is prime.
 \6                     # tail = \1 == A+14
 \3?                    # optionally make tail = A
 (?!(xx+)\7+$)          # Assert tail is prime. We don't need to exclude treating
                        # 1 as prime, because the potential false positive of N==15
                        # is already excluded by requiring \4 >= 1.
 

Deadcode
quelle
3

Brachylog , 13 12 Bytes

ṗ;14{+|-};?×

Geben Sie die Kandidatennummer als Befehlszeilenargument ein. Ausgänge trueoder false. Probieren Sie es online!

Erläuterung

Der Code ist ein Prädikat, dessen Eingabe nicht eingeschränkt ist und dessen Ausgabe die Zahl ist, die wir testen.

ṗ             Let the input ? be a prime number
 ;14          Pair it with 14, yielding the list [?, 14]
    {+|-}     Either add or subtract, yielding ?+14 or ?-14
         ;?   Pair the result with the input, yielding [?+14, ?] or [?-14, ?]
           ×  Multiply; the result must match the candidate number

(Trinkgelder sind willkommen. Das {+|-}fühlt sich immer noch klobig an.)

DLosc
quelle
3

Brachylog , 9 Bytes

Anderer Ansatz als die Antwort von DLosc

Ċ-14&∋ṗ&×

N als Ausgabe nehmen, [P, P-14] oder [P + 14, P] durch Eingabe zurückgeben (größte Zahl zuerst)

Erläuterung

Ċ              # The 'input' is a pair of numbers
 -14           #   where the 2nd is 14 smaller then the first
    &∋ṗ        #   and the pair contains a prime
       &×      #   and the numbers multiplied give the output (N)

Probieren Sie es online!

Kroppeb
quelle
2

Pyth, 22 bis 20 Bytes

}Qsm*Ld+Ld_B14fP_TSh

Probieren Sie es hier online aus .

}Qsm*Ld+Ld_B14fP_TShQ   Implicit: Q=eval(input())
                        Trailing Q inferred
                  ShQ   Range [1-(Q+1)]
              fP_T      Filter the above to keep primes
   m                    Map the elements of the above, as d, using:
          _B14            [14, -14]
       +Ld                Add d to each
    *Ld                   Multiply each by d
  s                     Flatten result of map
}Q                      Is Q in the above? Implicit print

Bearbeiten: Gespeicherte 3 Bytes als Eingabe sind immer positiv, sodass keine negativen Werte aus der Liste herausgefiltert werden müssen. Auch einen Fehler für die Eingänge festgelegt 1und 2, kostet 1 Byte. Vorherige Version:}Qsm*Ld>#0+Ld_B14fP_TU

Sok
quelle
2

05AB1E , 16 15 14 Bytes

1 Byte durch Berechnen von 14 mit anstelle von žvÍ(kann nicht glauben, dass ich nicht an erster Stelle darüber nachgedacht habe) gespeichert.

Dank Emigna 1 Byte gespeichert

ÅPε7·D(‚+y*Q}Z

Probieren Sie es online! oder Alle Eingänge testen

Erläuterung

                 # Implicit input n
ÅP               # Push a list of primes up to n
  ε         }    # For each prime in the list...
   7·            # Push 14 (by doubling 7)
     D(‚         # Push -14 and pair them together to get [14,-14]
        +        # Add [14,-14] to the prime
         y*      # Multiply the prime to compute p(p-14) and p(p+14)
           Q     # Check if the (implicit) input is equal to each element
             Z   # Take the maximum
Wisław
quelle
1
Sie können ein Byte speichern }˜så, Q}Zindem Sie die implizite Eingabe verwenden. Ihre Testsuite werden müßte ein bisschen so etwas wie verändert auf diese , um es dann zu arbeiten. Auch eine naheliegendere Schreibweise žvÍoder wäre 14;)
Emigna
Vielen Dank! Warum es einfach machen, wenn Sie 14 auf die komplizierteste Weise /
facepalm
2

Retina 0.8.2 , 61 Bytes

.+
$*
^((1{14})1(1)+)(?<=(?<!^\4+(..+))\2?)(?<-3>\1)+$(?(3)1)

Probieren Sie es online! Erläuterung:

.+
$*

In Unary konvertieren.

^((1{14})1(1)+)

\1erfasst den größeren der beiden Faktoren. \2erfasst die Konstante 14 und speichert ein Byte. \3erfasst den kleineren der beiden Faktoren minus 1. Dies stellt auch sicher, dass beide Faktoren mindestens 2 sind.

(?<=(?<!^\4+(..+))\2?)

Überprüfen Sie die beiden Faktoren, um sicherzustellen, dass mindestens einer der Faktoren prim ist. Die Idee der Verwendung \2?wurde schamlos aus der Antwort von @ Deadcode gestohlen.

(?<-3>\1)+

Wiederholen Sie den größeren der beiden Faktoren so oft, bis er um eins niedriger ist als der kleinere der beiden Faktoren. Da wir den größeren Faktor bereits einmal erfasst haben, führt dies dazu, dass das Produkt der beiden Faktoren erfasst wird.

$(?(3)1)

Stellen Sie sicher, dass das Produkt der angegebenen Anzahl entspricht.

Eine direkte Übersetzung in Retina 1 durch Ersetzen $*durch *1hätte die gleiche Byteanzahl, aber ein Byte könnte durch Ersetzen aller 1s durch _s gespeichert werden, und das *1könnte dann durch *anstatt ersetzt werden *_. Vorherige Retina 1 Antwort für 68 Bytes:

.+
*
Lw$`^(__+)(?=(\1)+$)
$1 _$#2*
Am` (__+)\1+$
(_+) \1

0m`^_{14}$

Probieren Sie es online! Erläuterung:

.+
*

In Unary konvertieren.

Lw$`^(__+)(?=(\1)+$)
$1 _$#2*

Finden Sie alle Faktorenpaare.

Am` (__+)\1+$

Stellen Sie sicher, man ist prime.

(_+) \1

Nehmen Sie den absoluten Unterschied.

0m`^_{14}$

Überprüfen Sie, ob 14 vorhanden sind.

Neil
quelle
1

JavaScript (Babel Node) , 69 Byte

Verdammt, ich dachte, ich würde Arnaulds 'Antwort besiegen, aber nein .....: c

x=>[...Array(x)].some((a,b)=>x/(a=(p=n=>--b-1?n%b&&p(n):n)(b))-a==14)

Probieren Sie es online!

Ich möchte das x=>[...Array(x)].some(Teil mithilfe der Rekursion entfernen, damit es mit der Zeit kürzer wird

Erläuterung

x=>[...Array(x)]                                                              Creates a range from 0 to x-1 and map:

                .some((a,b)=>                                                 Returns True if any of the following values is true
                             x/                                              Input number divided by
                                (a=(p=n=>--b-1?n%b&&p(n):n)(b))               recursive helper function. Receives a number (mapped value) as parameters and returns 
                                                                              the same number if it is prime, otherwise returns 1. Take this value
                                                                              and assign to variable a
                                                               -a            Subtract a from the result  
                                                                     ==14    Compare result equal to 14

Es wird die Formel verwendet

n/p-p==14

Luis Felipe De Jesus Munoz
quelle
1

APL (NARS) 16 Zeichen, 32 Byte

{14=∣r-⍵÷r←↑⌽π⍵}

{π⍵} würde die Faktorisierung seines Arguments finden und wir nehmen an, dass das letzte Element seines Ergebnisses (die Liste der Teiler von n) der maximale Primteiler von n ist; Hier nehmen wir an, dass eine äquivalente Definition der Rocco-Zahl ist: n ist eine Rocco-Zahl <=> Max-Faktor-Primzahl von n: r ist so, dass es wahr ist 14 = ∣rn ÷ r [für C Pseudocode als 14 == abs (rn / r) diese Definition der Rocco-Zahl scheint endlich im Bereich 1..1000000 in Ordnung zu sein]; der Bereich des ok-Wertes wäre 1..maxInt; Prüfung:

 f←{14=∣r-⍵÷r←↑⌽π⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨1..10000
32  51  95  147  207  275  351  435  527  627  851  1107  1247  1395  1551  1887  2067  2255  2451  2655  2867  3551  4047  4307  4575  5135  5427  5727  6035  6351  6675  7347  8051  8787  9167  9951   
RosLuP
quelle
1

C # (Visual C # Interactive Compiler) , 99 Byte

n=>Enumerable.Range(2,n).Any(p=>Enumerable.Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

Probieren Sie es online!

Enumerable.Range schlägt wieder zu :) Mit der verrückten Compiler-Flagge kann man die Dinge ein wenig reduzieren, obwohl ich ein bisschen ein Fan der Vanille-Lösung bin.

C # (Visual C # Interactive Compiler) + /u:System.Linq.Enumerable, 77 Byte

n=>Range(2,n).Any(p=>Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

Probieren Sie es online!

Unten ist eine Portierung von Arnauld's Lösung, die ziemlich cool wirkte. Es ist derzeit das längste, aber es kann wahrscheinlich einige Golf gespielt werden.

C # (Visual C # Interactive Compiler) , 101 Byte

n=>{bool g(int k)=>--k<2?n>1:n%k>0&g(k);var d=Math.Sqrt(n+49)-7;return(n=(int)d)==d&(g(n)|g(n+=14));}

Probieren Sie es online!

Dana
quelle
0

APL (NARS) 30 Zeichen, 60 Byte

{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}

Hier ist 0π die Funktion sagen, wenn eine Zahl eine Primzahl ist, Test:

 f←{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨0..700
32  51  95  147  207  275  351  435  527  627
RosLuP
quelle
0

F #, 2 Antworten (nicht konkurrierend)

Die Antworten von @Arnauld haben mir sehr gut gefallen, deshalb habe ich sie übersetzt.

123 Bytes , basierend auf der JavaScript-Antwort

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||)

Erläuterung:

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||) //Lambda which takes an integer, n
       let t=int<|sqrt(float n+49.)                                                                                         //let t be n, converted to float, add 49 and get square root, converted back to int (F# type restrictions)
                                   in                                                                                       //in the following...
                                                                                                  [t-7;t+7]                 //Subtract and add 7 to t in a list of 2 results (Lists and Seqs can be interchanged various places)
                                      Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)                          //See if either are prime (here, if either result has 2 and only 2 divisors)
                                                                                                           |>Seq.reduce(||) //And logically OR the resulting sequence

125 Bytes , basierend auf der 05AB1E-Antwort

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14

Erläuterung:

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14  //Lambda which takes an integer, n
       let l=Seq.filter(fun i->n%i=0)[2..n-1]                                                                                  //let l be the list of n's primes 
                                             in                                                                                //in...
                                                let m=Seq.map(fun i->n/i)l                                                     //m, which is n divided by each of l's contents
                                                                           in                                                  //and then...
                                                                              Seq.map2(fun a b->abs(a-b))l m                   //take the absolute difference between each pair of items in the two sequences to make a new sequence
                                                                                                            |>Seq.contains 14  //and does the resulting sequence contain the number 14?
LSM07
quelle
0

Python 2 , 58 Bytes

Ausgabe nach Exit-Code, fail ( 1) für Rocco-Nummern.

P=k=1.
n=input()
exec"P*=k*k;k+=1;P%k*abs(n/k-k)==14>y;"*n

Probieren Sie es online!

ovs
quelle