23
\$\begingroup\$

Task

Find all the non-negative integers up to and including a given non-zero positive integer n, that are prime and the count of 1's and 0's in their binary representation (having no leading zeroes) are prime too.

Here are the first five such primes,

17, 19, 37, 41, 79

10001, 10011, 100101, 101001, 1001111

Clarifications and rules

  • Default I/O methods are accepted.
  • The answer can be a program or a function.
  • If there are no such primes then output garbage or nothing.
  • Standard loopholes are forbidden.
  • 2 3 5 7 did not make it to the list because in their binary representation number of occurrences of 0's and 1's are not prime. Consider 7whose binary representation is 111, here 0 occurs zero times and zero is not prime.
  • Built-ins are allowed.

  • The shortest code in bytes wins!

Test cases

10
[]

100
[17, 19, 37, 41, 79]

150
[17, 19, 37, 41, 79, 103, 107, 109, 131, 137]

/* Configuration */

var QUESTION_ID = 107050; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 47650; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();
    
    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
  • 1
    \$\begingroup\$ You ask for all primes under a given n, but you also say inclusive. Which do you mean? \$\endgroup\$ – Riley Jan 16 '17 at 21:02
  • \$\begingroup\$ @Riley What I mean is ...all the numbers from 1....n. I do not know how to rephrase it in a simple way. \$\endgroup\$ – Gurupad Mamadapur Jan 16 '17 at 21:12
  • 6
    \$\begingroup\$ OEIS A144214 \$\endgroup\$ – mbomb007 Jan 16 '17 at 21:16
  • 3
    \$\begingroup\$ @mbomb007 Clearly, for any total ordering of integer sequences, the smallest uninteresting integer sequence would be itself interesting, and thus worthy of inclusion in OEIS. Ergo, OEIS contains all integer sequences, of any interest real or imagined :-) \$\endgroup\$ – Iwillnotexist Idonotexist Jan 16 '17 at 21:44
  • 9
    \$\begingroup\$ I'm wondering whether Mathematica contains more builtins than OEIS has sequences... \$\endgroup\$ – Neil Jan 17 '17 at 0:48

26 Answers 26

5
\$\begingroup\$

Jelly, 14 13 bytes

RBċþd`ÆPPTfÆR

Try it online!

How it works

RBċþd`ÆPPTfÆR  Main link. Argument: n

R              Range; yield [1, ..., n].
 B             Binary; convert each integer to base 2.
    d`         Divmod self; yield [n : n, n % n], i.e., [1, 0].
  ċþ           Count table; count the occurrences of 1 and 0 in each binary
               representation, yielding a pair of lists of length n.
      ÆP       Test each count for primality.
        P      Product; multiply the corresponding Booleans.
         T     Truth; get all indices of 1, yielding the list of integers in
               [1, ..., n] that have a prime amount of 0's and 1's.
           ÆR  Prime range; yield all primes in [1, ..., n].
          f    Filter; intersect the lists.
\$\endgroup\$
  • 2
    \$\begingroup\$ That d`​ trick is something else... \$\endgroup\$ – ETHproductions Jan 17 '17 at 18:20
10
\$\begingroup\$

Python 2, 106 102 100 bytes

k=m=1;p={0}
exec"p^={m%k*k,0};c=bin(k).count\nif{k,c('1'),c('0')-1}<p:print k\nm*=k*k;k+=1;"*input()

Try it online!

Background

To identify primes, we use a corollary of Wilson's theorem:

corollary of Wilson's theorem

How it works

We start by initializing k and m as 1 and p as the set {0}. Note that m = 1 = 0!² = (k - 1)!². Immediately afterwards, the following code is executed n times, where n is the integer read from standard input.

p^={m%k*k,0};c=bin(k).count
if{k,c('1'),c('0')-1}<p:print k
m*=k*k;k+=1

By the corollary, m % k will be 1 if k is prime and 0 otherwise. Thus, {m%k*k,0} will return the set {k, 0} if k is prime and the set {0} otherwise.

If (and only if) k is prime, since p cannot contain k at this point, the in-place symmetric difference p^={m%k*k,0} will add k to the set p. Also, p will contain 0 after the update if and only if it does not contain 0 before, so 0 ∊ p if and only if k is even.

On the same line, we define a function c via c=bin(k).count, which will count the occurrences of its argument in k's binary representation.

The second line produces the actual output. {k,c('1'),c('0')-1} returns the set that consists of k itself, the number of set bits in k, and the number of unset bits in k. Since the output of bin(k) begins with 0b, we have to decrement c('0') to account for the leading 0.

If all of them are prime, they will all belong to p, which by now contains all prime numbers up to k (and potentially 0). If k is a Mersenne number (i.e., if it has only set bits), c('0')-1 will yield 0. Since Mersenne numbers are odd, p will not contain 0, so the condition will fail.

After (potentially) printing k, we multiply m by . Since m = (k-1)!² before the update, m = k!² after it. After incrementing k, the relation m = (k-1)!² holds again and we're ready for the next iteration.

\$\endgroup\$
9
\$\begingroup\$

Mathematica, 80 68 54 bytes

Select[p=PrimeQ;Range@#,p@#&&And@@p/@#~DigitCount~2&]&

Explanation

Select[p=PrimeQ;Range@#,p@#&&And@@p/@#~DigitCount~2&]&

       p=PrimeQ                                        (* Store prime check func. in p *)
Select[                                             ]  (* Select *)
                Range@#                                (* from a list {1..n} *)
                        p@#                            (* numbers that are prime *)
                           &&                          (* And *)
                                     #~DigitCount~2    (* whose digit counts in binary *)
                             And@@p/@                  (* are prime as well *)
\$\endgroup\$
8
\$\begingroup\$

JavaScript (ES6), 123 118 115 111 104 96 bytes

Saved 4 bytes thanks to @Arnauld

G=n=>n?G(n>>1,++a[n%2]):a.some(n=>(P=x=>n%--x?P(x):x)(n)-1)
F=n=>F(n-1,G(n,a=[0,0,n])||alert(n))

A combination of three typical recursive functions. Alerts the sequence in reverse order and terminates on a "too much recursion" error.

Test snippet

(modified to output to the page)

alert = s => O.textContent += s + "\n"

G=n=>n?G(n>>1,++a[n%2]):a.some(n=>(P=x=>n%--x?P(x):x)(n)-1)
F=n=>F(n-1,G(n,a=[0,0,n])||alert(n))

F(1000)
<pre id=O></pre>

The main function can return an array for 104 bytes:

G=n=>n?G(n>>1,++a[n%2]):a.some(n=>(P=x=>n%--x?P(x):x)(n)-1)
F=n=>n?F(n-1).concat(G(n,a=[0,0,n])?[]:n):[]

It can also be non-recursive at the cost of another byte:

G=n=>n?G(n>>1,++a[n%2]):a.some(n=>(P=x=>n%--x?P(x):x)(n)-1)
n=>[for(_ of Array(n))if(!G(--n,a=[0,0,n]))n]

Here's the one I started with: (Saved 6 bytes thanks to @Arnauld)

P=(n,x=n)=>n>1&--x<2||n%x&&P(n,x)
G=n=>n?G(n>>1,o+=n%2,t++):P(o)&P(t-o)
F=n=>n?F(n-1).concat(P(n)&G(n,o=t=0)?n:[]):[]

I tried golfing this further and managed to do it in 104 bytes—then realized I had already found that solution (it's at the bottom of the answer). Don't you hate it when that happens? :P

A non-recursive attempt at the main function (again, same byte count):

n=>[for(i of Array(n))if(P(--n)&G(n,o=t=0))n]

This one takes the easy route of counting how many 0's and 1's are in the binary representation:

F=n=>n?F(n-1).concat([n,(G=x=>n.toString(2).split(x).length-1)(0),G(1)].some(n=>(P=x=>n%--x?P(x):x)(n)-1)?[]:n):[]

Same thing with an array comprehension:

n=>[for(_ of Array(n))if(![--n,(G=x=>n.toString(2).split(x).length-1)(0),G(1)].some(n=>(P=x=>n%--x?P(x):x)(n)-1))n]

This one takes a slightly harder route to do the same thing:

F=n=>n?F(n-1).concat([n,(G=(x,w=n)=>w&&G(x,w>>1)+(w%2==x))(0),G(1)].some(n=>(P=x=>n%--x?P(x):x)(n)-1)?[]:n):[]

And this one takes yet another related route that's as short as the original:

F=n=>n?F(n-1).concat([n,o=(G=x=>x&&x%2+G(n>>++t))(n,t=0),t-o].some(n=>(P=x=>n%--x?P(x):x)(n)-1)?[]:n):[]

Again, you can golf 8 bytes by making it alert the sequence in reverse order:

F=n=>F(n-1,[n,o=(G=x=>x&&x%2+G(n>>++t))(n,t=0),t-o].some(n=>(P=x=>n%--x?P(x):x)(n)-1)||alert(n))
\$\endgroup\$
  • \$\begingroup\$ You don't really need to recursively pass a. Just initialize it in the initial call to G. (That should save 4 bytes.) \$\endgroup\$ – Arnauld Jan 16 '17 at 21:39
  • \$\begingroup\$ @Arnauld Oh yeah, thanks! This is fun :-) \$\endgroup\$ – ETHproductions Jan 16 '17 at 21:42
  • 1
    \$\begingroup\$ Wow this has dropped a lot. Nice work \$\endgroup\$ – George Reith Jan 17 '17 at 18:06
6
\$\begingroup\$

Jelly, 17 16 bytes

BĠL€µ;LÆPẠ
ÆRÇÐf

Try it online!

How?

BĠL€µ;LÆPẠ - Link 1, hasPrimeBits: n  e.g. 7         or 13
B          - convert to binary        e.g. [1,1,1]  or [1,1,0,1]
 Ġ         - group indices            e.g. [1,2,3]  or [3,[1,2,4]]
  L€       - length of €ach           e.g. 3          or [1,3]
    µ      - monadic chain separation
     ;L    - concatenate length       e.g. [3,1]      or [1,3,2]
           -     this caters for the edge case of Mersenne primes (like 7), which have
           -     no zero bits, the length will be 1, which is not prime.
       ÆP  - isPrime?                 e.g. [1,0]      or [0,1,1]
         Ạ - All?                     e.g. 0          or 0

ÆRÇÐf - Main link: N
ÆR    - prime range (primes up to and including N)
   Ðf - filter keep those satisfying
  Ç   - last link (1) as a monad
\$\endgroup\$
  • 1
    \$\begingroup\$ Ah thanks, I see you changed that, that'll save a byte. \$\endgroup\$ – Jonathan Allan Jan 16 '17 at 20:52
  • 1
    \$\begingroup\$ You've got the alphabet going, there. ẠBÇЀfĠ... \$\endgroup\$ – mbomb007 Jan 16 '17 at 22:04
  • 2
    \$\begingroup\$ @mbomb007 Yeah, the LƵ;P bit always confuses me. \$\endgroup\$ – Jonathan Allan Jan 16 '17 at 22:16
6
\$\begingroup\$

05AB1E, 14 bytes

ƒNpNbSD_‚OpP&–

Try it online!

Explanation

ƒ               # for N in [0 ... input]
 Np             # push N is prime
   Nb           # push N converted to binary
     S          # split into individual digits
      D_        # push an inverted copy
        ‚       # pair the 2 binary lists
         O      # sum them
          p     # elementwise check for primality
           P    # product of list
            &   # and with the primality of N
             –  # if true, print N
\$\endgroup\$
  • \$\begingroup\$ I still can't find a use for , this challenge seemed good for it, but is longer: FNb{.¡€gpONp+3QiN}}) \$\endgroup\$ – Magic Octopus Urn Jan 17 '17 at 19:35
  • \$\begingroup\$ @carusocomputing: I had a similar solution I considered as well, but it also ended up slightly longer than this. \$\endgroup\$ – Emigna Jan 17 '17 at 22:27
4
\$\begingroup\$

05AB1E, 17 15 bytes

LDpÏvybSD_)OpP—

Uses the CP-1252 encoding. Try it online!

\$\endgroup\$
  • \$\begingroup\$ LDpÏvybSD_)OpP— for 15 bytes should work. \$\endgroup\$ – Emigna Jan 16 '17 at 21:31
  • \$\begingroup\$ @Emigna That is really clever! Thanks :). \$\endgroup\$ – Adnan Jan 16 '17 at 21:36
4
\$\begingroup\$

MATL, 16 15 bytes

:"@tB!t~hshZp?@

Try it online!

:         % Input n (implicit). Push range [1 2 ... n]
"         % For each k in [1 2 ... n]
  @       %   Push k
  tB!     %   Duplicate. Binary expansion as an m×1 vector
  t~      %   Duplicate. Negate
  hs      %   Concatenate horizontally into an m×2 matrix. Sum of each column.
          %   This gives a 1×2 vector. However, for k==1 this gives the sum of
          %   the original 1×2 matrix (m==1). But fortunately it doesn't matter
          %   because 1 is not a prime anyway
  h       %   Concatenate horizontally into a 1×3 row vector
  Zp      %   Isprime function applied on each of those three numbers
  ?       %   If all gave true
    @     %     Push k
          %   End (implicit)
          % End (implicit)
          % Display (implicit)
\$\endgroup\$
4
\$\begingroup\$

Perl, 101 bytes

99 bytes of code + -nl flags.

$r=q/^1?$|^(11+)\1+$/;for$@(2..$_){$_=sprintf"%b",$@;print$@if(1x$@)!~$r&y/01/1/dr!~$r&s/0//gr!~$r}

To run it:

perl -lne '$r=q/^1?$|^(11+)\1+$/;for$@(2..$_){$_=sprintf"%b",$@;print$@if(1x$@)!~$r&y/01/1/dr!~$r&s/0//gr!~$r}' <<< 150

Some short explanations
$r holds the classical prime checking regex (q/^1?$|^(11+)\1+$/).
For all numbers between 2 and the input,
(1x$@)!~$r checks if the number is prime,
y/01/1/dr!~$r checks if the number of 0 in the binary representation is prime,
s/0//gr!~$r checks if the number 1 in the binary representation is prime.
(if the 3 conditions are met, print$@ prints it).

\$\endgroup\$
  • \$\begingroup\$ Thanks for the explanation. Quite amazing what you can do with what is basically regex and some logic :) \$\endgroup\$ – Emigna Jan 16 '17 at 21:41
  • \$\begingroup\$ @Emigna Thanks! The explanations aren't very detailed (I'm having a hard time writing longer explanations), but it seems it was enough for you :) (I still believe the code is slightly too long, but I don't see how to get it shorter, so here it is) \$\endgroup\$ – Dada Jan 16 '17 at 21:46
  • 1
    \$\begingroup\$ As someone who doesn't know Perl I appreciate every explanation I can get. It won't help me make a Perl program but I understand some of the reasoning behind the method employed, which is always interesting. \$\endgroup\$ – Emigna Jan 16 '17 at 21:48
3
\$\begingroup\$

Python, 129 125 123 bytes

If only zero were prime...

p=lambda n:all(n%m for m in range(2,n))*n>1
lambda n:[i for i in range(n+1)if p(i)*all(p(bin(i)[2:].count(x))for x in'01')]

Try it online

Function p is the prime-checking function, which has >0 at the end so that it works for zero as well, which would otherwise return -1. The anonymous lambda is the lambda that checks all the conditions required.


Here's a slightly different method using a set comprehension. The result will be a set. (124 bytes):

p=lambda n:all(n%m for m in range(2,n))*n>1
lambda n:{i*p(i)*all(p(bin(i)[2:].count(x))for x in'01')for i in range(n+1)}-{0}
\$\endgroup\$
3
\$\begingroup\$

Perl 6, 65 bytes

{grep {all($^a,|map {+$a.base(2).comb(~$_)},0,1).is-prime},0..$_}

Try it

Expanded:

{           # bare block lambda with implicit parameter 「$_」

  grep      # find all of the values where

  {         # lambda with placeholder parameter 「$a」

    all(    # all junction ( treat multiple values as a single value )

      $^a,  # declare parameter to block

      |\    # slip the following list into the outer list

      # get the count of 0's and 1's in the binary representation
      map

      {             # bare block lambda with implicit parameter 「$_」

        +           # turn to numeric ( count the values in the list )
        $a          # the outer parameter
        .base(2)    # in base 2
        .comb(~$_)  # find the characters that are the same as
      },0,1         # 0 or 1

    # ask if $a, count of 0's, count of 1's are all prime
    ).is-prime

  },

  0 .. $_ # Range from 0 to the input inclusive

}
\$\endgroup\$
3
\$\begingroup\$

Octave, 73 bytes

@(n)(p=primes(n))(all(isprime([s=sum(dec2bin(p)'-48);fix(log2(p))+1-s])))

Try It Online!

@(n)
    (p=primes(n))                           generate prime numbers
        (all(                               from them select those that
            isprime(                        are prime both
                [s=sum(dec2bin(p)'-48);     sum of 1s
                fix(log2(p))+1-s])))        and sum of 0s
\$\endgroup\$
2
\$\begingroup\$

CJam, 26 27 bytes

ri){mp},{2b_1-,mp\0-,mp&},p

Straightforward algorithm, will golf further.

EDIT: Forgot n was inclusive.

Try it online!

For fun, this is very similar and also 27 bytes:

ri){_mp\2b_1-,mp\0-,mp&&},p

Explanation

ri                          e# Take an int as input
  ){mp},                    e# Take the range up and including to the input, 
                            e#   including only prime numbers
       {                    e# For each prime...
        2b_                 e# Convert it to binary and copy it
           1-,mp            e# Take the top binary number, remove 1's, check if the length 
                            e#   is prime
                \           e# Swap top elements
                 0-,mp      e# Do the same but remove 0's
                      &     e# And
                       },   e# Filter out primes for which the above block was false
                         p  e# Print nicely
\$\endgroup\$
2
\$\begingroup\$

Jelly, 14 bytes

BċÆPðÐf
ÆRç0ç1

Try it online!

Unfortunately, I could only tie with @Dennis, but the algorithm seems to be somewhat different so I'm posting this anyway.

Explanation

Helper function (deletes list elements that don't have a prime number of occurrences of a given bit):

BċÆPðÐf
     Ðf   Filter {the first argument}, looking for truthy returns from
    ð     the preceding code, which takes two arguments:
B         Convert {the element being checked} to binary
 ċ        Count the number of occurrences of {the second argument}
  ÆP      Return true if prime, false if not prime

Main program:

ÆRç0ç1
ÆR        Generate all primes from 2 to the input
  ç0      Call the subroutine to require a prime 0 count
    ç1    Call the subroutine to require a prime 1 count
\$\endgroup\$
2
\$\begingroup\$

Haxe, 169 171 bytes

function f(n,?p)return[for(j in(p=[for(i in 0...++n)i<2?0:i]))if(j>0){var x=j*2,y=0,z=0,k=j;while(k<n)p[k+=j]=0;while((x>>=1)>0)x&1>0?y++:z++;p[y]<1||p[z]<1?continue:j;}];

Nothing crazy. Essentially a modified sieve of Eratosthenes that evaluates the primality of the 0 / 1 count in the same iteration as crossing out higher non-primes. With some whitespace:

function f(n, ?p)
  return [ for (j in (p = [ for(i in 0...++n) i < 2 ? 0 : i ]))
    if (j > 0){
      var x = j * 2, y = 0, z = 0, k = j;
      while (k < n)
        p[k += j] = 0;
      while((x >>= 1) > 0)
        x & 1 > 0 ? y++ : z++;
      p[y] < 1 || p[z] < 1 ? continue : j;
    }
  ];

But today I learned I could put continue in a ternary operator and Haxe doesn't even mind.

Edit: +2 because n is an inclusive upper bound!

\$\endgroup\$
  • \$\begingroup\$ Hey, the n is inclusive. \$\endgroup\$ – Gurupad Mamadapur Jan 17 '17 at 15:39
  • \$\begingroup\$ @GurupadMamadapur You're right, fixed! \$\endgroup\$ – Aurel Bílý Jan 17 '17 at 19:43
2
\$\begingroup\$

Bash + GNU utilities, 129 126 123 114 111 109 bytes

seq '-fp()([ `factor|wc -w` = 2 ]);g()(dc -e2o${n}n|tr -cd $1|wc -c|p);n=%.f;p<<<$n&&g 0&&g 1&&echo $n' $1|sh

Try it online!

Noticed the comment that the output doesn't have to be in increasing order -- shaved off 3 bytes by counting down instead of counting up.

Replaced grep with wc to save 3 additional bytes.

Eliminated a variable (9 more bytes off).

Changed the way factor is used -- 3 more bytes.

Made it golfier with seq (2 bytes).

\$\endgroup\$
2
\$\begingroup\$

Python, 172 170 168 159 154 133 130 bytes

p=lambda n:[i for i in range(1,n)if n%i==0]==[1]
lambda n:[i for i in range(n+1)if p(i)*all(p(bin(i)[2:].count(x))for x in'10')]

Usage: Call the anonymous lambda function
Method p checks whether a number is prime


Saved 2+2+9=13 bytes thanks to Gurupad Mamadapur
Saved 5 bytes thanks to mbomb007

\$\endgroup\$
  • 1
    \$\begingroup\$ You can save 2 more by using this v - def v(n):a=bin(n)[2:];return p(n)and(p(a.count('1'))and p(a.count('0'))) \$\endgroup\$ – Gurupad Mamadapur Jan 16 '17 at 21:29
  • 1
    \$\begingroup\$ A much shorter one - v=lambda a:p(a)and all(p(bin(a)[2:].count(x))for x in['1','0']) \$\endgroup\$ – Gurupad Mamadapur Jan 16 '17 at 21:35
  • 2
    \$\begingroup\$ Strings are iterable. So you can use for x in'01'. \$\endgroup\$ – mbomb007 Jan 16 '17 at 21:47
1
\$\begingroup\$

Pyke, 21 bytes

S#j_PI\0[jb2R/_P)I\1[

Try it here!

S#j                   - for j in filter(range(1, input+1))
   _PI                -  if is_prime(j):
        [jb2R/_P)     -   function_[(a) = V
         jb2          -      base_2(j)
            R/        -     ^.count(a)
      \0         I    -   if function_[("0"):
                  \1[ -    function_[("1")
\$\endgroup\$
1
\$\begingroup\$

Groovy, 120 bytes

p={x->(2..<x).every{x%it!=0}&x>1|x==2}
{x->(1..x).findAll({y->p(y)&'10'.every{p(Integer.toBinaryString(y).count(it))}})}

This is an unnamed closure.

Try it here!

\$\endgroup\$
1
\$\begingroup\$

Pyth, 18 bytes

f.APM_M+T/LSjT2U2S

Try it online here.

\$\endgroup\$
  • 1
    \$\begingroup\$ @GurupadMamadapur srry changing U to S \$\endgroup\$ – Maltysen Jan 16 '17 at 21:39
  • \$\begingroup\$ @GurupadMamadapur done \$\endgroup\$ – Maltysen Jan 16 '17 at 21:39
  • \$\begingroup\$ @GurupadMamadapur eS \$\endgroup\$ – Maltysen Jan 16 '17 at 21:58
  • 1
    \$\begingroup\$ @GurupadMamadapur cuz we're out of chars :P Pyth is ascii only. \$\endgroup\$ – Maltysen Jan 16 '17 at 22:01
1
\$\begingroup\$

Python 3, 97 bytes

def f(n,k=2,m=1,p={0}):f(n-1,k+1,m*k*k,p^{m%k*k,{*map(bin(m%k%n*k)[2:].count,'01')}<p==print(k)})

This is the same algorithm as in my Python 2 answer, but the implementation is quite different. The function prints to STDOUT and terminates with an error.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 110 bytes

B=n=>n?B(n>>1,v[n%2]++):v.every(n=>(P=i=>n%--i?P(i):1==i)(n))
F=(n,a=[])=>n?F(n-1,B(n,v=[0,0,n])?[n,...a]:a):a

B=n=>n?B(n>>1,v,v[n%2]++):v.every(n=>(P=i=>n%--i?P(i):1==i)(n))
F=(n,a=[])=>n?F(n-1,B(n,v=[0,0,n])?[n,...a]:a):a

const update = () => {
  console.clear();
  console.log(F(input.value))
}

input.oninput = update;
update();
<input id="input" type="number" min="1" value="100" />

\$\endgroup\$
  • \$\begingroup\$ That primality test function is... just amazing :-) Did you create it yourself? \$\endgroup\$ – ETHproductions Jan 17 '17 at 2:47
  • \$\begingroup\$ @ETHproductions You've seen it before codegolf.stackexchange.com/a/91309/11182 modified from here. I also borrowed your 1 and 0 counting code (whooped anything I could come up with) but alas I couldn't beat your byte count. \$\endgroup\$ – George Reith Jan 17 '17 at 3:36
  • \$\begingroup\$ @ETHproductions Good catch thanks! Was an artefact of a previous version \$\endgroup\$ – George Reith Jan 17 '17 at 18:04
1
\$\begingroup\$

MATLAB, 50 bytes

@(n)all(isprime([n,sum(de2bi(n)),sum(~de2bi(n))]))
\$\endgroup\$
1
\$\begingroup\$

Haxe, 158 147 bytes

function p(n,x=1)return n%++x<1||n<2?x==n:p(n,x);function f(n){var q=n,t=0,o=0;while(q>0){t++;o+=q%2;q>>=1;}p(n)&&p(o)&&p(t-o)?trace(n):0;f(n-1);};

Outputs to STDOUT and terminates on a "too much recursion" error; call with e.g. f(1000);. You can use a while loop with no error for 156 bytes:

function p(n,x=1)return n%++x<1||n<2?x==n:p(n,x);function f(n){while(n>0){var q=n,t=0,o=0;while(q>0){t++;o+=q%2;q>>=1;}p(n)&&p(o)&&p(t-o)?trace(n):0;n--;}};

Using a range turned out three bytes longer:

function p(n,x=1)return n%++x<1||n<2?x==n:p(n,x);function f(n){for(i in 0...n+1){var q=i,t=0,o=0;while(q>0){t++;o+=q%2;q>>=1;}p(i)&&p(o)&&p(t-o)?trace(i):0;}};

Test it online!

\$\endgroup\$
1
\$\begingroup\$

Rust, 147 bytes

fn f(x:u32){let p=|n|n>1&&(2..n).all(|x|n%x!=0);for n in 9..x+1{if p(n)&&p(n.count_ones())&&p(n.count_zeros()-n.leading_zeros()){print!("{} ",n)}}}

playground link

The count_ones, count_zeros, and leading_zeros methods came in handy.

Formatted version

fn f(x: u32) {
    // primality test closure using trial division
    let p = |n| n > 1 && (2..n).all(|x| n % x != 0);

    for n in 9..x + 1 {
        if p(n) && p(n.count_ones()) && p(n.count_zeros() - n.leading_zeros()) {
            print!("{} ", n)
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 50 bytes

{grep {($_&+.base(2).comb(~0&~1)).is-prime},0..$_}

Variation of b2gills' answer, using the & junction operator to great effect.

Try it online!

How it works

{                                                }  # Lambda
                                            0..$_   # Range from 0 to the lambda argument.
 grep {                                   },        # Filter values satisfying:
       ($_                      ).is-prime          #  a) The Number itself is prime.
       (   +.base(2).comb(~0   )).is-prime          #  b) The count of 0's is prime.
       (   +.base(2).comb(   ~1)).is-prime          #  c) The count of 1's is prime.
          &                 &                       # Junction magic! :)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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