Tetapkan bahwa bilangan asli p adalah prima +1 dari bilangan alami n jika p adalah bilangan prima dan representasi biner standar (yaitu, tanpa nol nol di depan) dari p dapat diperoleh dengan menambahkan (yaitu, mengawali, menambahkan atau menyisipkan) 1 tunggal untuk representasi biner standar n .

Sebagai contoh, representasi biner dari 17 adalah 10001 ₂ . Bilangan alami berbeda yang dapat dibentuk dengan menambahkan 1 hingga 10001 ₂ adalah 110001 ₂ atau 49 , 101001 ₂ atau 41 , 100101 ₂ atau 37 , dan 100011 ₂ atau 35 .

Di antaranya, 41 dan 37 adalah bilangan prima, jadi 17 memiliki dua bilangan prima +1 .

Tugas

Tulis program atau fungsi yang menerima bilangan bulat positif n sebagai input dan mencetak atau mengembalikan jumlah bilangan prima +1 yang unik dari n .

Input dan output harus berupa bilangan bulat, atau representasi string desimal atau unary.

Aturan standar kode-golf berlaku.

Uji kasus

Input:  4
Output: 0

Input:  1
Output: 1

Input:  17
Output: 2

Input:  33
Output: 3

Input:  553
Output: 4

Input:  3273
Output: 5

Input:  4145
Output: 6

Input:  4109
Output: 7

Input:  196869
Output: 8

Pyth, 20 byte

s/LPd{mij\1c.BQ]d2hQ

Test Suite

s/LPd{mij\1c.BQ]d2hQ
                        Q = eval(input())
      m           hQ    For insertion position in [0 ... Q]
            .BQ         Convert Q to binary string
           c   ]d       Chop at insertion position
        j\1             Join on '1'
       i         2      Convert to integer
     {                  Deduplicate
 /LPd                   Map each number to the number of times it occurs in its
                        prime factorization, e.g. whether or not it is prime.
s                       Sum and print.

JavaScript ES6, 141 byte 143 147 160

Menghemat 13 byte, terima kasih kepada @Nouak

n=>[...t=n.toString(2)].map((l,i)=>t.slice(0,v=i+1)+1+t.slice(v)).filter((l,i,a)=>a.indexOf(l)==i&&(p=(n,c)=>n%c&&c>n-2||p(n,++c))('0b'+l,2))

Metode yang mirip dengan jawaban TeaScript saya, menggunakan RegExp (Anda mendengar saya benar) untuk memeriksa bilangan prima.

Tidak disatukan

n=>
   [...t = n.toString(2)]                  // To binary
   .map((l,i)=>                            // Make cycles
               t.slice(0, v = i+1)
               + 1
               + t.slice(v)
   ).filter((l,i,a)=>  
                     a.indexOf(l) == i &&  // Remove Duplicates
                     (p=(n,c)=>            // Prime checking
                               n % c &&
                                 c > n - 2 ||
                                 p(n,++c)
                     )('0b'+l,2)
   ).length

Minkolang 0.11 , 54 52 byte

n1(2*d0c`,)(0c1c$%$r2*1c*1c++1g2:d1G)rxSI1-[0g2M+]N.

Penjelasan

n             Get integer from input (let's call it n)
1(       )    Get the smallest power of 2 (say, k) greater than input (starting with 1)
  2*d         Multiply by 2 and duplicate
     0c`,     Copy n and see if it's greater (while loop breaks on 0)

(0c1c$%                       Copy n, copy k, and divmod (pushes n//k, n%k)
       $r                     Swap top two elements
         2*                   Multiply by 2
           1c*                Copy k and multiply
              1c+             Copy k and add
                 +            Add
                  1g2:        Get k and divide by 2
                      d1G)    Duplicate and put one copy back in its former place

rx            Reverse and dump (dumps n and top of stack is now 0)
S             Remove duplicates
I1-[     ]    Check each element for primality
    0g        Get potential prime from bottom of stack
      2M      1 if prime, 0 otherwise
        +     Add (this is why I didn't dump the left-over 0 earlier)
N.            Output as integer and stop.

TeaScript , 22 byte

x÷¿®x÷E(i¬,1)¤©d¡F(¥)n

TeaScript mulai terlihat seperti APL ... Karakter khusus dikonversi menjadi lebih lama, urutan yang sering diulang

Penerjemah online pastikan untuk memeriksa "Input adalah angka."

Penjelasan && Tidak Disatukan

xT(2)s``m(#P(xT(2)E(i+1,1),2))d()F($P)n

xT(2)      // Take input, convert to binary
s``m(#     // Loop over input

  P(         // Convert to decimal...
     xT(2)     // Input to binary
     E(i+1,1)  // Inset 1 into (above) at current index in loop
  ,2)    

)d()       // Remove duplicates
F($P)      // Filter items that aren't prime
n          // Grab length.

Julia, 55 52 byte

n->sum(isprime,∪(2n+(k=2.^(0:endof(bin(n))))-n%k))

k=2.^(0:endof(bin(n)))menghasilkan array yang berisi kekuatan 2 dari 1 ke daya tertinggi kurang dari n. 2n+k-n%kkemudian menggunakan operasi array untuk menentukan semua kemungkinan "angka +1". ∪(setara dengan union, yang melakukan hal yang sama seperti uniquedalam situasi ini) menghilangkan nilai repeat. Kemudian sum(isprime,)menghitung jumlah bilangan prima dalam daftar.

CJam, 26 byte

Bukan pemenang, tetapi itu mengalahkan jawaban CJam yang ada dengan cukup solid dan ini adalah pertama kalinya saya menggunakan perintah 0.6.5 e\.

1ri2b+_,{_)e\_}%_&{2bmp},,

Uji di sini.

Penjelasan

1       e# Push a 1 (this is the 1 we'll be inserting everywhere).
ri      e# Read input and convert to integer.
2b      e# Convert to base 2.
+       e# Prepend the 1.
_,      e# Duplicate and get the number of bits N.
{       e# Map this block over i from 0 to N-1...
  _)    e#   Create a copy and increment to i+1.
  e\    e#   Swap the bits at positions i and i+1, moving the 1 one step through the array.
  _     e#   Duplicate so we keep this version on the stack.
}%
_&      e# Remove duplicates via set intersection with itself.
{       e# Filter the remaining digit lists based on this block...
  2b    e#   Convert bits back to an integer.
  mp    e#   Test for primality.
},
,       e# Get the length of the remaining list.

Satu hal yang perlu diperhatikan adalah bahwa kita menukar bit pada 0dan 1sebelum membuat salinan pertama, jadi kita kehilangan array asli dengan yang 1diawali dengan bagian depan. Namun, input selalu positif, sehingga digit terdepan akan selalu menjadi satu. Itu berarti setelah memprioritaskan yang lain, daftar digit akan selalu dimulai dengan [1 1 ...]sehingga swap pertama akan menjadi no-op dalam hal apa pun.

Mathematica, 87 byte

Union[#~FromDigits~2&/@StringReplaceList[#~IntegerString~2,a_:>a<>"1"]]~Count~_?PrimeQ&

Julia, 110 108 104 87 byte

n->sum(i->isprime(parse(Int,i,2)),(b=bin(n);∪([b[[1:i;1;i+1:end]]for i=1:endof(b)])))

Ini menciptakan fungsi tanpa nama yang menerima dan integer dan mengembalikan integer. Untuk menyebutnya, berikan nama, mis f=n->....

Tidak Disatukan:

function f(n::Integer)
    # Get the binary representation of n as a string
    b = bin(n)

    # Construct an array consisting of binary strings with
    # a one prepended, appended, and each insertion
    x = [b[[1:i; 1; i+1:end]] for i = 1:endof(b)]

    # Count the number of primes
    c = sum(i -> isprime(parse(Int, i, 2)), unique(x))

    return c
end

Disimpan 17 byte berkat Glen O!

CJam, 58 byte

L{:TQ\=A+Q\+TWe\-2<s:~2b}q~2b0+:Q,(%{:BLe=!{B+:L}&}%~:mp:+

Ini memakan waktu sehari, dan ini adalah pengulangan keempat saya.

Japt -x , 14 11 byte

ƤiX1Ãâ ®Íj

Cobalah atau jalankan semua test case

ƤiX1Ãâ ®Íj     :Implicit input of integer U
Æ               :Map each X in the range [0,U)
 ¤              :  Convert U to binary string
  iX1           :  Insert "1" at 0-based index X
     Ã          :End map
      â         :Deduplicate
        ®       :Map
         Í      :  Convert to decimal
          j     :  Is prime?
                :Implicit output of array sum

PHP, 145 byte

Saya telah menambahkan baris baru untuk keterbacaan:

function($n){for($b=base_convert;++$i<=strlen($s=$b($n,10,2));$r+=!$s[$i]&$k<=$j)
for($j=1;($k=$b(substr_replace($s,1,$i,0),2,10))%++$j;);echo$r;}

CJam, 34 byte

li2b_,),\f{_2$<@@>1\++}_&2fb{mp},,

Cobalah online

Versi pertama, akan diperbarui jika saya menemukan sesuatu yang lebih baik.

APL, 55

{+/{2=+/0=⍵|⍨⍳⍵}¨∪⍵{2⊥(⍵↑X),1,⍵↓X←⍺⊤⍨N⍴2}¨-1-⍳N←1+⌊2⍟⍵}

2 byte lebih pendek Dyalog versi spesifik:

{+/2=+/¨0=|⍨∘⍳⍨¨∪⍵{2⊥⍵(↑,(1∘,↓))⍺⊤⍨N⍴2}¨-1-⍳N←1+⌊2⍟⍵}

Matlab (120)

n=input('');a=dec2bin(n);g=arrayfun(@(x)bin2dec(cat(2,a(1:x),49,a(x+1:end))),1:log2(n));nnz(unique(g(find(isprime(g)))))

• Lebih banyak bermain golf sedang berlangsung ...

Brachylog , 17 byte

{ḃ~c₂{,1}ʰc~ḃṗ}ᶜ¹

Cobalah online!

Input melalui variabel input dan output melalui variabel output.

{             }ᶜ¹    Count every unique
             ṗ       prime number
           ~ḃ        the binary representation of which is
 ḃ                   the binary representation of the input
  ~c₂                partitioned into two (possibly empty) lists
     {  }ʰ           with the first list
      ,1             having a 1 appended
          c          and the two lists then being concatenated back into one.

Jelly , 13 byte

BLṬkj1ʋ€$QḄẒS

Cobalah online!

Python 2 , 103 byte

lambda n:sum(all(i%j for j in range(2,i))for i in{n%2**i+((n>>i)*2+1<<i)for i in range(len(bin(n))-2)})

Cobalah online!