Primes autres qu'Optimus

36

Défi

Pour un nombre entier en entrée n > 0, indiquez le nombre de nombres premiers ( autres que n, si nlui-même est premier) pouvant être générés en modifiant un chiffre dans le développement décimal de n (sans modifier le nombre de chiffres).

Exemples

Par exemple, n = 2. En modifiant un chiffre dans le développement décimal de 2, nous pouvons obtenir trois nombres premiers supplémentaires 3, 5, 7, donc a(n) = 3.

Pour un autre exemple, n = 13. En modifiant un chiffre, vous pouvez obtenir des nombres premiers 11, 17, 19, 23, 43, 53, 73, 83, donc a(13) = 8.

Pour un dernier exemple, n = 20. En modifiant un chiffre, vous pouvez obtenir des nombres premiers 23, 29, donc a(20) = 2.

Séquence

Voici les 20 premiers termes pour vous aider à démarrer. C'est OEIS A048853 .

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

Règles

  • On peut supposer que l’entrée et la sortie s’intègrent dans le type entier natif de votre langue.
  • L'entrée et la sortie peuvent être données dans n'importe quel format pratique .
  • Ignorer les zéros non significatifs (par exemple, ce 03n'est pas un nombre premier dans cette formulation).
  • Un programme complet ou une fonction sont acceptables. Si une fonction est utilisée, vous pouvez renvoyer la sortie plutôt que de l’imprimer.
  • Si possible, veuillez inclure un lien vers un environnement de test en ligne afin que d'autres personnes puissent tester votre code!
  • Les échappatoires standard sont interdites.
  • Il s’agit du donc toutes les règles de golf habituelles s’appliquent et le code le plus court (en octets) gagne.
AdmBorkBork
la source
4
J'essaie de penser au plus petit npour lequel la sortie est 0. Je pense que c'est n = 200. Je pense aussi qu'ils viennent en grappes: 200,202,204,206,208, 320,322,...,328, 510,...,518, 620,...628, 840,...,848, etc.
Ingénieur Toast
"L'entrée et la sortie peuvent être supposées correspondre au type entier natif de votre langue" indique-t-il que nous ne sommes pas autorisés à prendre l'entrée sous forme de chaîne?
Dead Possum
1
@DeadPossum Non, c'est autorisé. Simplement, vous n'avez pas à vous soucier de l'entrée 2 ^ 100 si vous utilisez uniquement des entiers 32 bits, par exemple.
AdmBorkBork
Faites-moi savoir si je vais trop loin ... J'ai 3 soumissions différentes maintenant
Patrick Roberts
2
@EngineerToast Après avoir trouvé le premier exemple de prime (294001), j'ai finalement pensé à le rechercher sur OEIS: A192545 et A158124 . Également pertinent: A143641 .
Ørjan Johansen

Réponses:

10

05AB1E , 17 16 14 11 octets

ā°`<Ÿʒ.L}pO

Explication:

ā             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

Essayez-le en ligne! ou jusqu'à 100 .

Okx
la source
1
.L? Sérieusement? .L?!?!
Erik the Outgolfer
@EriktheOutgolfer L.
Okx
Je veux dire, il y a un construit pour la distance de levenshtein!
Erik l'Outgolfer
@EriktheOutgolfer ¯ \ _ (ツ) _ / ¯
Okx
Je sais que cela fait longtemps, mais vous pouvez supprimer le <pour sauvegarder un octet. Même si le filtre ne supprime pas le fichier 100/ 1000/ 10000/ etc.
Kevin Cruijssen
5

Python 2 , 146, 136, 127, 121, 121, 118, octets

Merci à @ Mr.Xcoder pour ses suggestions

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)))

Explication:

Générer des nombres de longueur égale à la longueur de saisie, en sautant d’abord (1,10,100,1000, ...)

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

Vérifiez que le nombre généré diffère de l'entrée par un seul chiffre

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

Vérifier pour prime

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

Compter

sum(...)    

Essayez-le en ligne!

Mort possum
la source
Peut-être serait-il plus court de ne pas en faire un lambda, et faites r=range-le puisque vous l'utilisez plusieurs fois ...?
Stewie Griffin
1
Est-ce que cela fonctionne pour des choses comme 143? Parce que je vois range(1,10), cela exclut 0et 103est primordial
M. Xcoder
@ Mr.Xcoder fixe
Dead Possum
1
Vous n'avez pas besoin 0de r(0,10)po r(10)suffit.
M. Xcoder
1
Aussi, je suggère de le mettre comme tel:lambda I,r=range:
M. Xcoder
4

Javascript (ES6) 148 octets

Prend l'entrée sous forme de chaîne et retourne sous forme de nombre

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)

Exemple d'extrait de code:

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
la source
4

Jelly , 21 18 15 octets

3 octets grâce à Dennis.

æḟ⁵æR×⁵$DnDS€ċ1

Essayez-le en ligne! ou Vérifiez tous les cas de test .

Fuite Nun
la source
æḟ⁵æR×⁵$DnDS€ċ1enregistre quelques octets.
Dennis
La gamme alternative est assez intelligente.
Leaky Nun
3

Mathematica, 105 octets

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

Essayez-le en ligne!

Functionqui attend un entier positif #. Définit fégal à la fonction IntegerDigitsqui renvoie la liste des chiffres de son entrée. Nous prenons le Rangede gà 10g(inclus), où g=10^Length@f@#/10est la plus grande puissance 10inférieure ou égale à l'entrée #, puis Countle ntel que PrimeQ@n&&MatchQ[f@n-f@#,{x=0...,_,x}]&&n!=#. PrimeQ@nvérifie si nest premier, MatchQ[f@n-f@#,{x=0...,_,x}]vérifie si la différence entre la liste des chiffres de net #est du formulaire {0..., _, 0...}et n!=#s'assure que net #sont Unequal.

ngenisis
la source
3

JavaScript (ES6), 153 142 139 octets

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)

Accepte les entrées en tant que chaîne. Comportement non défini pour une entrée non valide, même s'il doit se terminer sans erreur sur toutes les chaînes auxquelles je peux penser. Pas nécessairement avant la chaleur-mort de l'univers, surtout pour les longues ficelles.

Démo

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>

Améliorations

Vous avez enregistré 11 octets en reformulant les reduce()appels en map()appels et en copiant implicitement le tableau adans le paramètre de fonction, au lieu de dans le contexte de l' splice()appel.

Sauvegardé de 3 octets grâce à la suggestion de @Neil de convertir [...Array(10)]en [...''+1e9].

Code non miné

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
)

Explication

La fonction utilise un niveau map()à deux niveaux pour additionner le nombre de permutations satisfaisant au test de primalité, emprunté et modifié à partir de cette réponse .

(Réponse originale)

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

Ainsi, par exemple, pour calculer la somme d'un tableau, vous devez passer un initialValueof 0et renvoyer un aggregateégal à accumulator + currentValue. En modifiant légèrement cette approche, nous calculons plutôt le nombre de permutations satisfaisant le test de primalité:

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

C’est essentiellement l’intérieur reduce(), qui répète toutes les permutations du digitArrayen changeant chacune decimalen un spécifique permutatedDigit. Nous avons ensuite besoin d’un extérieur reduce()pour itérer tous les possibles permutatedDigitavec lesquels remplacer chacun decimal, ce qui est juste 0-9.

Anomalies dans la mise en œuvre

[...''+1e9].map((u,j)=>...était le chemin le plus court @Neil pourrait penser à itérer un argument 0par 9. Dans ce cas, il serait préférable de le faire avec u, mais cela un’est pas utile pour chaque élément du tableau.

i+jdans la condition ternaire vérifie qu'il 0n'y a pas de permutation possible du premier chiffre, conformément à la spécification de défi. j!=cgarantit que l'original nn'est pas candidat pour passer le test de primalité.

(a.splice(i,1,j),a.join``) C'est un peu le bordel. splice()remplace le chiffre at decimal == ipar le permutatedDigit == j, mais puisque splice()renvoie les éléments supprimés (dans ce cas, serait égal à [a[i]]) au lieu du tableau modifié, nous devons utiliser l'opérateur virgule pour transmettre le tableau modifié aau test de primalité, mais pas avant join(). dans une chaîne numérique.

Enfin, le eval() s'agit de sauvegarder un octet puisque, comparé à l'approche plus canonique, il est plus court:

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

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

La référence au premier test p est initialisée dans un argument inutilisé de l' map()appel.

Patrick Roberts
la source
Je pense que la page de conseils dit [...''+1e9]est plus courte.
Neil
2

Python 2 , 134 octets

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)))

Essayez-le en ligne!

Plus élégante, version plus longue:

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))))

L'entrée est prise comme une chaîne.


Explication (ancienne version)

  • lambda x,r=range,l=len:- Définit un lambda avec un paramètre String xet deux paramètres constants r=rangeet l=len.

  • sum(1...)- Obtenez la longueur, ce qui économise 1 octet len([...]).

  • for f in r(10**~-l(x),10**l(x))- Génère absolument tous les nombres avec le même ordre de grandeur que l'entrée (attendre pour 0). Par exemple, une entrée de 3, aboutirait à [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 - Vérifie si le nombre actuel est exactement à 1 chiffre de l'entrée et s'il est supérieur à 1.

  • all(f%v for v in r(2,f)) - Vérifie si le nombre actuel est premier.

M. Xcoder
la source
1
Vous devez changer sum(1for..ifBOOL)pour sum(BOOLfor)économiser quelques octets
Dead Possum
Sommes-nous autorisés à prendre l'entrée sous forme de chaîne? En regardant "On peut supposer que l'entrée et la sortie correspondent au type entier natif de votre langue" Je ne suis pas sûr
Dead Possum
@DeadPossum Certaines des réponses le font. Pourquoi ne serait-il pas permis?!
M. Xcoder
Je suis à court de votes pour aujourd'hui, mais je vais +1 dès que possible: D
Dead Possum
@DeadPossum Bien sûr. N'oubliez pas ou je vous cinglerai! ( </joke>)
M. Xcoder
1

JavaScript (ES6), 137 octets

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)

Adapte mon autre réponse à une soumission de programme complet à l'aide des méthodes de l'API Web prompt()et alert().

Patrick Roberts
la source
1

Bean , 126 octets

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

Essayez-le en ligne!

Une adaptation de ma soumission JavaScript du programme complet .

Équivalent JavaScript

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

Explication

aest implicitement initialisé en tant que première ligne d'entrée sous forme de chaîne et la dernière instruction sest implicitement générée, ce qui contient la somme des permutations principales.

Patrick Roberts
la source
1

Husk , 32 octets

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

Essayez-le en ligne!

Ungolfed / Explication

                              İ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
ბიმო
la source
1

Japt , 28 23 octets

-5 octets grâce à @ETHproductions.

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

Prend une chaîne en entrée.

Essayez-le en ligne!

Justin Mariner
la source
Peut-être un autre couple avec ¬x@AÇ|Y©+UhYZsÃâ kUn)èj?
ETHproductions
1

PHP , 151 147 141 140 136 134 129 128 128 octets

-6 octets grâce à @Einacio; -1 octet grâce à @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;

Essayez-le en ligne!

Formaté, avec commentaires:

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

Pour être aussi bref que possible, j'ai:

  • missions combinées $f = $t = 1 ;
  • snook dans un ++incrément dans le cadre d'une autre expression $f += $i % $t++ == 0(l'incrément est exécuté après l'opération de module et n'affecte donc pas le résultat);
  • et plutôt que d'utiliser une ifinstruction pour un incrément conditionnel, ils ont utilisé le fait que boolean true lorsqu'il est converti en entier devient 1, en utilisant $c += $f == 2;plutôt que if ($f == 2) $c++;.
WebSmithery
la source
1
vous n'avez pas besoin de définir $ c, cela vaut 0 sur le premier + =
Einacio
@Einacio Quelles sont les règles du golf? Est-ce autorisé, car cela donne un avertissement de variable non défini?
WebSmithery
@Einacio Apparemment, tout résultat sur STDERR peut être ignoré, alors merci pour la suggestion.
WebSmithery
1
+1 pour l'utilisation de levenshtein. Bonne idée! $i%$t++<1est plus court que $i%$t++==0.
Titus
0

PHP, 100 + 1 octets

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;

Exécuter en pipe -nRou essayer en ligne .

panne

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
la source
0

Java 8, 201 194 octets

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

Explication:

Essayez ici.

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):"") aboutira à ces entiers:

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

Kevin Cruijssen
la source
0

JavaScript (ES7), 118 octets

Prend l'entrée sous forme de chaîne.

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

Essayez-le en ligne!

Commenté

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
la source
0

Ruby avec -rprime, 101 octets

-rprimeimporte le module Prime dans Ruby. Obtenez tous les nombres premiers jusqu'àdixFloor(logdixn)+1 et compter combien ont le même nombre de chiffres de n et sont également à 1 chiffre.

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

Essayez-le en ligne!

Valeur d'encre
la source