Temukan nomor Rocco

12

Saya ditanya pertanyaan ini dalam sebuah wawancara tetapi saya tidak dapat menemukan solusi. Saya tidak tahu apakah pertanyaannya benar atau tidak. Saya mencoba banyak tetapi tidak dapat mencapai solusi apa pun. Jujur saja, tidak ada yang terlintas di pikiran saya.

Nomor Rocco

Bilangan bulat positif adalah bilangan Rocco jika bilangan tersebut dapat direpresentasikan sebagai atau , di mana adalah bilangan prima.nn=hal(hal+14)n=hal(hal-14)hal

10 angka Rocco pertama adalah:

32,51,95,147,207,275,351,435,527,627

Tugas

Kode Anda harus menerima bilangan bulat positif sebagai input dan menentukan apakah itu nomor Rocco atau tidak.

Brownie poin

  • Tulis fungsi yang menghitung dan mencetak jumlah angka Rocco kurang dari atau sama dengan 1 juta.
  • Tulis fungsi yang menghitung dan mencetak hitungan angka Rocco dari pertanyaan bonus (di atas yang) prima.
kode vijays
sumber
5
Hai dan selamat datang di PPCG. Kami menerima tantangan (penampilan Anda sangat menarik) yang memiliki kriteria penilaian dan kemenangan yang objektif. Coba edit posting Anda untuk memasukkan itu. Saya merekomendasikan kode-golf sebagai tujuannya, karena ini adalah cara termudah untuk mendapatkan yang benar. Juga, Anda ingin menghindari bonus itu; hanya fokus pada satu tugas yang jelas.
Adám
3
output akan berupa bilangan bulat : Bukankah maksud Anda Boolean untuk apakah inputnya adalah nomor Rocco atau tidak?
Adám
5
Bonus 2: print 0. Semua angka Rocco adalah gabungan (n*..), jadi tidak ada bilangan prima dalam kisaran apa pun.
TFeld
4
"Poin bonus" bisa berupa nilai yang dikodekan dengan keras, dan sama sekali tidak menguntungkan tantangan. Saya sarankan menghapusnya.
Erik the Outgolfer
5
Saya telah mengedit pertanyaan dan tag. Jangan ragu untuk mengembalikan atau mengedit lebih lanjut jika Anda tidak setuju. Seperti yang dikatakan @EriktheOutgolfer, saya pikir bonus harus dihapus.
Arnauld

Jawaban:

10

05AB1E , 8 byte

Mengembalikan jika adalah nomor Rocco, atau sebaliknya.1n0

fDŠ/α14å

Cobalah online!

Bagaimana?

Diberikan bilangan bulat positif , kami menguji apakah ada faktor prima dari sehingga:nhaln

|hal-nhal|=14

Berkomentar

fDŠ/α14å  # expects a positive integer n as input       e.g. 2655
f         # push the list of unique prime factors of n  -->  2655, [ 3, 5, 59 ]
 D        # duplicate it                                -->  2655, [ 3, 5, 59 ], [ 3, 5, 59 ]
  Š       # moves the input n between the two lists     -->  [ 3, 5, 59 ], 2655, [ 3, 5, 59 ]
   /      # divide n by each prime factor               -->  [ 3, 5, 59 ], [ 885, 531, 45 ]
    α     # compute the absolute differences
          # between both remaining lists                -->  [ 882, 526, 14 ]
     14å  # does 14 appear in there?                    -->  1
Arnauld
sumber
11

JavaScript (ES7), 55 byte

n=>(g=k=>k>0&&n%--k?g(k):k==1)(n=(49+n)**.5-7)|g(n+=14)

Cobalah online!

Bagaimana?

Dengan bilangan bulat positif , kami mencari bilangan prima sehingga atau .nxx(x+14)=nx(x-14)=n

Oleh karena itu persamaan kuadrat berikut:

(1)x2+14x-n=0
(2)x2-14x-n=0

Akar positif dari adalah:(1)

x0=49+n-7

dan akar positif dari adalah:(2)

x1=49+n+7

Oleh karena itu, masalahnya setara dengan menguji apakah atau adalah prima.x0x1

Untuk melakukan itu, kami menggunakan fungsi tes primality rekursif klasik, dengan tes tambahan untuk memastikan bahwa itu tidak berulang selamanya jika diberi nomor irasional sebagai input.

g = k =>    // k = explicit input; this is the divisor
            // we assume that the implicit input n is equal to k on the initial call
  k > 0 &&  // abort if k is negative, which may happen if n is irrational
  n % --k ? // decrement k; if k is not a divisor of n:
    g(k)    //   do a recursive call
  :         // else:
    k == 1  //   returns true if k is equal to 1 (n is prime)
            //   or false otherwise (n is either irrational or a composite integer)

Fungsi pembungkus utama:

n => g(n = (49 + n) ** .5 - 7) | g(n += 14)
Arnauld
sumber
6

Perl 6 , 45 28 byte

((*+49)**.5+(7|-7)).is-prime

Cobalah online!

Menggunakan konstruksi Arnauld , bahwa harus menjadi prima agar menjadi nomor Rocco.n+49±7n

Penjelasan:

 (*+49)**.5                   # Is the sqrt of input+49
           +(7|-7)            # Plus or minus 7
(                 ).is-prime  # Prime?
Jo King
sumber
6

Regex (ECMAScript), 64 62 byte

Regex ini menemukan dua angka dan sehingga . Jika menemukan mereka, itu kemudian menegaskan bahwa atau adalah prima. Itu dia!SebuahSebuah+14n=Sebuah(Sebuah+14)SebuahSebuah+14

Ini menggunakan varian dari algoritma multiplikasi yang dijelaskan secara singkat dalam paragraf posting regex angka saya yang berlimpah . Ini adalah spoiler . Jadi jangan membaca lebih jauh jika Anda tidak ingin beberapa sihir regex unary canggih dimanjakan untuk Anda . Jika Anda ingin mencoba mencari tahu sendiri keajaiban ini, saya sangat menyarankan memulai dengan memecahkan beberapa masalah dalam daftar masalah yang direkomendasikan secara spoiler-tag pada posting sebelumnya , dan mencoba untuk menemukan wawasan matematika secara mandiri.

Algoritma multiplikasi diterapkan secara berbeda di sini karena kami menyatakan bahwa dua nilai yang dikenal dikalikan bersama dengan nilai yang diketahui lainnya (seperti yang juga dilakukan dalam versi alternatif dari regex dalam posting ini , untuk menguji angka menjadi kuadrat sempurna). Dalam sebagian besar jawaban saya yang diposting regex sejauh ini, perkalian diimplementasikan sebagai perhitungan (bukan pernyataan, secara konseptual) di mana tujuannya adalah untuk menemukan produk dari dua angka yang dikenal. Kedua metode bekerja di kedua keadaan, tetapi golf-bijaksana, lebih buruk dalam melakukan pekerjaan masing-masing.

^(?=(x((x{14})(x+)))(?=(\1*)\4\2*$)(\1*$\5))\6\3?(?!(xx+)\7+$)

Cobalah online!


 # For the purposes of these comments, the input number = N.
 ^
 # Find two numbers A and A+14 such that A*(A+14)==N.
 (?=
     (x((x{14})(x+)))   # \1 = A+14; \2 = \1-1; \3 = 14; \4 = A-1; tail -= \1
     (?=                # Assert that \1 * (\4+1) == N.
         (\1*)\4\2*$    # We are asserting that N is the smallest number satisfying
                        # two moduli, thus proving it is the product of A and A+14
                        # via the Chinese Remainder Theorem. The (\1*) has the effect
                        # of testing every value that satisfies the "≡0 mod \1"
                        # modulus, starting with the smallest (zero), against "\4\2*$",
                        # to see if it also satisfies the "≡\4 mod \2" modulus; if any
                        # smaller number satisfied both moduli, (\1*) would capture a
                        # nonzero value in \5. Note that this actually finds the
                        # product of \4*\1, not (\4+1)*\1 which what we actually want,
                        # but this is fine, because we already subtracted \1 and thus
                        # \4*\1 is the value of tail at the start of this lookahead.
                        # This implementation of multiplication is very efficient
                        # golf-wise, but slow, because if the number being tested is
                        # not even divisible by \1, the entire test done inside this
                        # lookahead is invalid, and the "\1*$" test below will only
                        # fail after this useless test has finished.
     )
     (\1*$\5)           # Assert that the above test proved \1*(\4+1)==N, by
                        # asserting that tail is divisible by \1 and that \5==0;
                        # \6 = tool to make tail = \1
 )
 # Assert that either A or A+14 is prime.
 \6                     # tail = \1 == A+14
 \3?                    # optionally make tail = A
 (?!(xx+)\7+$)          # Assert tail is prime. We don't need to exclude treating
                        # 1 as prime, because the potential false positive of N==15
                        # is already excluded by requiring \4 >= 1.
 

Kode mati
sumber
3

Brachylog , 13 12 byte

ṗ;14{+|-};?×

Masukkan nomor kandidat sebagai argumen baris perintah. Output trueatau false. Cobalah online!

Penjelasan

Kode adalah predikat yang inputnya tidak dibatasi dan yang outputnya adalah nomor yang kami uji.

ṗ             Let the input ? be a prime number
 ;14          Pair it with 14, yielding the list [?, 14]
    {+|-}     Either add or subtract, yielding ?+14 or ?-14
         ;?   Pair the result with the input, yielding [?+14, ?] or [?-14, ?]
           ×  Multiply; the result must match the candidate number

(Tips dipersilakan. Itu {+|-}masih terasa kikuk.)

DLosc
sumber
3

Brachylog , 9 byte

Pendekatan yang berbeda dari jawaban DLosc

Ċ-14&∋ṗ&×

Mengambil N sebagai output, memberikan [P, P-14] atau [P + 14, P] kembali melalui input (angka terbesar pertama)

penjelasan

Ċ              # The 'input' is a pair of numbers
 -14           #   where the 2nd is 14 smaller then the first
    &∋ṗ        #   and the pair contains a prime
       &×      #   and the numbers multiplied give the output (N)

Cobalah online!

Kroppeb
sumber
2

Pyth, 22 20 byte

}Qsm*Ld+Ld_B14fP_TSh

Cobalah online di sini .

}Qsm*Ld+Ld_B14fP_TShQ   Implicit: Q=eval(input())
                        Trailing Q inferred
                  ShQ   Range [1-(Q+1)]
              fP_T      Filter the above to keep primes
   m                    Map the elements of the above, as d, using:
          _B14            [14, -14]
       +Ld                Add d to each
    *Ld                   Multiply each by d
  s                     Flatten result of map
}Q                      Is Q in the above? Implicit print

Sunting: Disimpan 3 byte sebagai input akan selalu positif, jadi tidak perlu menyaring nilai-nilai negatif dari daftar. Juga memperbaiki bug untuk input 1dan 2, biaya 1 byte. Versi sebelumnya:}Qsm*Ld>#0+Ld_B14fP_TU

Sok
sumber
2

05AB1E , 16 15 14 byte

Disimpan 1 byte oleh komputasi 14 dengan bukannya žvÍ(tidak percaya saya tidak memikirkan ini di tempat pertama).

Disimpan 1 byte berkat Emigna

ÅPε7·D(‚+y*Q}Z

Cobalah online! atau Uji semua input

Penjelasan

                 # Implicit input n
ÅP               # Push a list of primes up to n
  ε         }    # For each prime in the list...
   7·            # Push 14 (by doubling 7)
     D(‚         # Push -14 and pair them together to get [14,-14]
        +        # Add [14,-14] to the prime
         y*      # Multiply the prime to compute p(p-14) and p(p+14)
           Q     # Check if the (implicit) input is equal to each element
             Z   # Take the maximum
Wisław
sumber
1
Anda dapat menyimpan byte dengan mengubah }˜såuntuk Q}Zmenggunakan input implisit. Test-Suite Anda harus diubah sedikit menjadi seperti ini agar bisa berfungsi. Juga, cara yang lebih jelas untuk menulis žvÍatau menjadi 14;)
Emigna
Terima kasih! Mengapa membuatnya mudah ketika Anda dapat menekan 14 dengan cara / facepalm yang paling rumit :)
Wisław
2

Retina 0.8.2 , 61 byte

.+
$*
^((1{14})1(1)+)(?<=(?<!^\4+(..+))\2?)(?<-3>\1)+$(?(3)1)

Cobalah online! Penjelasan:

.+
$*

Konversikan ke unary.

^((1{14})1(1)+)

\1menangkap lebih besar dari dua faktor. \2menangkap konstanta 14, menghemat satu byte. \3menangkap lebih kecil dari dua faktor, minus 1. Ini juga memastikan bahwa kedua faktor minimal 2.

(?<=(?<!^\4+(..+))\2?)

Periksa kedua faktor untuk memastikan setidaknya satu di antaranya prima. Gagasan menggunakan \2?dicuri tanpa malu-malu dari jawaban @ Deadcode.

(?<-3>\1)+

Ulangi yang lebih besar dari dua faktor beberapa kali sama dengan satu lebih kecil dari dua faktor yang lebih kecil. Seperti yang telah kita tangkap faktor yang lebih besar setelah ini maka akhirnya menangkap produk dari dua faktor.

$(?(3)1)

Pastikan produk sama dengan angka yang diberikan.

Terjemahan langsung ke Retina 1 dengan mengganti $*dengan *1akan memiliki jumlah byte yang sama tetapi byte dapat disimpan dengan mengganti semua 1s dengan _s dan kemudian *1dapat diganti dengan *alih - alih *_. Jawaban Retina 1 sebelumnya untuk 68 byte:

.+
*
Lw$`^(__+)(?=(\1)+$)
$1 _$#2*
Am` (__+)\1+$
(_+) \1

0m`^_{14}$

Cobalah online! Penjelasan:

.+
*

Konversikan ke unary.

Lw$`^(__+)(?=(\1)+$)
$1 _$#2*

Temukan semua pasangan faktor.

Am` (__+)\1+$

Pastikan satu adalah prima.

(_+) \1

Ambil perbedaan absolut.

0m`^_{14}$

Periksa apakah ada 14.

Neil
sumber
1

JavaScript (Babel Node) , 69 byte

Sial, saya pikir saya akan mengalahkan Jawaban Arnaulds tetapi tidak .....: c

x=>[...Array(x)].some((a,b)=>x/(a=(p=n=>--b-1?n%b&&p(n):n)(b))-a==14)

Cobalah online!

Saya ingin menyingkirkan x=>[...Array(x)].some(bagian menggunakan rekursi sehingga mungkin menjadi lebih pendek dari waktu ke waktu

Penjelasan

x=>[...Array(x)]                                                              Creates a range from 0 to x-1 and map:

                .some((a,b)=>                                                 Returns True if any of the following values is true
                             x/                                              Input number divided by
                                (a=(p=n=>--b-1?n%b&&p(n):n)(b))               recursive helper function. Receives a number (mapped value) as parameters and returns 
                                                                              the same number if it is prime, otherwise returns 1. Take this value
                                                                              and assign to variable a
                                                               -a            Subtract a from the result  
                                                                     ==14    Compare result equal to 14

Ini menggunakan rumus

n/hal-hal==14

Luis felipe De jesus Munoz
sumber
1

APL (NARS) 16 karakter, 32 byte

{14=∣r-⍵÷r←↑⌽π⍵}

{π⍵} akan menemukan faktorisasi argumennya dan kami menduga bahwa elemen terakhir dari hasilnya (daftar pembagi n) adalah pembagi utama maksimum n; Di sini kita mengira bahwa satu definisi yang setara dari angka Rocco adalah: n adalah angka Rocco <=> prima faktor maks dari n: r sedemikian rupa sehingga benar 14 = ∣rn ÷ r [untuk k pseudocode sebagai 14 == abs (rn / r) definisi nomor Rocco ini tampaknya ok pada akhirnya di kisaran 1..1000000]; kisaran nilai ok akan menjadi 1..maxInt; uji:

 f←{14=∣r-⍵÷r←↑⌽π⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨1..10000
32  51  95  147  207  275  351  435  527  627  851  1107  1247  1395  1551  1887  2067  2255  2451  2655  2867  3551  4047  4307  4575  5135  5427  5727  6035  6351  6675  7347  8051  8787  9167  9951   
RosLuP
sumber
1

C # (Visual C # Interactive Compiler) , 99 byte

n=>Enumerable.Range(2,n).Any(p=>Enumerable.Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

Cobalah online!

Enumerable.Range menyerang lagi :) Menggunakan flag compiler gila, Anda dapat mengurangi banyak hal, meskipun saya agak penggemar solusi vanilla.

C # (Visual C # Interactive Compiler) + /u:System.Linq.Enumerable, 77 byte

n=>Range(2,n).Any(p=>Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

Cobalah online!

Di bawah ini adalah port solusi Arnauld yang tampak cukup keren. Saat ini terpanjang, tetapi mungkin bisa golf beberapa.

C # (Visual C # Interactive Compiler) , 101 byte

n=>{bool g(int k)=>--k<2?n>1:n%k>0&g(k);var d=Math.Sqrt(n+49)-7;return(n=(int)d)==d&(g(n)|g(n+=14));}

Cobalah online!

dana
sumber
0

APL (NARS) 30 karakter, 60 byte

{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}

Di sini 0π adalah fungsi mengatakan jika satu angka adalah bilangan prima, uji:

 f←{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨0..700
32  51  95  147  207  275  351  435  527  627
RosLuP
sumber
0

F #, 2 jawaban (tidak bersaing)

Saya sangat menyukai jawaban @Arnauld, jadi saya menerjemahkannya.

123 byte , berdasarkan pada jawaban JavaScript

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||)

Penjelasan:

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||) //Lambda which takes an integer, n
       let t=int<|sqrt(float n+49.)                                                                                         //let t be n, converted to float, add 49 and get square root, converted back to int (F# type restrictions)
                                   in                                                                                       //in the following...
                                                                                                  [t-7;t+7]                 //Subtract and add 7 to t in a list of 2 results (Lists and Seqs can be interchanged various places)
                                      Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)                          //See if either are prime (here, if either result has 2 and only 2 divisors)
                                                                                                           |>Seq.reduce(||) //And logically OR the resulting sequence

125 byte , berdasarkan jawaban 05AB1E

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14

Penjelasan:

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14  //Lambda which takes an integer, n
       let l=Seq.filter(fun i->n%i=0)[2..n-1]                                                                                  //let l be the list of n's primes 
                                             in                                                                                //in...
                                                let m=Seq.map(fun i->n/i)l                                                     //m, which is n divided by each of l's contents
                                                                           in                                                  //and then...
                                                                              Seq.map2(fun a b->abs(a-b))l m                   //take the absolute difference between each pair of items in the two sequences to make a new sequence
                                                                                                            |>Seq.contains 14  //and does the resulting sequence contain the number 14?
LSM07
sumber
0

Python 2 , 58 byte

Output dengan kode keluar, gagal ( 1) untuk nomor Rocco.

P=k=1.
n=input()
exec"P*=k*k;k+=1;P%k*abs(n/k-k)==14>y;"*n

Cobalah online!

ovs
sumber