Counting +1 primes

Question

Define that the natural number p is a +1 prime of the natural number n if p is a prime number and the standard binary representation (i.e., without leading zeroes) of p can be obtained by adding (i.e., prepending, appending or inserting) a single 1 to the standard binary representation of n.

For example, the binary representation of 17 is 10001₂. The distinct natural numbers that can be formed by adding a 1 to 10001₂ are 110001₂ or 49, 101001₂ or 41, 100101₂ or 37, and 100011₂ or 35.

Among these, 41 and 37 are prime numbers, so 17 has two +1 primes.

Task

Write a program or function that accepts a strictly positive integer n as input and prints or returns the number of distinct +1 primes of n.

Input and output must either be an integer, or its decimal or unary string representation.

Standard code-golf rules apply.

Test cases

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

\$\begingroup\$ Cool! If I had time tonight I would answer right now \$\endgroup\$
– anOKsquirrel
Commented Nov 7, 2015 at 1:09 — anOKsquirrel, Commented Nov 7, 2015 at 1:09

Downgoat · Accepted Answer · 2015-11-08 16:49:11Z

8

JavaScript ES6, 141 bytes 143 147 160

Saves 13 bytes, thanks to @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))

Similar method to my TeaScript answer, uses RegExp (you heard me right) to check for primes.

Ungolfed

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

edited Nov 8, 2015 at 16:49

answered Nov 7, 2015 at 3:26

Downgoat

29.1k6 gold badges84 silver badges155 bronze badges

\$\begingroup\$ I think you can shorten a bit checking prime like this: (p=(n,c)=>n%c!=0?c>=n-1?1:p(n,++c):0)('0b'+l,2) instead of !Array(+('0b'+l)+1).join(1).match(/^1?$|^(11+?)\1+$/) \$\endgroup\$
– Naouak
Commented Nov 7, 2015 at 19:19
\$\begingroup\$ @Naouak Awesome that saves 13 bytes! :) \$\endgroup\$
– Downgoat
Commented Nov 7, 2015 at 19:22

Add a comment |

isaacg · Accepted Answer · 2015-11-07 20:00:03Z

5

Pyth, 20 bytes

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.

answered Nov 7, 2015 at 20:00

isaacg

42.1k5 gold badges73 silver badges213 bronze badges

2

\$\begingroup\$ Huh, "deduplicate" is actually a word. \$\endgroup\$
– lirtosiast
Commented Nov 8, 2015 at 4:54

Add a comment |

Downgoat · Accepted Answer · 2015-11-07 17:53:09Z

4

TeaScript, 22 bytes

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

TeaScript is starting to look like APL... The special characters are converted to longer, commonly repeated sequences

Online interpreter be sure to check "Inputs are numbers."

Explanation && Ungolfed

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.

edited Nov 7, 2015 at 17:53

answered Nov 7, 2015 at 2:32

Downgoat

29.1k6 gold badges84 silver badges155 bronze badges

\$\begingroup\$ It's 31 bytes, by the way, using gedit on Xubuntu \$\endgroup\$
– Glen O
Commented Nov 7, 2015 at 17:41
1

\$\begingroup\$ It's 31 bytes with UTF-8 encoding, but 22 bytes with ISO-8859-1. \$\endgroup\$
– Dennis
Commented Nov 7, 2015 at 22:40

Add a comment |

Glen O · Accepted Answer · 2015-11-07 18:09:23Z

4

Julia, 55 52 bytes

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

k=2.^(0:endof(bin(n))) generates an array containing the powers of 2 from 1 to the highest power less than n. 2n+k-n%k then uses array operations to determine all of the possible "+1 numbers". ∪ (equivalent to union, which does the same thing as unique in this situation) removes the repeat values. Then sum(isprime,) counts the number of primes on the list.

edited Nov 7, 2015 at 18:09

answered Nov 7, 2015 at 15:26

Glen O

2,94814 silver badges13 bronze badges

Add a comment |

Martin Ender · Accepted Answer · 2015-12-04 15:23:01Z

CJam, 26 bytes

Not a winner, but it beats the existing CJam answers quite solidly and it's the first time I got to use the 0.6.5 command e\.

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

Test it here.

Explanation

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.

One thing worth noting is that we swap the bits at 0 and 1 before making the first copy, so we lose the original array with the 1 prepended to the front. However, the input is always positive, so the leading digit will always be one. That means after prepending another one, the digit list will always start with [1 1 ...] so the first swap will be a no-op in any case.

El'endia Starman · Accepted Answer · 2015-11-07 03:22:26Z

Minkolang 0.11, 54 52 bytes

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

Explanation

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.

\$\begingroup\$ I'm always excited to say another Minkolang version. \$\endgroup\$
– Conor O'Brien
Commented Nov 7, 2015 at 19:52 — Conor O'Brien, Commented Nov 7, 2015 at 19:52

LegionMammal978 · Accepted Answer · 2015-11-07 12:19:14Z

3

Mathematica, 87 bytes

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

answered Nov 7, 2015 at 12:19

LegionMammal978

18k4 gold badges25 silver badges57 bronze badges

Add a comment |

Alex A. · Accepted Answer · 2015-11-07 19:43:46Z

3

Julia, 110 108 104 87 bytes

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

This creates an unnamed function that accepts and integer and returns an integer. To call it, give it a name, e.g. f=n->....

Ungolfed:

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

Saved 17 bytes thanks to Glen O!

edited Nov 7, 2015 at 19:43

answered Nov 7, 2015 at 2:50

Alex A.

24.7k5 gold badges38 silver badges119 bronze badges

\$\begingroup\$ bin has to start with a 1, so you don't need to separately handle "1"b. And when i=length(b), you'll have b[i+1:end] equivalent to "", so no need for that entry (just need to handle b=bin(n) at some point). And sum will do the same thing as count for two fewer bytes. \$\endgroup\$
– Glen O
Commented Nov 7, 2015 at 14:54
\$\begingroup\$ Also, since you're going to use a range over the length of b anyway, might as well get it with a bit of a trick - b=bin(n)[s=1:end] and then for i=s for the comprehension. \$\endgroup\$
– Glen O
Commented Nov 7, 2015 at 17:44
\$\begingroup\$ You can also save another byte by using the fact that the first bit in bin should be 1, and you'll get this: n->sum(i->isprime(parse(Int,i,2)),(b=bin(n);unique([b[[1:i;1;i+1:end]]for i=1:endof(b)]))) - this brings the count down to 90 bytes. \$\endgroup\$
– Glen O
Commented Nov 7, 2015 at 17:52
\$\begingroup\$ In fact, take off one more byte, by replacing unique with union - it will do the same thing, if given only one array as input. Or better yet, ∪ instead of union. \$\endgroup\$
– Glen O
Commented Nov 7, 2015 at 18:01
\$\begingroup\$ @GlenO You're the master. Thank you, 先生! \$\endgroup\$
– Alex A.
Commented Nov 7, 2015 at 19:45

Add a comment |

anOKsquirrel · Accepted Answer · 2015-11-07 13:29:56Z

2

CJam, 58 bytes

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

This took me a day, and this was my 4th iteration.

answered Nov 7, 2015 at 13:29

anOKsquirrel

3913 silver badges10 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

Japt `-x`, 14 11 bytes

Æ¤iX1Ãâ ®Íj

Try it or run all test cases

Æ¤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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jun 21, 2019 at 16:43

Shaggy

43.5k4 gold badges36 silver badges94 bronze badges

Add a comment |

Blackhole · Accepted Answer · 2015-11-07 11:33:02Z

1

PHP, 145 bytes

I've added a newline for readability:

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

answered Nov 7, 2015 at 11:33

Blackhole

2,3822 gold badges13 silver badges17 bronze badges

Add a comment |

Reto Koradi · Accepted Answer · 2015-11-08 04:26:18Z

1

CJam, 34 bytes

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

Try it online

First version, will update if I come up with something better.

answered Nov 8, 2015 at 4:26

Reto Koradi

4,9311 gold badge13 silver badges19 bronze badges

Add a comment |

user46915 · Accepted Answer · 2015-11-08 06:26:00Z

1

APL, 55

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

2 bytes shorter Dyalog-specific version:

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

answered Nov 8, 2015 at 6:26

user46915

2211 silver badge3 bronze badges

Add a comment |

Abr001am · Accepted Answer · 2015-11-08 09:08:45Z

1

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

More golfing in progress ...

answered Nov 8, 2015 at 9:08

Abr001am

9307 silver badges17 bronze badges

Add a comment |

Unrelated String · Accepted Answer · 2019-06-21 08:07:05Z

Brachylog, 17 bytes

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

Try it online!

Input through the input variable and output through the output variable.

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

Erik the Outgolfer · Accepted Answer · 2019-06-22 17:58:08Z

1

Jelly, 13 bytes

BLṬkj1ʋ€$QḄẒS

Try it online!

answered Jun 22, 2019 at 17:58

Erik the Outgolfer

40.6k5 gold badges45 silver badges122 bronze badges

Add a comment |

Razetime · Accepted Answer · 2020-11-07 09:04:39Z

1

Husk, 20 bytes

←#ṗumȯḋJ1`Cḋ¹oSze↔ŀḋ

Try it online!

Barely got away with a single byte.

Husk, 21 bytes

#oṗḋumJ1§z§e↑↓oΘŀo¢;ḋ

Try it online!

There's probably a much shorter way to do this.

edited Nov 7, 2020 at 9:04

answered Nov 2, 2020 at 12:02

Razetime

27.4k3 gold badges29 silver badges72 bronze badges

\$\begingroup\$ Down to 18 bytes now... \$\endgroup\$
– Dominic van Essen
Commented Nov 7, 2020 at 20:13

Add a comment |

Dominic van Essen · Accepted Answer · 2020-11-07 21:09:19Z

Husk, 18 17 bytes

#oṗḋużoJ1eḣḋ¹mtṫḋ

Try it online!

Different approach to Razetime's Husk answer, saving 2 3 bytes.

How?

#oṗḋużoJ1eḣḋ¹mtṫḋ
#o                      # how many
  ṗ                     # prime numbers
   ḋ                    # among numbers formed by binary digits of
    u                   # unique elements of
     żo                 # zip together 2 lists of lists,
       J1e              # joining each pair with the digit '1'
          ḣḋ¹           # list 1:
          ḣ             # all prefixes of 
           ḋ¹           # binary digits of input
             mtṫḋ       # list 2:
             mt         # remove first element from
               ṫ        # all suffixes of
                ḋ       # binary digits of input

\$\begingroup\$ Very nicely done. \$\endgroup\$
– Razetime
Commented Nov 8, 2020 at 3:48 — Razetime, Commented Nov 8, 2020 at 3:48

Erik the Outgolfer · Accepted Answer · 2019-06-22 19:03:41Z

0

Python 2, 103 bytes

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

Try it online!

answered Jun 22, 2019 at 19:03

Erik the Outgolfer

40.6k5 gold badges45 silver badges122 bronze badges

Add a comment |

lyxal · Accepted Answer · 2023-12-22 03:09:40Z

0

Vyxal 3 `s`, 11 bytes

bƛ?bm1ỊB}uṄ

Try it Online! (link is to literate version)

Explained

'uniquify( to-binary map< 
  (input to-binary) 'insert (ctx-m 1)
  from-binary}
)
  
prime?

answered Dec 22, 2023 at 3:09

lyxal

34.3k2 gold badges64 silver badges141 bronze badges

Add a comment |

Stack Exchange Network

Counting +1 primes

Task

Test cases

20 Answers 20

JavaScript ES6, 141 bytes 143 147 160

Ungolfed

Pyth, 20 bytes

TeaScript, 22 bytes

Explanation && Ungolfed

Julia, 55 52 bytes

CJam, 26 bytes

Explanation

Minkolang 0.11, 54 52 bytes

Explanation

Mathematica, 87 bytes

Julia, 110 108 104 87 bytes

CJam, 58 bytes

Japt `-x`, 14 11 bytes

PHP, 145 bytes

CJam, 34 bytes

APL, 55

Matlab (120)

Brachylog, 17 bytes

Jelly, 13 bytes

Husk, 20 bytes

Husk, 21 bytes

Husk, 18 17 bytes

Python 2, 103 bytes

Vyxal 3 `s`, 11 bytes

Explained

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
primes
binary
or ask your own question.

Hot Network Questions

Counting +1 primes

Task

Test cases

20 Answers 20

JavaScript ES6, 141 bytes 143 147 160

Ungolfed

Pyth, 20 bytes

TeaScript, 22 bytes

Explanation && Ungolfed

Julia, 55 52 bytes

CJam, 26 bytes

Explanation

Minkolang 0.11, 54 52 bytes

Explanation

Mathematica, 87 bytes

Julia, 110 108 104 87 bytes

CJam, 58 bytes

Japt -x, 14 11 bytes

PHP, 145 bytes

CJam, 34 bytes

APL, 55

Matlab (120)

Brachylog, 17 bytes

Jelly, 13 bytes

Husk, 20 bytes

Husk, 21 bytes

Husk, 18 17 bytes

Python 2, 103 bytes

Vyxal 3 s, 11 bytes

Explained

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfmathprimesbinary or ask your own question.

Related

Hot Network Questions

Japt `-x`, 14 11 bytes

Vyxal 3 `s`, 11 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
math
primes
binary
or ask your own question.