Primes selain Optimus

36

Tantangan

Mengingat integer masukan n > 0, keluaran jumlah bilangan prima ( lainnya selain n, jika nitu sendiri adalah perdana) yang dapat diproduksi dengan mengubah satu digit dalam ekspansi desimal n (tanpa mengubah jumlah digit).

Contohnya

Sebagai contoh n = 2,. Dengan mengubah satu digit dalam ekspansi desimal 2, kita dapat menghasilkan tiga bilangan prima tambahan 3, 5, 7,, jadi a(n) = 3.

Sebagai contoh lain n = 13,. Dengan mengubah satu digit, Anda bisa mendapatkan bilangan prima 11, 17, 19, 23, 43, 53, 73, 83, jadi a(13) = 8.

Sebagai contoh terakhir n = 20,. Dengan mengubah satu digit, Anda bisa mendapatkan bilangan prima 23, 29, jadi a(20) = 2.

Urutan

Berikut adalah 20 istilah pertama untuk membantu Anda memulai. Ini adalah OEIS A048853 .

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

Aturan

  • Input dan output dapat dianggap sesuai dengan tipe integer asli bahasa Anda.
  • Input dan output dapat diberikan dalam format apa pun yang nyaman .
  • Abaikan angka nol di depan (misalnya, 03bukan bilangan prima dalam formulasi ini).
  • Program lengkap atau fungsi dapat diterima. Jika suatu fungsi, Anda dapat mengembalikan output daripada mencetaknya.
  • Jika memungkinkan, harap sertakan tautan ke lingkungan pengujian online sehingga orang lain dapat mencoba kode Anda!
  • Celah standar dilarang.
  • Ini adalah sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.
AdmBorkBork
sumber
4
Saya mencoba memikirkan yang terkecil nuntuk outputnya 0. Saya pikir itu n = 200. Saya juga berpikir mereka datang dalam tandan: 200,202,204,206,208, 320,322,...,328, 510,...,518, 620,...628, 840,...,848, dll
Insinyur Toast
Apakah "Input dan output dapat dianggap sesuai dengan tipe integer asli bahasa Anda" menyatakan bahwa kami tidak diizinkan untuk mengambil input sebagai string?
Dead Possum
1
@DeadPossum Tidak, itu diizinkan. Hanya saja Anda tidak perlu khawatir tentang 2 ^ 100 sebagai input jika Anda hanya menggunakan bilangan bulat 32-bit, misalnya.
AdmBorkBork
Tolong beri tahu saya jika saya akan keluar dari kapal ... Saya memiliki 3 pengajuan berbeda sekarang
Patrick Roberts
2
@ EngineerToast Setelah menemukan contoh perdana pertama (294001), saya akhirnya berpikir untuk mencarinya di OEIS: A192545 dan A158124 . Juga relevan: A143641 .
Ørjan Johansen

Jawaban:

10

05AB1E , 17 16 14 11 byte

ā°`<Ÿʒ.L}pO

Penjelasan:

ā             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

Cobalah online! atau hingga 100 .

Okx
sumber
1
.L? Serius? .L?!?!
Erik the Outgolfer
@EriktheOutgolfer L.
Okx
Maksudku, ada builtin untuk jarak levenshtein!
Erik the Outgolfer
@EriktheOutgolfer ¯ \ _ (ツ) _ / ¯
Okx
Saya tahu ini sudah lama, tetapi Anda dapat menghapus <untuk menyimpan byte. Bahkan jika filter tidak menghapus 100/ 1000/ 10000/ etc., Itu tidak pernah jadi yang utama jadi tidak akan mempengaruhi output.
Kevin Cruijssen
5

Python 2 , 146 136 127 121 118 byte

Terima kasih kepada @ Mr.Xcoder untuk saran

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

Penjelasan:

Hasilkan angka dengan panjang sama dengan panjang input, lewati dulu (1,10,100,1000, ...)

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

Periksa bahwa angka yang dihasilkan berbeda dari input dengan hanya satu digit

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

Periksa prime

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

Menghitung

sum(...)    

Cobalah online!

Possum Mati
sumber
Mungkinkah lebih pendek untuk tidak membuat ini lambda, dan lakukan r=range, karena Anda menggunakannya berkali-kali ...?
Stewie Griffin
1
Apakah ini bekerja untuk hal-hal seperti 143? Karena saya melihat range(1,10), itu tidak termasuk 0, dan 103ini utama
Tn. Xcoder
@ Mr.Xcoder diperbaiki
Dead Possum
1
Anda tidak perlu 0di r(0,10). r(10)cukup.
Tn. Xcoder
1
Juga, saya sarankan meletakkannya seperti:lambda I,r=range:
Mr. Xcoder
4

Javascript (ES6) 148 byte

Mengambil input sebagai string dan kembali sebagai angka

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)

Cuplikan kode contoh:

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.
sumber
4

Jelly , 21 18 15 byte

3 byte berkat Dennis.

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

Cobalah online! atau Verifikasi semua testcases .

Biarawati Bocor
sumber
æḟ⁵æR×⁵$DnDS€ċ1menghemat beberapa byte.
Dennis
Kisaran alternatifnya cukup pintar.
Leaky Nun
3

Mathematica, 105 byte

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

Cobalah online!

Functionyang mengharapkan bilangan bulat positif #. Set fsama dengan fungsi IntegerDigitsyang mengembalikan daftar digit inputnya. Kami mengambil Rangedari gke 10g(inklusif), di mana g=10^Length@f@#/10adalah kekuatan terbesar 10kurang dari atau sama dengan input #, kemudian Countyang nseperti itu PrimeQ@n&&MatchQ[f@n-f@#,{x=0...,_,x}]&&n!=#. PrimeQ@nmemeriksa apakah nprime, MatchQ[f@n-f@#,{x=0...,_,x}]memeriksa apakah perbedaan antara daftar digit ndan #bentuk {0..., _, 0...}, dan n!=#memastikan itu ndan #sedang Unequal.

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

Menerima input sebagai string. Perilaku tidak terdefinisi untuk input tidak valid, meskipun harus diakhiri tanpa kesalahan pada string apa pun yang dapat saya pikirkan. Belum tentu sebelum kematian-panas alam semesta, terutama untuk string panjang.

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>

Perbaikan

Disimpan 11 byte dengan refactoring reduce()panggilan menjadi map()panggilan, dan dengan secara implisit menyalin array adalam parameter fungsi, bukan di dalam konteks splice()panggilan.

Disimpan 3 byte berkat saran @Neil untuk dikonversi [...Array(10)]ke [...''+1e9].

Kode tidak ditambang

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
)

Penjelasan

Fungsi ini menggunakan dua tingkat map()untuk menjumlahkan jumlah permutasi yang lulus tes primality, yang dipinjam dan dimodifikasi dari jawaban ini .

(Jawaban asli)

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

Jadi misalnya, untuk menghitung jumlah suatu array, Anda akan melewatkan initialValuedari 0, dan mengembalikan aggregatesama dengan accumulator + currentValue. Dengan sedikit memodifikasi pendekatan ini, kami menghitung jumlah permutasi yang lulus tes primality:

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

Itu pada dasarnya adalah bagian dalam reduce(), yang mengulangi semua permutasi dari digitArraydengan mengubah masing decimal- masing ke spesifik permutatedDigit. Kita kemudian membutuhkan bagian luar reduce()untuk mengulangi semua kemungkinan permutatedDigituntuk mengganti masing-masing decimal, yang adil 0-9.

Kelainan dalam implementasi

[...''+1e9].map((u,j)=>...adalah cara terpendek @Neil bisa memikirkan untuk mengulangi argumen 0melalui 9. Akan lebih baik untuk melakukannya dengan u, tetapi utidak berguna untuk setiap elemen dalam array, dalam hal ini.

i+jdalam kondisi terner memeriksa untuk memastikan bahwa 0tidak ada permutasi yang mungkin dari digit terdepan, sesuai spesifikasi tantangan. j!=cmemastikan bahwa dokumen asli nbukan kandidat untuk menjalani tes primality.

(a.splice(i,1,j),a.join``)agak berantakan. splice()mengganti digit pada decimal == idengan permutatedDigit == j, tetapi karena splice()mengembalikan elemen yang dihapus (dalam hal ini, akan sama dengan [a[i]]) alih-alih array yang dimodifikasi, kita harus menggunakan operator koma untuk meneruskan array yang dimodifikasi ake tes primality, tetapi tidak sebelum join()memasukkannya menjadi string angka.

Terakhir, eval()adalah untuk menyimpan byte karena, dibandingkan dengan pendekatan yang lebih kanonik, lebih pendek:

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

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

Referensi ke tes utama pdiinisialisasi dalam argumen yang tidak digunakan untuk map()panggilan.

Patrick Roberts
sumber
Saya pikir halaman tips mengatakan [...''+1e9]lebih pendek.
Neil
2

Python 2 , 134 byte

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

Cobalah online!

Lebih elegan, versi lebih panjang:

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

Input diambil sebagai String.


Penjelasan (versi lama)

  • lambda x,r=range,l=len:- Menentukan lambda dengan parameter String xdan dua parameter konstan r=rangedan l=len.

  • sum(1...)- Dapatkan panjangnya, yang menghemat 1 byte lebih len([...]).

  • for f in r(10**~-l(x),10**l(x))- Menghasilkan benar-benar semua angka dengan urutan magnitudo yang sama dengan input (yang diharapkan 0). Misalnya, input dari 3, akan menghasilkan [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 - Memeriksa apakah angka saat ini tepat 1 digit dari input, dan lebih tinggi dari 1.

  • all(f%v for v in r(2,f)) - Memeriksa apakah nomor saat ini prima.

Tuan Xcoder
sumber
1
Anda dapat mengubah sum(1for..ifBOOL)untuk sum(BOOLfor)menyimpan beberapa byte
Dead Possum
Apakah kami diizinkan mengambil input sebagai string? Melihat "Input dan output dapat dianggap sesuai dengan tipe bilangan bulat asli bahasa Anda" Saya tidak yakin
Dead Possum
@DeadPossum Beberapa jawaban lakukan. Kenapa itu tidak diizinkan ?!
Tn. Xcoder
Saya kehabisan suara untuk hari ini, tetapi akan +1 secepatnya: D
Dead Possum
@DeadPossum Sure. Jangan lupa atau aku akan ping kamu! ( </joke>)
Tn. 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)

Mengadaptasi jawaban saya yang lain ke dalam pengiriman program lengkap menggunakan metode prompt()dan API Web alert().

Patrick Roberts
sumber
1

Bean , 126 byte

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

Cobalah online!

Adaptasi pengajuan program JavaScript lengkap saya .

Setara 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

Penjelasan

asecara implisit diinisialisasi sebagai baris pertama input sebagai string dan pernyataan terakhir sadalah output secara implisit, yang berisi jumlah permutasi utama.

Patrick Roberts
sumber
1

Sekam , 32 byte

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

Cobalah online!

Tidak Terikat / Penjelasan

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

Japt , 28 23 byte

-5 byte terima kasih kepada @ETHproductions.

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

Mengambil string sebagai input.

Cobalah online!

Justin Mariner
sumber
Mungkin pasangan lain ¬x@AÇ|Y©+UhYZsÃâ kUn)èj?
ETHproduk
1

PHP , 151 147 141 140 136 134 129 128 byte

-6 byte terima kasih kepada @Einacio; -1 byte terima kasih kepada @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;

Cobalah online!

Diformat, dengan komentar:

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

Untuk membuatnya sesingkat mungkin, saya sudah:

  • tugas gabungan $f = $t = 1;
  • snook in ++increment sebagai bagian dari ekspresi lain $f += $i % $t++ == 0(increment dieksekusi setelah operasi modulus dan karenanya tidak mempengaruhi hasilnya);
  • dan bukannya menggunakan ifpernyataan untuk kenaikan bersyarat telah memanfaatkan fakta bahwa boolean benar ketika dilemparkan sebagai bilangan bulat menjadi 1, menggunakan $c += $f == 2;daripada if ($f == 2) $c++;.
WebSmithery
sumber
1
Anda tidak perlu mendefinisikan $ c, itu dihitung sebagai 0 pada + pertama =
Einacio
@Einacio Apa aturan mainnya? Apakah itu diizinkan, karena memberikan pemberitahuan peringatan variabel yang tidak ditentukan?
WebSmithery
@Einacio Rupanya setiap output ke STDERR dapat diabaikan, jadi terima kasih atas sarannya.
WebSmithery
1
+1 untuk penggunaan levenshtein. Ide bagus! $i%$t++<1lebih pendek dari $i%$t++==0.
Titus
1

Perl 6 , 83 byte

{+grep &is-prime,m:ex/^(.*)(.)(.*)$/.map:{|map
.[0]~*~.[2],grep *-.[1],?.[0]..9}}

Cobalah online!

Sean
sumber
Bagaimana kalau menggunakan X~bukan map? 81 byte
Jo King
0

PHP, 100 +1 byte

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;

Jalankan sebagai pipa dengan -nRatau coba online .

kerusakan

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

Java 8, 201 194 byte

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

Penjelasan:

Coba di sini.

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):"") akan menghasilkan bilangan bulat ini:

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

Kevin Cruijssen
sumber
0

JavaScript (ES7), 118 byte

Mengambil input sebagai string.

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

Cobalah online!

Berkomentar

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

Ruby dengan -rprime, 101 byte

-rprime10flHaiHair(lHaig10n)+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}}

Cobalah online!

Nilai Tinta
sumber