Andere Primes als Optimus

36

Herausforderung

Bei einer gegebenen Eingang ganzzahligen n > 0Ausgang die Anzahl der Primzahlen ( andere als das n, wenn nich eine Primzahl ist ) , die durch die Veränderung eine Ziffer in der Dezimaldarstellung von n erzeugt werden kann (ohne die Anzahl der Ziffern zu ändern).

Beispiele

Zum Beispiel n = 2. Durch die Veränderung einer Ziffer in der Dezimalentwicklung 2, können wir mit drei weiteren Primzahlen kommen, 3, 5, 7so a(n) = 3.

Für ein anderes Beispiel n = 13. Durch die Veränderung einer Ziffer, können Sie Primzahlen 11, 17, 19, 23, 43, 53, 73, 83, so a(13) = 8.

Als letztes Beispiel n = 20. Durch die Veränderung einer Ziffer, können Sie Primzahlen 23, 29, so a(20) = 2.

Sequenz

Hier sind die ersten 20 Begriffe, mit denen Sie beginnen können. Dies ist OEIS A048853 .

4, 3, 3, 4, 3, 4, 3, 4, 4, 4, 7, 4, 8, 4, 4, 4, 7, 4, 7, 2

Regeln

  • Es kann davon ausgegangen werden, dass die Eingabe und Ausgabe in den systemeigenen Ganzzahltyp Ihrer Sprache passen.
  • Die Ein- und Ausgabe kann in jedem beliebigen Format erfolgen .
  • Führende Nullen ignorieren (zum Beispiel 03ist in dieser Formulierung keine Primzahl).
  • Es ist entweder ein vollständiges Programm oder eine Funktion zulässig. Bei einer Funktion können Sie die Ausgabe zurückgeben, anstatt sie zu drucken.
  • Fügen Sie nach Möglichkeit einen Link zu einer Online-Testumgebung hinzu, damit andere Benutzer Ihren Code ausprobieren können!
  • Standardlücken sind verboten.
  • Dies ist daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.
AdmBorkBork
quelle
4
Ich versuche, an das kleinste zu denken, nfür das die Ausgabe ist 0. Ich denke es ist n = 200. Ich denke auch , sie kommen in Trauben: 200,202,204,206,208, 320,322,...,328, 510,...,518, 620,...628, 840,...,848etc.
Ingenieur Toast
Stellt "Die Eingabe und Ausgabe muss in den systemeigenen Integer-Typ Ihrer Sprache passen" fest, dass keine Eingabe als Zeichenfolge zulässig ist?
Dead Possum
1
@DeadPossum Nein, das ist erlaubt. Nur, dass Sie sich keine Sorgen um 2 ^ 100 als Eingabe machen müssen, wenn Sie beispielsweise nur 32-Bit-Ganzzahlen verwenden.
AdmBorkBork
Lassen Sie mich wissen, wenn ich über Bord gehe ... Ich habe jetzt 3 verschiedene Einreichungen
Patrick Roberts
2
@EngineerToast Nachdem ich die erste Beispiel-Primzahl (294001) gefunden hatte, überlegte ich mir, sie in OEIS nachzuschlagen : A192545 und A158124 . Ebenfalls relevant: A143641 .
Ørjan Johansen

Antworten:

10

05AB1E , 17 16 14 11 Bytes

ā°`<Ÿʒ.L}pO

Erläuterung:

ā             Push inclusive range from 1 to the length of the input
 °            Raise 10 to the power of each element
  `           Push each element to the stack
   <          Decrement the topmost element
    Ÿ         Inclusive range
              For 13, this creates an array like [10 11 12 13 14 .. 98 99]
     ʒ.L}     Only keep elements with a levenshtein distance to the input of
              exactly one
         p    Check each element for primality
          O   Sum

Probieren Sie es online! oder bis zu 100 .

Okx
quelle
1
.L? Ernst? .L?!?!
Erik der Outgolfer
@EriktheOutgolfer L.
Okx
Ich meine, es gibt eine eingebaute für die Entfernung!
Erik der Outgolfer
@EriktheOutgolfer ¯ \ _ (ツ) _ / ¯
Okx
Ich weiß, es ist schon eine Weile her, aber Sie können das entfernen <, um ein Byte zu speichern. Auch wenn der Filter 100/ 1000/ 10000/ etc nicht entfernt , ist es sowieso nie eine Primzahl und hat keinen Einfluss auf die Ausgabe.
Kevin Cruijssen
5

Python 2 , 146 136 127 121 118 Bytes

Danke an @ Mr.Xcoder für die Vorschläge

lambda I:sum(all(i%v for v in range(2,i))*sum(z!=x for z,x in zip(I,`i`))==1for i in range(1+10**~-len(I),10**len(I)))

Erläuterung:

Generieren Sie Zahlen mit einer Länge, die der eingegebenen Länge entspricht. Überspringen Sie zuerst (1,10,100,1000, ...).

for i in range(1+10**~-len(I),10**len(I))

Stellen Sie sicher, dass sich die generierte Nummer nur um eine Ziffer von der Eingabe unterscheidet

sum(z!=x for z,x in zip(I,`i`))==1

Auf Prime prüfen

all(i%v for v in range(2,i))

Anzahl

sum(...)    

Probieren Sie es online!

Totes Opossum
quelle
Könnte es kürzer sein, dies nicht zu einem Lambda zu machen, und zwar r=range, weil Sie es oft verwenden ...?
Stewie Griffin
1
Funktioniert das für Dinge wie 143? Weil ich sehe range(1,10), das schließt aus 0und 103ist prime
Mr. Xcoder
@ Mr.Xcoder behoben
Dead Possum
1
Sie brauchen nicht 0in r(0,10). r(10)genügt.
Mr. Xcoder
1
Ich schlage auch vor, es so lambda I,r=range:
auszudrücken
4

Javascript (ES6) 148 Bytes

Nimmt die Eingabe als Zeichenfolge und gibt sie als Zahl zurück

n=>(n.replace(/./g,"$`a$' ").split` `.map(s=>s&&[..."0123456789"].map(d=>r+=+(t=s.replace(/a/,d))[0]&&t^n&&(p=v=>t>1&(--v<2||t%v&&p(v)))(t)),r=0),r)

Beispielcode-Snippet:

f=
n=>(n.replace(/./g,"$`a$' ").split` `.map(s=>s&&[..."0123456789"].map(d=>r+=+(t=s.replace(/a/,d))[0]&&t^n&&(p=v=>t>1&(--v<2||t%v&&p(v)))(t)),r=0),r)

for(var k=1;k<=20;k++)
  o.innerText+=f(""+k)+" "
<pre id=o></pre>

Herman L
quelle
3

Mathematica, 105 Bytes

F=Count[Range[f=IntegerDigits;g=10^Length@f@#/10,10g],n_/;PrimeQ@n&&MatchQ[f@n-f@#,{x=0...,_,x}]&&n!=#]&;

Probieren Sie es online!

Functiondas erwartet eine positive ganze Zahl #. Setzt fgleich der Funktion, IntegerDigitsdie die Liste der Ziffern ihrer Eingabe zurückgibt. Wir nehmen das Rangevon gbis 10g(einschließlich), wobei g=10^Length@f@#/10die größte Potenz 10kleiner oder gleich der Eingabe ist #, dann Countdie nsolche, dass PrimeQ@n&&MatchQ[f@n-f@#,{x=0...,_,x}]&&n!=#. PrimeQ@nprüft, ob nes sich um eine Primzahl handelt, MatchQ[f@n-f@#,{x=0...,_,x}]prüft, ob der Unterschied zwischen der Liste der Ziffern von nund #der Form entspricht {0..., _, 0...}, und n!=#stellt sicher, dass nund #sind Unequal.

Genisis
quelle
3

JavaScript (ES6), 153 142 139 Byte

n=>([...n].map((c,i,[...a])=>[...''+1e9].map((u,j)=>s+=j+i&&j!=c?p((a.splice(i,1,j),a.join``)):0),s=0,p=q=>eval('for(k=q;q%--k;);k==1')),s)

Akzeptiert Eingaben als Zeichenfolge. Undefiniertes Verhalten bei ungültigen Eingaben, obwohl es bei jeder erdenklichen Zeichenfolge fehlerfrei enden sollte. Nicht unbedingt vor dem Hitzetod des Universums, besonders für lange Saiten.

Demo

f=
n=>([...n].map((c,i,[...a])=>[...''+1e9].map((u,j)=>s+=j+i&&j!=c?p((a.splice(i,1,j),a.join``)):0),s=0,p=q=>eval('for(k=q;q%--k;);k==1')),s)
console.log([...''+1e19].map((_,i)=>f(i+1+'')).join())
i.onchange=()=>console.log(f(i.value))
<input id=i>

Verbesserungen

Sie haben 11 Byte eingespart, indem Sie die reduce()Aufrufe in map()Aufrufe umgestaltet und das Array implizit ain den Funktionsparameter anstatt in den Kontext des splice()Aufrufs kopiert haben .

Gespeichert 3 Bytes dank @Neil ‚s Vorschlag zu konvertieren [...Array(10)]zu [...''+1e9].

Unbegrenzter Code

input => (
  [...input].map(
    (char, decimal, [...charArray]) =>
      [...'' + 1e9].map(
        (unused, digit) => sum +=
          digit + decimal && digit != char ?
            prime(
              (
                charArray.splice(decimal, 1, digit)
                , charArray.join``
              )
            ) :
            0
      )
    , sum = 0
    , prime = test => eval('for(factor = test; test % --factor;); factor == 1')
  )
  , sum
)

Erläuterung

Die Funktion verwendet eine zweistufige map()Summe der Permutationen, die den Primalitätstest bestehen, der aus dieser Antwort ausgeliehen und geändert wurde .

(Originalantwort)

reduce((accumulator, currentValue, currentIndex, array) => aggregate, initialValue)

Um zum Beispiel die Summe eines Arrays zu berechnen, übergeben Sie ein initialValuevon 0und geben ein aggregateGleich zurück accumulator + currentValue. Wenn Sie diesen Ansatz leicht modifizieren, berechnen wir stattdessen die Anzahl der Permutationen, die den Primalitätstest bestehen:

reduce(
  (passedSoFar, currentDecimal, currentIndex, digitArray) =>
    isValidPermutation() ?
      passedSoFar + prime(getPermutation()) :
      passedSoFar
  , 0
)

Das ist im Wesentlichen das Innere reduce(), das alle Permutationen des durchläuft, digitArrayindem jedes decimalauf ein bestimmtes geändert wird permutatedDigit. Wir brauchen dann ein Äußeres reduce(), um alle möglichen zu iterieren permutatedDigit, um jedes zu ersetzen decimal, was gerecht ist 0-9.

Unregelmäßigkeiten bei der Durchführung

[...''+1e9].map((u,j)=>...war der kürzeste Weg @Neil von iterieren ein Argument denken konnte 0durch 9. In diesem Fall ist dies vorzuziehen u, jedoch unicht für jedes Element im Array sinnvoll.

i+jIn der ternären Bedingung wird überprüft, ob 0es sich um eine mögliche Permutation der führenden Ziffer gemäß der Challenge-Spezifikation handelt. j!=cstellt sicher, dass das Original nkein Kandidat für den Primalitätstest ist.

(a.splice(i,1,j),a.join``)ist eine Art Durcheinander. splice()Ersetzt die Ziffer decimal == imit dem permutatedDigit == j, aber da splice()die entfernten Elemente (in diesem Fall wäre das gleich [a[i]]) anstelle des geänderten Arrays zurückgegeben werden, müssen wir den Kommaoperator verwenden, um das geänderte Array aan den Primitätstest zu übergeben, jedoch nicht bevor wir join()es übergeben in eine Zahlenfolge.

Schließlich soll eval()ein Byte gespeichert werden, da es im Vergleich zum kanonischeren Ansatz kürzer ist:

q=>eval('for(k=q;q%--k;);k==1')

q=>{for(k=q;q%--k;);return k==1}

Der Verweis auf den Primetest pwird in einem nicht verwendeten Argument zum map()Aufruf initialisiert .

Patrick Roberts
quelle
Ich denke, die Tipps-Seite sagt, [...''+1e9]ist kürzer.
Neil
2

Python 2 , 134 Bytes

lambda x,r=range,l=len:sum(~-f*(~-l(x)==sum(`f`[t]==x[t]for t in r(l(x))))and all(f%v for v in r(2,f))for f in r(10**~-l(x),10**l(x)))

Probieren Sie es online!

Elegantere, längere Version:

lambda x,r=range,l=len:l(filter(lambda f:(~-f*(~-l(x)==sum(`f`[t]==x[t]for t in r(l(x)))))*all(f%v for v in r(2,f)),r(10**~-l(x),10**l(x))))

Die Eingabe wird als Zeichenfolge verwendet.


Erklärung (ältere Version)

  • lambda x,r=range,l=len:- Definiert ein Lambda mit einem String-Parameter xund zwei konstanten Parametern r=rangeundl=len .

  • sum(1...) - Holen Sie sich die Länge, die 1 Byte über spart len([...]) .

  • for f in r(10**~-l(x),10**l(x))- Erzeugt absolut alle Zahlen mit der gleichen Größenordnung wie die Eingabe (erwartet für 0). Zum Beispiel würde eine Eingabe von 3, ergeben[1, 2, 3, 4, 5, 6, 7, 8, 9] .

  • sum(1for t in r(l(x))if`f`[t]==x[t])==~-l(x)and f>1 - Überprüft, ob die aktuelle Nummer genau 1 Stelle von der Eingabe entfernt ist und ob sie höher als 1 ist.

  • all(f%v for v in r(2,f)) - Überprüft, ob die aktuelle Nummer eine Primzahl ist.

Mr. Xcoder
quelle
1
Sie cound ändern sum(1for..ifBOOL), sum(BOOLfor)um einige Bytes zu speichern
Dead Possum
Dürfen wir Eingaben als String annehmen? Ich bin mir nicht sicher
Dead Possum
@DeadPossum Einige der Antworten sind zutreffend. Warum sollte das nicht erlaubt sein ?!
Mr. Xcoder
Ich habe für heute keine Stimmen mehr, werde aber umgehend +1 geben: D
Dead Possum
@DeadPossum Sicher. Vergiss nicht oder ich werde dich anpingen! ( </joke>)
Mr. Xcoder
1

JavaScript (ES6), 137 Byte

i=(a=prompt()).length;s=0;while(i--)for(j=0;j<=9;j++){(b=[...a]).splice(i,1,j);k=b=b.join('');while(b%--k);s+=i+j&&a[i]!=j&&k==1}alert(s)

Passt meine andere Antwort mithilfe der Web-API-Methoden prompt()und in eine vollständige Programmübermittlung an alert().

Patrick Roberts
quelle
1

Bean , 126 Bytes

00000000: a64d a065 8050 80a0 5d20 8001 a64d a06f  ¦M e.P. ] ..¦M o
00000010: 8025 39b5 cb81 2065 27a6 4da0 6680 2581  .%9µË. e'¦M f.%.
00000020: 0035 cb81 2066 27a6 53d0 80cd a05e 8043  .5Ë. f'¦SÐ.Í ^.C
00000030: cf20 5d00 2080 82a0 65a5 3a20 66a6 4da0  Ï ]. .. e¥: f¦M 
00000040: 6780 4da0 5e80 53d0 80a0 5e20 807b 2300  g.M ^.SÐ. ^ .{#.
00000050: b5cc a05e 8f4b c120 6728 264d a06f 814e  µÌ ^.KÁ g(&M o.N
00000060: cecc a065 8b20 6681 4cd0 84a0 5d20 6581  ÎÌ e. f.LÐ. ] e.
00000070: 2066 814c a067 8025 3a26 206f b130        f.L g.%:& o±0

Probieren Sie es online!

Eine Anpassung meines JavaScript-Vollprogramms .

JavaScript-Äquivalent

i=a.length
s=0
while(i--){
  j=10
  while(j--){
    (b=[...a]).splice(i,1,j)
    k=b=b.join('')
    while(b%--k);
    s+=i+j&&a[i]!=j&&k==1
  }
}
s

Erläuterung

awird implizit als erste Eingabezeile als Zeichenfolge initialisiert und die letzte Anweisung swird implizit ausgegeben, die die Summe der Primzahlpermutationen enthält.

Patrick Roberts
quelle
1

Schale , 32 Bytes

Lof§&ȯ=1Σzo±≠d⁰o=Ld⁰L↑o≤Ld⁰Lmdİp

Probieren Sie es online!

Ungolfed / Erklärung

                              İp  -- get all primes
                            md    -- and convert them to list of digits
                     ↑o≤   L      -- take as long as the lenghth of these digit lists are ≤ ..
                        Ld⁰       -- .. the number of digits of input 
 of                               -- from those primes filter:
               o=Ld⁰L             --   same number of digits as input
   §&                             --   and
        Σz                        --   the number of..
          o±≠d⁰                   --   .. digits that differ from input digits ..
     ȯ=1                          --   .. must be one
L                                 -- finally count them
ბიმო
quelle
1

Japt , 28 23 Bytes

-5 Bytes dank @ETHproductions.

¬x@AÇ|Y©+UhYZsÃâ kUn)èj

Nimmt einen String als Eingabe.

Probieren Sie es online!

Justin Mariner
quelle
Vielleicht noch ein Paar mit ¬x@AÇ|Y©+UhYZsÃâ kUn)èj?
ETHproductions
1

PHP , 151 147 141 140 136 134 129 128 Bytes

-6 Bytes dank @Einacio; -1 Byte dank @Titus

<?php for($i=$m=10**strlen($n=$argv[1]);$i-->$m/10;)if(levenshtein($n,$i)==$f=$t=1){while($t<$i)$f+=$i%$t++<1;$c+=$f==2;}echo$c;

Probieren Sie es online!

Formatiert mit Kommentaren:

<?php
// Work through each integer with the same number of digits as the input $argv[1].
for ($i = $m = 10 ** strlen($n = $argv[1]); $i-- > $m / 10;)
    // Is it exactly one digit different from the input?
    if (levenshtein($n, $i) == $f = $t = 1) {
        // Count its factors.
        while ($t < $i) $f += $i % $t++ < 1;
        // If there are exactly 2 factors then it's a prime, so increment the counter.
        $c += $f == 2;
    }
// Print the final count.
echo $c;

Um es so kurz wie möglich zu halten, habe ich:

  • kombinierte Aufgaben $f = $t = 1 ;
  • ein ++Inkrement als Teil eines anderen Ausdrucks einbinden $f += $i % $t++ == 0(das Inkrement wird nach der Modul-Operation ausgeführt und hat somit keinen Einfluss auf das Ergebnis);
  • und anstatt eine ifAnweisung für ein bedingtes Inkrement zu verwenden, haben wir die Tatsache ausgenutzt, dass der boolesche Wert true, wenn er als Ganzzahl umgewandelt wird, zu 1 wird, $c += $f == 2;anstatt if ($f == 2) $c++;.
WebSmithery
quelle
1
du brauchst $ c nicht zu definieren, es zählt als 0 auf dem ersten + =
Einacio
@Einacio Wie lauten die Golfregeln? Ist das erlaubt, da es einen undefinierten variablen Warnhinweis gibt?
WebSmithery
@Einacio Anscheinend kann jede Ausgabe an STDERR ignoriert werden, also danke für den Vorschlag.
WebSmithery
1
+1 für die Verwendung von levenshtein. Gute Idee! $i%$t++<1ist kürzer als $i%$t++==0.
Titus
0

PHP, 100 + 1 Bytes

for(;~($a=$argn)[$i];$i++)for($d=-!!$i;$d++<9;$c+=$k==1)for($a[$i]=$d,$k=$a;--$k&&$a%$k;);echo$c-$i;

Laufen Sie als Pipe mit -nRoder probieren Sie es online aus .

Nervenzusammenbruch

for(;~($n=$argn)[$i];$i++)  # loop through argument digits, restore $n in every iteration
    for($d=-!!$i;               # loop $d from 0 (1 for first digit)
        $d++<9;                 # ... to 9
        $c+=$k==1                   # 3. if divisor is 1, increment counter
    )
        for($n[$i]=$d,              # 1. replace digit
            $k=$n;--$k&&$n%$k;      # 2. find largest divisor of $n smaller than $n
        );
echo$c-$i;                  # print counter - length
Titus
quelle
0

Java 8, 201 194 Bytes

n->{String s=n+"";int r=0,i=0,j,k,t,u,l=s.length();for(;i<l;i++)for(j=0;++j<10;r+=n==u|t<2?0:1)for(u=t=new Integer(s.substring(0,i)+j+(i<l?s.substring(i+1):"")),k=2;k<t;t=t%k++<1?0:t);return r;}

Erläuterung:

Probieren Sie es hier aus.

n->{                        // Method with integer as parameter and return-type
  String s=n+"";            //  String representation of the input-int
  int r=0,                  //  Result-integer
      i=0,j,k,              //  Index-integers
      t,u,                  //  Temp integers
      l=s.length();         //  Length of the String
  for(;i<l;i++)             //  Loop (1) from 0 to `l` (exclusive)
    for(j=0;++j<10;         //   Inner loop (2) from 1 to 10 (exclusive)
        r+=                 //     And after every iteration, raise the result by:
           n==u             //      If the current number equals the input
           |t<2?            //      or it is not a prime:
            0               //       Add nothing to the result-counter
           :                //      Else:
            1)              //       Raise the result-counter by one
      for(                  //    Inner loop (3)
          u=t=              //     First set both `u` and `t` to:
              new Integer(  //      Convert the following String to an integer: 
               s.substring(0,i)
                            //       Get the substring from 0 to `i` (exclusive)
               +j           //       + `j`
               +(i<l?       //       + If `i` is smaller than the String-length:
                  s.substring(i+1)
                            //          The substring from 0 to `i` (inclusive)
                 :          //         Else:
                  "")),     //          Nothing
          k=2;              //     And start `k` at 2
              k<t;          //     Continue looping as long as `k` is smaller than `t`
        t=t%k++<1?          //     If `t` is divisible by `k`:
           0                //      Change `t` to 0
          :                 //     Else:
           t                //      Leave `t` as is
      );                    //    End of inner loop (3)
                            //    (`t` remained the same after loop 3? -> It's a prime)
                            //   End of inner loop (2) (implicit / single-line body)
                            //  And of loop (1) (implicit / single-line body)
  return r;                 //  Return the result-counter
}                           // End of method

new Integer(s.substring(0,i)+j+(i<l?s.substring(i+1):"") ergibt diese ganzen Zahlen:

Für 0-9: 1, 2, 3, 4, 5, 6, 7, 8, 9.
Für 10: 10, 20, 30, 40, 50, 60, 70, 80, 90, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
Für 11: 11, 21, 31, 41, 51, 61, 71, 81, 91, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
etc.

Kevin Cruijssen
quelle
0

JavaScript (ES7), 118 Byte

Übernimmt die Eingabe als Zeichenfolge.

n=>[...2**29+'4'].map(d=>n.replace(/./g,c=>s+=d+i>0&(P=k=>N%--k?P(k):N-n&&k==1)(N=p+d+n.slice(++i),p+=c),i=p=0),s=0)|s

Probieren Sie es online!

Kommentiert

n =>                        // n = input number (as a string)
  [...2**29 + '4']          // generate "5368709124" (all decimal digits)
  .map(d =>                 // for each digit d in the above string:
    n.replace(/./g, c =>    //   for each digit c in n:
      s +=                  //     increment s if the following code yields 1:
        d + i > 0 & (       //       if this is not the first digit of n or d is not "0":
          P = k =>          //         P = recursive function taking k and using N:
            N % --k ?       //           decrement k; if k is not a divisor of N:
              P(k)          //             do recursive calls until it is
            :               //           else:
              N - n &&      //             return true if N is not equal to n
              k == 1        //             and k is equal to 1 (i.e. N is prime)
          )(                //         initial call to P ...
            N =             //           ... with N defined as:
              p +           //             the current prefix p
              d +           //             followed by d
              n.slice(++i), //             followed by the trailing digits
                            //             (and increment the pointer i)
            p += c          //           append c to p
          ),                //         end of initial call
          i = p = 0         //         start with i = p = 0
    ),                      //   end of replace()
    s = 0                   //   start with s = 0
  ) | s                     // end of map(); return s
Arnauld
quelle
0

Ruby mit -rprime101 Bytes

-rprime10flOOr(lOG10n)+1n

->n{d=n.digits;Prime.each(10**l=d.size).count{|x|d.zip(e=x.digits).count{|a,b|a==b}==l-1&&e.size==l}}

Probieren Sie es online!

Wert Tinte
quelle