Bisakah angka bahkan menjadi prima?

24

Urutannya

Semua orang tahu satu-satunya bilangan prima adalah 2. Ho-hum. Tapi, ada bilangan genap tertentu di nmana, ketika digabungkan dengan n-1, mereka menjadi bilangan prima.

Sebagai permulaan, 1tidak ada dalam daftar, karena 10tidak prima. Demikian pula dengan 2( 21), dan 3( 32). Namun, 4berfungsi karena 43prima, jadi ini adalah angka pertama dalam urutan a(1) = 4. Angka berikutnya yang berfungsi (baik 6( 65) maupun 8( 87) berfungsi) adalah 10, karena 109adalah bilangan prima, jadi a(2) = 10. Lalu kami melewati banyak lagi sampai 22, karena 2221itu utama, jadi a(3) = 22. Dan seterusnya.

Jelas semua istilah dalam urutan ini adalah genap, karena bilangan ganjil nketika digabungkan dengan n-1menjadi genap (seperti 3berubah menjadi 32), yang tidak akan pernah menjadi prima.

Ini adalah urutan A054211 pada OEIS.

Tantangan

Mengingat nomor input nyang cocok di suatu tempat ke dalam urutan ini (yaitu, ndigabungkan dengan n-1prima), output posisinya dalam urutan ini. Anda dapat memilih 0 atau 1 diindeks, tetapi sebutkan yang Anda kirim.

Aturan

  • Input dan output dapat dianggap sesuai dengan tipe integer asli bahasa Anda.
  • Input dan output dapat diberikan dalam format apa pun yang nyaman .
  • Program lengkap atau fungsi dapat diterima. Jika suatu fungsi, Anda dapat mengembalikan output daripada mencetaknya.
  • Jika memungkinkan, harap sertakan tautan ke lingkungan pengujian online agar orang lain dapat mencoba kode Anda!
  • Celah standar dilarang.
  • Ini adalah sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.

Contohnya

Contoh di bawah ini adalah 1-diindeks.

n = 4
1

n = 100
11

n = 420
51
AdmBorkBork
sumber
1
Mengapa Anda harus melakukannya secara terbalik? cQuents tidak memiliki mode itu :(
Stephen
4
@ LangkahHanya Hanya untuk perubahan kecepatan; sesuatu yang berbeda dari biasanya.
AdmBorkBork
9
Saya merasa ini akan jauh lebih baik sebagai masalah keputusan.
Wheat Wizard
4
Tidak hanya 2 bilangan prima yang dapat habis dibagi 2, 3 juga merupakan bilangan prima yang dapat dibagi dengan 3, dan 5 adalah satu-satunya bilangan prima yang dapat dibagi dengan 5. Secara umum, bilangan prima nselalu merupakan satu-satunya bilangan prima yang dapat dibagi n. Itu tidak istimewa - hanya bagaimana bilangan prima bekerja.
Buah Esolanging

Jawaban:

11

Jelly ,  8  7 byte

ḊżṖVÆPS

Tautan monadik yang mengambil anggota urutan dan mengembalikan indeksnya dalam urutan.

Cobalah online!

Bagaimana?

ḊżṖVÆPS - Link: number, n
Ḋ       - dequeue (implicit range) = [ 2   , 3   , 4   ,... ,              n         ]
  Ṗ     - pop (implicit range)     = [   1 ,   2 ,   3 ,... ,                  n-1   ]
 ż      - zip                      = [[2,1],[3,2],[4,3],... ,             [n , n-1]  ]
   V    - evaluate as Jelly code   = [ 21  , 32  , 43  ,... ,         int("n"+"n-1") ]
    ÆP  - is prime? (vectorises)   = [  0  ,  0  ,  1  ,... , isPrime(int("n"+"n-1"))]
      S - sum
Jonathan Allan
sumber
TIO Bukan untuk saya, mungkin saja kembali?
Conor O'Brien
1
Diperbaiki mulai 2 menit yang lalu :)
Jonathan Allan
Indah! Itu zip(head(), pop())trik benar-benar dingin. :)
DJMcMayhem
Dalam pengkodean apa itu 7 byte?
kylefinn
1
@kylefinn Jelly memiliki halaman kode sendiri, klik tautan byte di header untuk melihatnya.
Jonathan Allan
8

Haskell , 80 75 70 byte

5 byte menghemat berkat Laikoni

p x=all((>0).mod x)[2..x-1]
g n=sum[1|x<-[4..n],p$read$show=<<[x,x-1]]

Cobalah online!

Wisaya Gandum
sumber
1
Saya pikir Anda dapat menggunakan tes prime pendek p x=all((>0).mod x)[2..x-1]yang gagal untuk 1, tetapi ini seharusnya tidak menjadi masalah dalam kasus ini.
Laikoni
1
Juga show x++show(x-1)bisa disingkat menjadi show=<<[x,x-1].
Laikoni
@Laikoni Terima kasih atas tipsnya! Saya pikir itu showbisa dilakukan dengan metode yang lebih pendek tetapi saya tidak memikirkan peta konser karena alasan tertentu.
Wheat Wizard
6

Jelly , 12, 10 , 8 byte

;’VÆPµ€S

Cobalah online!

1-2 byte disimpan berkat @ nmjmcman101, dan 2 byte disimpan berkat @Dennis!

Penjelasan:

     µ€   # For N in range(input()):
;         #   Concatenate N with...
 ’        #   N-1
  V       #   And convert that back into an integer
   ÆP     #   Is this number prime?
       S  # Sum that list 
DJMcMayhem
sumber
Bisakah Anda menjatuhkan R dan menggunakan rentang implisit?
nmjcman101
@ nmjcman101 Saya benar-benar tidak tahu itu sesuatu. Terima kasih!
DJMcMayhem
5

05AB1E , 9 8 7 byte

Kode

ƒNN<«pO

Menggunakan penyandian 05AB1E . Cobalah online!

Penjelasan

ƒ          # For N in [0 .. input]..
 NN<«      #   Push n and n-1 concatenated
     p     #   Check for primality
      O    #   Sum the entire stack (which is the number of successes)
Adnan
sumber
Tentu saja ini mengambil keuntungan dari kenyataan bahwa 05AB1E mengabaikan kesalahan ... karena saya tidak berpikir Anda dapat memeriksa apakah '0-1'ini prima.
Erik the Outgolfer
5

Sekam , 13 11 10 byte

1solusi -indeks:

#ȯṗdS¤+d←ḣ

Cobalah online!

Tidak Terikat / Penjelasan

         ḣ -- in the range [1..N]
#          -- count the number where the following predicate is true
        ←  --   decrement number,
    S  d   --   create lists of digits of number and decremented 
     ¤+    --   concatenate,
   d       --   interpret it as number and
 ȯṗ        --   check if it's a prime number

Terima kasih @Zgarb untuk -3byte!

ბიმო
sumber
1
£İpsetara dengan . Anda juga dapat menyimpan byte dengan #…ḣalih - alih £f…N.
Zgarb
4

Python 2 , 87 byte

-2 byte berkat @officialaimm . 1-diindeks.

lambda n:sum(all(z%v for v in range(2,z))for i in range(4,n+1)for z in[int(`i`+`i-1`)])

Test Suite.

Tuan Xcoder
sumber
Saya bermain golf ini sesegera mungkin. Saran diterima.
Tn. Xcoder
87 byte
officialaimm
4

Pyth , 12 byte

smP_s+`d`tdS

Cobalah online! atau Verifikasi semua Uji Kasus.


Bagaimana?

smP_s+`d`tdSQ  -> Full Program. Takes input from Standard Input. Q means evaluated input
                  and is implicit at the end.

 m         SQ  -> Map over the Inclusive Range: [1...Q], with the current value d.
    s+`d`td    -> Concatenate: d, the current item and: td, the current item decremented. 
                  Convert to int.
  P_           -> Prime?
s              -> Sum, counts the occurrences of True.
Tuan Xcoder
sumber
4

Japt , 15 14 12 11 9 8 byte

1-diindeks.

ÇsiZÄÃèj

Cobalah

Ç            :Map each Z in the range [0,input)
 s           :  Convert to string
  i          :    Prepend
   ZÄ        :    Z+1
     Ã       :End map
      è      :Count
       j     :  Primes
Shaggy
sumber
1
11 byte
Oliver
Gah! Mengapa saya memiliki blindspot untuk Ædan Ç?! Terima kasih, @Oliver; Saya akan memperbarui ketika saya kembali ke komputer.
Shaggy
2o+X(Dengan ruang tambahan) akan berfungsi sebagai pengganti [XXÉ], meskipun jika saya pernah menggunakan []kurung balancing otomatis, solusi Anda akan lebih pendek satu byte. (Sebenarnya 2, karena Anda bisa melakukannya õ_ZÉ]¬nÃèj)
ETHproduk
@ ETHproductions: Hari-hari ini, hal pertama yang saya lakukan ketika bekerja dengan array adalah memeriksa untuk melihat apakah auto-balancing telah ditambahkan []! : D
Shaggy
Untuk beberapa alasan saya pikir titik koma sepenuhnya berhenti bekerja juga, jadi saya akan mencoba memperbaikinya. Jangan berpikir saya akan memiliki kesempatan sampai besok sore.
ETHproduk
3

Röda , 73 byte

{seq 3,_|slide 2|parseInteger`$_2$_1`|{|i|[1]if seq 2,i-1|[i%_!=0]}_|sum}

Cobalah online!

1-diindeks. Menggunakan aliran untuk melakukan input dan output.

Penjelasan:

{
seq 3,_| /* Create a stream of numbers from 3 to input */
slide 2| /* Duplicate every number except the first and the last
            to create (n-1,n) pairs */
parseInteger`$_2$_1`| /* Concatenate n and n-1 and convert to integer */
{|i| /* For every i in the stream: */
    [1]if seq 2,i-1|[i%_!=0] /* Push 1 if i is a prime
                                (not divisible by smaller numbers) */
}_|
sum /* Return the sum of numbers in the stream */
}
fergusq
sumber
2

Pyth , 14 byte

lfP_Tms+`d`tdS

Cobalah online!

Penjelasan

              Q    # Implicit input
             S     # 1-indexed range
     m             # For d in range [1, Q]...
      s+`d`td      # Concatenate d and d - 1
 fP_T              # Filter on primes
l                  # Return the length of the list
Jim
sumber
Anda mengalahkan saya beberapa detik, saya mengalahkan Anda beberapa byte: P
Mr. Xcoder
@ Mr.Xcoder Versi pertama saya adalah lfTmP_s+`d`tdS, sangat disayangkan bahwa saya tidak menemukan trik Anda sendiri pada saat itu :)
Jim
2

Perl 6 , 45 byte

{first :k,$_,grep {is-prime $_~.pred},1..∞}

Cobalah online!

Yang grepmenghasilkan urutan angka-angka yang memenuhi syarat, maka kita mencari kunci ( :k) (yaitu, indeks) dari firstnomor dalam daftar yang sama dengan parameter input $_.

Sean
sumber
30 byte
Jo King
2

C, 99 94 byte

1 diindeks. Sungguh menyakitkan saya untuk menulis tes primality yang begitu boros secara komputasi, tetapi bagaimanapun juga byte adalah byte.

Jika kami mengizinkan beberapa hal yang benar-benar rapuh, kompilasi di komputer saya tanpa optimisasi dengan GCC 7.1.1, 94 byte berikut berfungsi (terima kasih @Conor O'Brien )

i,c,m,k;f(n){c=i=1;for(;++i<n;c+=m==k){for(k=m=1;m*=10,m<i;);for(m=i*m+i-1;++k<m&&m%k;);}n=c;}

jika tidak, 99 byte yang lebih kuat ini berfungsi

i,c,m,k;f(n){c=i=1;for(;++i<n;c+=m==k){for(k=m=1;m*=10,m<i;);for(m=i*m+i-1;++k<m&&m%k;);}return c;}

Program lengkap, sedikit lebih mudah dibaca:

i,c,m,k;
f(n){
    c=i=1;
    for(;++i<n;c+=m==k){
        for(k=m=1;m*=10,m<i;);
        for(m=i*m+i-1;++k<m&&m%k;);
    }
    return c;
}

int main(int argc, char *argv[])
{
    printf("%d\n", f(atoi(argv[1])));
    return 0;
}
algmyr
sumber
Bergantung pada kompiler Anda, Anda mungkin dapat menyimpan beberapa byte dengan menggunakan n=c;alih-alih return c;:i,c,m,k;f(n){c=i=1;for(;++i<n;c+=m==k){for(k=m=1;m*=10,m<i;);for(m=i*m+i-1;++k<m&&m%k;);}n=c;}
Conor O'Brien
Saya tidak bisa mengatakan saya ingin menggunakan hal-hal yang bahkan tampaknya berbeda dengan tingkat optimisasi. Menggunakan GCC, tanpa optimasi -O0 berfungsi, dengan flag optimasi lainnya tidak. Menariknya -O1 -O2 dan -O3 mengembalikan 0, dengan -Os mengembalikan 1, dengan -Og mengembalikan n-1.
algmyr
Anda selalu dapat menentukan dalam jawaban Anda bagaimana program Anda harus dikompilasi.
Conor O'Brien
Saya kira, terasa agak murah. Tapi saya bisa menambahkan alternatif.
algmyr
Saya mengerti, tapi saya tidak akan merasa bersalah melakukan itu - itu salah satu tips untuk bermain golf di C
Conor O'Brien
2

JavaScript (ES6),  49 48  47 byte

1-diindeks. Terbatas oleh ukuran tumpukan panggilan mesin Anda.

f=n=>n&&f(n-2)+(p=n=>n%--x?p(n):x<2)(x=n+[--n])

Cobalah online!

Arnauld
sumber
1

Mathematica, 77 byte

Position[Select[Range@#,PrimeQ@FromDigits[Join@@IntegerDigits/@{#,#-1}]&],#]&
J42161217
sumber
0

QBIC , 25 byte

[:|p=p-µa*z^_l!a$|+a-1}?p

Penjelasan

[:|     FOR a = 1 to <n>
p=p-    Decrement p (the counter) by
µ       -1 if the following is prime, or 0 if not
        For the concatenating, we multiply 'a' by 10^LENGTH(a), then add a-1$┘p
        Example 8, len(8) = 1, 8*10^1 = 80, add 8-1=7, isPrime(87) = 0
a*z^_l!a$|+a-1
}       Close the FOR loop - this also terminates the prime-test
?p      Print p, the 0-based index in the sequence.

Ini menggunakan beberapa hal matematika yang cukup terlibat dengan cast-to-string ditampar untuk ukuran yang baik. Membuat topi versi tidak hanya menggabungkan string berbasis satu byte lebih lama:

[:|A=!a$+!a-1$┘p=p-µ!A!}?p
steenbergh
sumber
0

PHP , 203 byte

<?php $n=($a=$argv[1]).($a-1);$p=[2];$r=0;for($b=2;$b<=$n;$b++){$x=0;if(!in_array($b,$p)){foreach($p as $v)if(!($x=$b%$v))break;if($x)$p[]=$b;}}for($b=1;$b<=$a;$b++)if(in_array($b.($b-1),$p))$r++;die $r;

Cobalah online!

Menggunakan indeks berbasis-1 untuk output. TIO link memiliki versi kode yang dapat dibaca.

Mic1780
sumber
0

Ruby , 42 + 9 = 51 byte

Menggunakan -rprime -nbendera. 1-diindeks.

Bekerja dengan menghitung semua angka sama dengan atau di bawah input yang memenuhi kondisi (atau lebih teknis, semua angka yang memenuhi n-1kondisi). Karena input dijamin dalam urutan, tidak ada risiko kesalahan dari input acak seperti 7itu tidak "menjadi prima".

p (?3..$_).count{|i|eval(i.next+i).prime?}

Cobalah online!

Nilai Tinta
sumber
0

Ruby , 62 byte

->g{(1..g).count{|r|(2...x=eval([r,r-1]*'')).none?{|w|x%w<1}}}

Cobalah online!

1-diindeks

GB
sumber
0

Python 2 , 85 byte

1-diindeks

lambda n:sum(all(z%v for v in range(2,z))for i in range(3,n)for z in[int(`i+1`+`i`)])

Uji

Perbaikan jawaban Mr. Xcoder

Halvard Hummel
sumber
0

Java 8, 108 byte

n->{for(long r=0,q=1,z,i;;){for(z=new Long(q+""+~-q++),i=2;i<z;z=z%i++<1?0:z);if(z>1)r++;if(q==n)return r;}}

Diindeks 0

Penjelasan:

Cobalah online.

n->{                             // Method with integer parameter and long return-type
  for(long r=0,                  //  Result-long, starting at 0
      q=1,                       //  Loop integer, starting at 1
      z,i;                       //  Temp integers
      ;){                        //  Loop indefinitely
    for(z=new Long(q+""+~-q++),  //   Set z to `q` concatted with `q-1`
        i=2;i<z;z=z%i++<1?0:z);  //   Determine if `z` is a prime,
      if(z>1)                    //   and if it indeed is:
        r++;                     //    Increase the result-long by 1
      if(q==n)                   //   If `q` is now equal to the input integer
        return r;}}              //    Return the result
Kevin Cruijssen
sumber
0

Stax , 10 byte

1- Diindeks

Äm▬á┌╕|°φ♦

Jalankan dan debug Penjelasannya

Rxr\{$e|pm|+         #Full program, unpacked, implicit input  (Example (4))
R                    #Create [1 to input] range  (ex [1,2,3,4] )             
 x                   #Copy value from x register (ex (4) )
  r                  #Create [0 to input-1] range (ex [0,1,2,3)
   \                 #Create array pair using the range arrays (ex [[1,0],[2,1],[3,2],[4,3]])
    {    m           #Map block
     $e|p            #To string, eval string (toNum), isPrime (ex [1,0] => "10" => 10 => 0)
          |+         #Sum the array to calculate number of truths (ex [0,0,0,1] => 1)
Multi
sumber
0

Tidy , 33 byte

index({n:prime(n.n-1|int)}from N)

Cobalah online!

Penjelasan

Ide dasarnya adalah membuat urutan angka yang valid kemudian mengembalikan fungsi indeks kari.

index({n:prime(n.n-1|int)}from N)
      {n:                }from       select all numbers `n` from...
                               N     the set of natural numbers, such that:
               n.n-1                     `n` concatenated with `n-1`
                    |int                 ...converted to an integer
         prime(         )                ...is prime
index(                          )    function that returns index of input in that sequence
Conor O'Brien
sumber