Primes diferentes da Optimus

36

Desafio

Dado um número inteiro de entrada n > 0, imprima o número de números primos ( outros que n, sen em si é primo), que pode ser produzido por alterao de um dígito na expansão decimal de n (sem alteração do número de dígitos).

Exemplos

Por exemplo n = 2,. Ao alterar um dígito na expansão decimal de 2, podemos criar três números primos adicionais,3, 5, 7 , para quea(n) = 3 .

Para outro exemplo n = 13,. Ao alterar um dígito, você pode obter números primos 11, 17, 19, 23, 43, 53, 73, 83, paraa(13) = 8 .

Para um exemplo final n = 20,. Ao alterar um dígito, você pode obter números primos 23, 29, paraa(20) = 2 .

Seqüência

Aqui estão os 20 primeiros termos para você começar. Este é o OEIS A048853 .

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

Regras

  • Pode-se presumir que a entrada e a saída se encaixam no tipo inteiro nativo do seu idioma.
  • A entrada e saída podem ser fornecidas em qualquer formato conveniente .
  • Ignore zeros à esquerda (por exemplo, 03 não é um número primo nesta formulação).
  • Um programa completo ou uma função são aceitáveis. Se uma função, você pode retornar a saída em vez de imprimi-la.
  • Se possível, inclua um link para um ambiente de teste on-line para que outras pessoas possam experimentar seu código!
  • As brechas padrão são proibidas.
  • Isso é portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.
AdmBorkBork
fonte
4
Estou tentando pensar no menor npara o qual a saída é 0. Eu acho que é n = 200. Eu também acho que eles vêm em cachos: 200,202,204,206,208, 320,322,...,328, 510,...,518, 620,...628, 840,...,848, etc.
Engenheiro Toast
"Pode-se presumir que" a entrada e a saída se encaixam no tipo inteiro nativo do seu idioma "afirma que não temos permissão para receber a entrada como string?
Morto Possum
1
@DeadPossum Não, isso é permitido. Só que você não precisa se preocupar com 2 ^ 100 como entrada se estiver usando apenas números inteiros de 32 bits, por exemplo.
AdmBorkBork 2/17/17
Do deixe-me saber se eu vou ao mar ... Eu tenho 3 diferentes apresentações agora
Patrick Roberts
2
@EngineerToast Depois de encontrar o primeiro exemplo de prime (294001), finalmente pensei em procurá-lo no OEIS: A192545 e A158124 . Também relevante: A143641 .
Ørjan Johansen

Respostas:

10

05AB1E , 17 16 14 11 bytes

ā°`<Ÿʒ.L}pO

Explicação:

ā             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

Experimente online! ou até 100 .

Okx
fonte
1
.L? A sério? .L?!?!
Erik the Outgolfer
@EriktheOutgolfer L.
Okx 03/08/19
Quero dizer, há uma distância embutida para levenshtein!
Erik the Outgolfer
@EriktheOutgolfer ¯ \ _ (ツ) _ / ¯
Okx
Eu sei que já faz um tempo, mas você pode remover o <para salvar um byte. Mesmo que o filtro não remova o 100/ 1000/ 10000/ etc., Ele nunca é primo, portanto não afetará a saída.
Kevin Cruijssen
5

Python 2 , 146 136 127 121 118 bytes

Obrigado a @ Mr.Xcoder por sugestões

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

Explicação:

Gere números com comprimento igual ao comprimento de entrada, pulando primeiro (1,10,100,1000, ...)

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

Verifique se o número gerado difere da entrada por apenas um dígito

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

Verifique se há prime

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

Contagem

sum(...)    

Experimente online!

Gambá morto
fonte
Pode ser mais curto para não tornar isso um lambda, e faz r=range, já que você o usa muitas vezes ...?
Stewie Griffin
1
Isso funciona para coisas como 143? Porque eu vejo range(1,10), isso exclui 0e 103é primordial
Sr. Xcoder 02/08/19
@ Mr.Xcoder corrigido
Dead Possum
1
Você não precisa 0entrar r(0,10). r(10)é suficiente.
Mr. Xcoder
1
Além disso, sugiro colocá-lo da seguinte forma:lambda I,r=range:
Sr. Xcoder
4

Javascript (ES6) 148 bytes

Pega a entrada como uma string e retorna como um número

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)

Exemplo de trecho de código:

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
fonte
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!=#]&;

Experimente online!

Functionque espera um número inteiro positivo #. Define figual à função IntegerDigitsque retorna a lista de dígitos de sua entrada. Tomamos o Rangede gpara 10g(inclusive), onde g=10^Length@f@#/10é a maior potência 10menor ou igual à entrada #, e depois Counta nque PrimeQ@n&&MatchQ[f@n-f@#,{x=0...,_,x}]&&n!=#. PrimeQ@nverifica se né primo, MatchQ[f@n-f@#,{x=0...,_,x}]verifica se a diferença entre a lista de dígitos de ne #é da forma {0..., _, 0...}e n!=#garante que ne #é Unequal.

ngenisis
fonte
3

JavaScript (ES6), 153 142 139 bytes

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)

Aceita entrada como uma sequência. Comportamento indefinido para entrada inválida, embora deva terminar sem erro em qualquer string que eu possa pensar. Não necessariamente antes da morte por calor do universo, principalmente para cordas longas.

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>

Melhorias

Salva 11 bytes refatorando as reduce()chamadas em map()chamadas e copiando implicitamente a matriz ano parâmetro function, em vez de dentro do contexto dosplice() chamada.

Economizou 3 bytes graças à sugestão de @Neil de converter [...Array(10)]para[...''+1e9] .

Código não minificado

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
)

Explicação

A função usa um nível de dois níveis map()para somar a quantidade de permutações que passam no teste de primalidade, que foi emprestado e modificado a partir desta resposta .

(Resposta original)

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

Por exemplo, para calcular a soma de uma matriz, você passaria um initialValuede 0e retornaria um aggregateigual a accumulator + currentValue. Modificando essa abordagem levemente, calculamos o número de permutações que passam no teste de primalidade:

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

Isso é essencialmente o interior reduce(), que itera todas as permutações do digitArrayalterando cada decimalum para um específico permutatedDigit. Precisamos, então, de um externo reduce()para iterar todos os possíveis permutatedDigitcom os quais substituir cada um decimal, o que é justo 0-9.

Anormalidades na implementação

[...''+1e9].map((u,j)=>...era o caminho mais curto @Neil poderia pensar para iterate um argumento 0através 9. Seria preferível fazê-lo com u, mas unão é útil para cada elemento da matriz, neste caso.

i+jna condição ternária, verifica 0se não é uma permutação possível do dígito inicial, conforme a especificação do desafio. j!=cgarante que o original nnão seja um candidato para passar no teste de primalidade.

(a.splice(i,1,j),a.join``)é uma bagunça. splice()substitui o dígito por decimal == icom permutatedDigit == j, mas como splice()retorna os elementos removidos (nesse caso, seria igual a [a[i]]) em vez da matriz modificada, devemos usar o operador vírgula para passar a matriz modificada apara o teste de primalidade, mas não antes de join()inseri-la em uma sequência numérica.

Por fim, o eval()é salvar um byte, pois, comparado à abordagem mais canônica, é mais curto:

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

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

A referência ao teste principal pé inicializada em um argumento não utilizado para a map()chamada.

Patrick Roberts
fonte
Eu acho que a página de dicas diz que [...''+1e9]é mais curta.
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)))

Experimente online!

Versão mais elegante e mais longa:

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

A entrada é tomada como uma String.


Explicação (versão mais antiga)

  • lambda x,r=range,l=len:- Define um lambda com um parâmetro String xe dois parâmetros constantes r=rangee l=len.

  • sum(1...)- Obtenha o comprimento, que economiza 1 byte len([...]).

  • for f in r(10**~-l(x),10**l(x))- Gera absolutamente todos os números com a mesma ordem de magnitude que a entrada (esperada 0). Por exemplo, uma entrada de 3, resultaria em [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 - Verifica se o número atual está exatamente a 1 dígito da entrada e se é maior que 1.

  • all(f%v for v in r(2,f)) - Verifica se o número atual é primo.

Mr. Xcoder
fonte
1
Você Cound mudar sum(1for..ifBOOL)para sum(BOOLfor)salvar alguns bytes
Morto Possum
É permitido receber entrada como string? Olhando para "A entrada e saída pode ser assumida para caber no tipo inteiro nativo do seu idioma" Eu não tenho certeza
Morto Possum
@DeadPossum Algumas das respostas fazem. Por que não seria permitido ?!
Mr. Xcoder
Estou sem votos para hoje, mas vou marcar com +1 o mais cedo possível: D
Dead Possum
@DeadPossum Sure. Não se esqueça ou eu vou pingar você! ( </joke>)
Sr. Xcoder
1

JavaScript (ES6), 137 bytes

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)

Adapta minha outra resposta a um envio de programa completo usando os métodos prompt()e API da Web alert().

Patrick Roberts
fonte
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

Experimente online!

Uma adaptação do meu envio de JavaScript para o programa completo .

Equivalente a 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

Explicação

aé inicializado implicitamente como a primeira linha de entrada como uma string e a última instrução sé emitida implicitamente, que contém a soma das permutações principais.

Patrick Roberts
fonte
1

Casca , 32 bytes

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

Experimente online!

Ungolfed / Explicação

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

Japonês , 28 23 bytes

-5 bytes graças a @ETHproductions.

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

Toma uma string como entrada.

Experimente online!

Justin Mariner
fonte
Talvez outro casal com ¬x@AÇ|Y©+UhYZsÃâ kUn)èj?
ETHproductions
1

PHP , 151 147 141 140 136 134 129 128 bytes

-6 bytes graças a @Einacio; -1 byte graças a @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;

Experimente online!

Formatado, com comentários:

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

Para mantê-lo o mais curto possível, eu:

  • tarefas combinadas $f = $t = 1;
  • snook em um ++incremento como parte de outra expressão $f += $i % $t++ == 0(o incremento é executado após a operação do módulo e, portanto, não afeta o resultado);
  • e, em vez de usar uma ifinstrução para um incremento condicional, utilizou o fato de que boolean true quando convertido como um número inteiro se torna 1, usando em $c += $f == 2;vez de if ($f == 2) $c++;.
WebSmithery
fonte
1
você não precisa definir $ c, ele conta como 0 no primeiro + =
Einacio
@Einacio Quais são as regras de golfe? Isso é permitido, pois fornece um aviso de aviso de variável indefinido?
WebSmithery 03/08/19
@Einacio Aparentemente, qualquer saída para STDERR pode ser ignorada, então obrigado pela sugestão.
WebSmithery 03/08/19
1
+1 para uso de levenshtein . Boa ideia! $i%$t++<1é mais curto que $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;

Execute como pipe -nRou experimente on-line .

demolir

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

Explicação:

Experimente aqui.

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):"") resultará nos números inteiros:

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

Kevin Cruijssen
fonte
0

JavaScript (ES7), 118 bytes

Recebe a entrada como uma sequência.

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

Experimente online!

Comentado

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
fonte
0

Ruby com -rprime, 101 bytes

-rprimeimporta o módulo Prime para o Ruby. Obtenha todos os números primos até10feuoor(euog10n)+1 e conte quantos têm o mesmo número de dígitos de n e também estão com 1 dígito.

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

Experimente online!

Value Ink
fonte