Zdefiniuj, że liczba naturalna p jest liczbą pierwszą +1 liczby naturalnej n, jeżeli p jest liczbą pierwszą, a standardową reprezentację binarną (tj. Bez zer wiodących) p można uzyskać poprzez dodanie (tj. Dodawanie, dodawanie lub wstawianie) pojedynczy 1 do standardowej reprezentacji binarnej n .

Na przykład binarna reprezentacja 17 to 10001 ₂ . Odrębne liczby naturalne, które można utworzyć, dodając 1 do 10001 _2, to 110001 ₂ lub 49 , 101001 ₂ lub 41 , 100101 ₂ lub 37 oraz 100011 ₂ lub 35 .

Wśród nich 41 i 37 to liczby pierwsze, więc 17 ma dwie liczby pierwsze +1 .

Zadanie

Napisać program lub funkcję, która przyjmuje ściśle dodatnią liczbę całkowitą N wejściu i nadrukami lub zwraca liczby odmiennych +1 bodźce o n .

Dane wejściowe i wyjściowe muszą być albo liczbą całkowitą, albo jej dziesiętną lub jedną reprezentacją ciągu.

Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

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 bajtów

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

Pakiet testowy

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 bajtów 143 147 160

Oszczędza 13 bajtów dzięki @Naouak

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

Metoda podobna do mojej odpowiedzi TeaScript, używa RegExp (dobrze mnie słyszałeś) do sprawdzania liczb pierwszych.

Nie golfił

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 bajty

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

Wyjaśnienie

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 bajty

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

TeaScript zaczyna wyglądać jak APL ... Znaki specjalne są konwertowane na dłuższe, często powtarzane sekwencje

Tłumacz online powinien zaznaczyć „Dane wejściowe to liczby”.

Wyjaśnienie i nieugolfowany

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 bajtów

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

k=2.^(0:endof(bin(n)))generuje tablicę zawierającą moce 2 od 1 do najwyższej mocy mniejszej niż n. 2n+k-n%knastępnie używa operacji tablicowych, aby określić wszystkie możliwe „liczby +1”. ∪(odpowiednik union, który robi to samo, co uniquew tej sytuacji) usuwa powtarzane wartości. Następnie sum(isprime,)liczy liczbę liczb pierwszych na liście.

CJam, 26 bajtów

Nie jest zwycięzcą, ale pokonuje istniejące odpowiedzi CJam dość solidnie i po raz pierwszy mogę użyć polecenia 0.6.5 e\.

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

Sprawdź to tutaj.

Wyjaśnienie

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.

Warto zwrócić uwagę na to, że zamieniamy bity przed 0i 1przed zrobieniem pierwszej kopii, więc tracimy oryginalną tablicę z 1dodanym do przodu. Jednak dane wejściowe są zawsze dodatnie, więc cyfra wiodąca zawsze będzie jedna. Oznacza to, że po przygotowaniu kolejnego lista cyfr zawsze zaczyna się od, [1 1 ...]więc pierwsza zamiana w żadnym wypadku nie będzie działać.

Mathematica, 87 bajtów

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

Julia, 110 108 104 87 bajtów

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

Spowoduje to utworzenie nienazwanej funkcji, która przyjmuje wartość całkowitą i zwraca liczbę całkowitą. Aby to nazwać, nadaj mu nazwę, np f=n->....

Nie golfowany:

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

Oszczędność 17 bajtów dzięki Glen O!

CJam, 58 bajtów

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

Zajęło mi to dzień i to była moja czwarta iteracja.

Japt -x , 14 11 bajtów

ƤiX1Ãâ ®Íj

Wypróbuj lub uruchom wszystkie przypadki testowe

Ƥ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 bajtów

Dodałem nowy wiersz dla czytelności:

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 bajty

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

Wypróbuj online

Pierwsza wersja zostanie zaktualizowana, jeśli wymyślę coś lepszego.

APL, 55

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

2 bajty krótsza wersja specyficzna dla Dyalog:

{+/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)))))

• Więcej golfa w toku ...

Brachylog , 17 bajtów

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

Wypróbuj online!

Wejście przez zmienną wejściową i wyjście przez zmienną wyjściową.

{             }ᶜ¹    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.

Galaretka , 13 bajtów

BLṬkj1ʋ€$QḄẒS

Wypróbuj online!

Python 2 , 103 bajty

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

Wypróbuj online!