Most of us know...

that all primes p>3 are of the form But, how many are the Plus Primes (6n+1) and how many are the Minus Primes (6n-1) in a certain range?

The Challenge

Given an integer k>5, count how many primes<=k are PlusPrimes and how many are MinusPrimes.

Examples

for k=100 we have
[5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89] 12 MinusPrimes
and
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97] 11 PlusPrimes

for k=149 we have
[5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149]
18 MinusPrimes
and
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139]
15 PlusPrimes

Rules

Your code must output 2 integers: one for the MinusPrimes and one for the PlusPrimes in any order you like (please specify which is which).
This is : shortest answer in bytes wins!

Test Cases

Input -> Output [MinusPrimes,PlusPrimes]

6->[1,0]
7->[1,1]
86->[11,10]
986->[86,78]
5252->[351,344]
100000->[4806,4784]
4000000->[141696, 141448]
• I did not know! :( – Stewie Griffin Aug 29 '17 at 15:14
• @StewieGriffin, it's easy to intuit if you look at the modulus sequence: 0%6 is a multiple of 6, 1%6 cannot be determined, 2%6 is a multiple of 2, 3%6 is a multiple of 3, 4%6 is a multiple of 2, and 5%6 cannot be determined. – zzzzBov Aug 29 '17 at 23:17
• @zzzzBov that'd be really helpful if I knew why modulus had a sequence, and what it meant for primes... I wish high school taught number theory... – Socratic Phoenix Aug 30 '17 at 3:43
• @SocraticPhoenix, modulus means "remainder after division". 0, 6, 12, etc all produce 0 after division by 6; 1, 7, 13 all produce 1. Since we're looking for numbers that can't be divided into factors, knowing that a number is divisible by an integer greater than 1 tells us that the number is not prime. – zzzzBov Aug 30 '17 at 4:33

05AB1E, 10 9 bytes

Saved 1 byte thanks to Erik the Outgolfer

Outputs as [PlusPrimes, MinusPrimes]

LDpÏ6%5Ñ¢

Try it online! or as a Test Suite

Explanation

L             # push range [1 ... input]
DpÏ          # keep only primes
6%        # mod each by 6
5Ñ      # divisors of 5 [1, 5]
¢     # count

MATL, 10 bytes

Zq6\!5lh=s

Explanation

Zq     % Implicitly input k. Push row vector of primes up to k
6\     % Modulo 6, element-wise
!      % Transpose into a column vector
5lh    % Push row vector [5, 1]
=      % Is equal?, element-wise with broadcast
s      % Sum of each column. Implicitly display

Jelly, 7 bytes

s6ÆPSm4

Plus, then minus.

Try it online!

How it works

s6ÆPSm4  Main link. Argument: n

s6       Split [1, ..., n] into chunks of length 6.
ÆP     Test all integers for primality.
S    Sum across columns.
This counts the primes of the form 6k + c for c = 1, ..., 6.
m4  Take every 4th element, leaving the counts for 6k + 1 and 6k + 5.

Python 2, 77 bytes

-2 bytes thanks to Neil

lambda x:[sum(all(n%j for j in range(2,n))for n in range(i,x,6))for i in 7,5]

Try it online!

Previous solution, 8381 79 bytes

-1 byte thanks to Mr. Xcoder
-2 bytes thanks to Halvard Hummel

lambda x:map([all(n%i for i in range(2,n))*n%6for n in range(4,x)].count,[5,1])

Try it online!
Both output as [MinusPrimes,PlusPrimes]

• 83 – Mr. Xcoder Aug 29 '17 at 12:43
• 81 bytes – Halvard Hummel Aug 29 '17 at 12:46
• 80? – Neil Aug 29 '17 at 15:48
• I've done too many JavaScript array comprehensions - I'd forgotten that Python lists often don't need []s. – Neil Aug 29 '17 at 17:08
• So, you divide n by all numbers from i to n-1 to see if it is prime, then generate all of the integers (5,11,...) and (7,13, ...) and test if the number in question is there, and count them. Seems efficient. ;) – Yakk Aug 29 '17 at 19:17

Mathematica, 51 bytes

(s=#;Mod[Prime~Array~PrimePi@s,6]~Count~#&/@{5,1})&

Try it online!

@ngenisis golfed it down, saving 4 bytes

Mathematica, 47 bytes

sPrime~Array~PrimePi@s~Mod~6~Count~#&/@{5,1}
• Mod can also be infix, and if you're going to name the first argument s, just use a named argument: sPrime~Array~PrimePi@s~Mod~6~Count~#&/@{5,1} – ngenisis Aug 29 '17 at 16:29

Japt, 1513 11 bytes

Output order is [+,-].

õj ò6 yx ë4

Test it

• Took some inspiration from Dennis' Jelly solution but, after golfing, it's closer to being a port.
• 2 bytes saved thank to Oliver bringing the previously-unknown-to-me ë method for arrays to my attention.

Explanation

Implicit input of integer U.

õj

Generate an array of integers (õ) from 1 to U and check if each is a prime (j), giving an array of booleans.

ò6

Partition the array into sub-arrays of length 6.

yx

Transpose (y) and sum the columns.

ë4

Get every 4th element of the array and implicitly output them.

Original, 191716 15 bytes

õ fj
5â £è_%6¥X

Test it

• 1 byte thanks to an inspired suggestion from Oliver to use the divisors of 5 after I'd rested on my laurels splitting 15 to an array.

J, 23 bytes

1#.5 1=/6|_1 p:@i.@p:>:

Try it online!

1#.5 1=/6|_1 p:@i.@p:>:   input: y
_1       p:     number of primes
>:   less than y + 1
p:@i.        prime range from 0 to that number
6|                get residues modulo 6
5 1=/                  table of values equal to 5 or 1
1#.                       sum of each (antibase 1)

Retina, 53 51 bytes

.+
$* 1$1¶
G1111
A^(11+)\1+$1{6} *M111 \b1\b Try it online! Explanation: .+$*

Convert to unary.

1
$1¶ Count from 1 up to n. G1111 Delete numbers less than 4. A^(11+)\1+$

Delete composite numbers.

1{6}

Take the remainder modulo 6.

*M111

Print the number of numbers with a remainder between 3 and 5.

\b1\b

Print the number of numbers with a remainder of 1.

Ruby, 61 60 bytes

(52 bytes + 8 for the -rprimes flag)

->n{[1,5].map{|x|(4..n).count{|i|i.prime?&&i%6==x}}}

Returns an array of the form [plus primes, minus primes].

Saved 1 byte thanks to G B!

Try it online.

• I was inspired by your answer and updated mine (in Haskell)! – jferard Aug 29 '17 at 20:37
• @jferard I'm very glad to hear that! :) – Cristian Lupascu Aug 29 '17 at 20:47
• You can use count on the range without the splat operator (save 1 byte). – G B Aug 30 '17 at 9:25

Perl 6, 42 bytes

Saved 1 byte by removing a useless space...

Saved 2 bytes by reorganizing the map call — thanks to @Joshua.

Saved 3 bytes because .round equals .round: 1.

Actually the complex exponential is cool but very expensive characterwise. Saved 10 bytes just by ditching it...

{[+] map {.is-prime*($_%6-1??i!!1)},5..$_}

Try it online!

This was the version with the complex exponential. (I like it too much to delete it.) The new version works exactly in the same way, just the complex exponential is replaced by the much shorter ternary operator.

{[+] map {.is-prime*exp(π*($_%6-1)i/8).round},5..$_}

Try it online!

The output is a complex number (PlusPrimes) + (MinusPrimes)i. I hope it's not too much against the rules.

Explanation: It's a function that takes one integer argument. We iterate over all integers from 5 to the argument ((5..$_)). For each of these, we evaluate .is-prime (this is called on$_, the argument of the mapped block), multiply it (if numified, True == 1, False == 0) with a complex exponential that's made to be either exp(0) = 1 (for $_%6 = 1) or exp(iπ/2) = i (for$_%6 = 5), and finally round it to the nearest integer. Summing them up with [+] gives the result.

Finally: it's really efficient, so I'm not sure if TIO won't time out before you get your output for higher numbers (for 1e5, it takes 26 sec on my machine, and TIO tends to be somewhat slower).

• that's fine. good job! – user73398 Aug 29 '17 at 21:52
• I think you mean inefficient? Nice method though! – Jonathan Allan Aug 29 '17 at 22:19
• That was a crude attempt at irony :—). – Ramillies Aug 29 '17 at 22:21
• When golfing, using the method forms of map or grep can sometimes cost you a few characters. This saves 2 chars: {[+] map {.is-prime*exp(π*($_%6-1)i/8).round: 1},5..$_} – Joshua Aug 30 '17 at 0:54
• Forgot to do that here, thanks for bringing it to my attention! – Ramillies Aug 30 '17 at 9:33

Actually, 21 bytes

u5xp░⌠6@%1=;╖*ƒ⌡Ml╜

Try it online!

Outputs the PlusPrimes first, followed by the MinusPrimes

Explanation:

u5xp░⌠6@%1=;╖*ƒ⌡Ml╜
u5x                    range(5, n+1)
p░                 primes in range
⌠6@%1=;╖*ƒ⌡M    for each prime:
6@%               mod 6
1=             equal to 1
;╖*ƒ        execute ╖ if p%6==1 (add 1 to register 0, consuming p)
l   length of resulting list (MinusPrimes)
╜  push value in register 0 (PlusPrimes)

[~>$primeYES 6%5 1,$=table tr$summap] Try it online! Rather slow, tests for primality for each K < N. Works similar to my J answer. MATLAB 2017a, 29 Bytes sum(mod(primes(k),6)'==[5,1]) Explanation: primes(k) gets all primes up to and including k. mod(primes(k),6)' takes the modulus 6 of all primes and transposes it so the sum runs along the correct dimension. ==[5,1] sets all fives (minusPrimes) to 1 in the first column and all ones (plusPrimes) to 1 in the second column. sum() sums each column. This outputs [minusPrime, plusPrime] Japt, 18 16 bytes -2 bytes thanks to @Oliver õ_j ©Z%6 5â £è¥X Try it online! Outputs in the format [PlusPrimes, MinusPrimes]. • Hmm ... I just got back to my desk, golfed mine down to 17 bytes and then saw you'd posted this ... don't know whether I should post it or not as the crux of both our solutions is mapping over [5,1] to get the counts and you got there first. – Shaggy Aug 29 '17 at 16:47 • @Shaggy IMO your solution has enough differences to remain a separate post. You used filter and a string; I used the mapping function of õ and an array. Besides, I got the [5,1] idea from another answer. – Justin Mariner Aug 29 '17 at 16:52 • I'll think on it a bit; solutions in different languages using similar methods (even if one "borrowed" it from the other) is OK but 2 solutions in the same language doing so doesn't sit entirely well with me. I've edited into my post as an alternative for now. – Shaggy Aug 29 '17 at 17:00 • I decided to run with it and then shaved another byte off. – Shaggy Aug 29 '17 at 17:47 • You can use to get [1,5] – Oliver Aug 29 '17 at 19:55 C#, 202179 174 Bytes -23 Bytes thanks to Mr. Xcoder -5 Bytes thanks to Cyoce Function that returns an array of length 2, [MinusPrimes, PlusPrimes] Execute by calling a(n). int[]a(int n){int[]r={0,0};for(int i=5;i<=n;i++)if(i%2*b(i)>0)if(i%6<5)r++;else++r;return r;}int b(int n){for(int i=3;i-2<Math.Sqrt(n);i+=2)if(n%i<1)return 0;return 1;} Properly formatted code on Try It Online: Here • Can you add a tio link? – Mr. Xcoder Aug 29 '17 at 13:49 • Sorry for golfing byte-to-byte, 194 bytes: public int[]a(int n){int[]r=new int;for(int i=5;i<=n;i++)if(i%2*b(i)>0)if(i%6<5)r++;else++r;return r;}public int b(int n){for(int i=3;i<=Math.Sqrt(n)+1;i+=2)if(n%i<1)return 0;return 1;} – Mr. Xcoder Aug 29 '17 at 14:06 • 193 bytes: public int[]a(int n){int[]r=new int;for(int i=5;i<=n;i++)if(i%2*b(i)>0)if(i%6<5)r++;else++r;return r;}public int b(int n){for(int i=3;i-2<Math.Sqrt(n);i+=2)if(n%i<1)return 0;return 1;} – Mr. Xcoder Aug 29 '17 at 14:09 • lmao youre loving this arent you ;) – MysticVagabond Aug 29 '17 at 14:10 • thanks for all the help, since youve posted a separate answer and stated its a golf of mine, im just gonna leave mine as is and take the lessons onto the next challenge :P – MysticVagabond Aug 30 '17 at 14:50 Haskell, 81 69 bytes f n=(\r->sum[1|i<-[2..n],all((>0).rem i)[2..i-1],rem i 6==r])<$>[5,1]

Try it online!

First solution was:

r!l=sum[1|i<-l,rem i 6==r]
f n|l<-[i|i<-[2..n],all((>0).rem i)[2..i-1]]=(5!l,1!l)

But I read w0lf's answer in Ruby...

/K%R6fP_TSQ5/K1

Test Suite.

m/%R6fP_TSQd,1 5

Test Suite.

How?

Explanation #1

/K%R6fP_TSQ5/K1 - Full program.

fP_TSQ     - Filter the primes in the range [1...input].
%R6           - Mod 6 on each.
K              - Assign them to a variable K.
/          5    - Count the occurrences of 5 in K.
/K1 - Count the occurrences of 1 in K.
- Implicitly output the result.

Explanation #2

m/%R6fP_TSQd,1 5 - Full program.

fP_TSQ      - Filter the primes in the range [1...input]
%R6            - Mod 6 on each.
,1 5 - Push the list [1, 5]
m/         d     - Count how many of each there are.
- Implicitly output the result.

Alternatives:

/K%R6fP_TSQ5/KhZ    (16 bytes)
K%R6fP_TSQ/K5/K1    (16 bytes)
m/%R6fP_TSQdj15T    (16 bytes)
m/%R6fP_TSQd[1 5    (16 bytes)
m/%R6fP_TSQdsM15   (17 bytes)
m/%R6.MP_ZSQd,1 5   (17 bytes)
m/%R6.MP_ZSQdj15T   (17 bytes)
m/%R6.MP_ZSQd[1 5   (17 bytes)
• Congrats on 10k!! – Luis Mendo Aug 29 '17 at 13:05
• @LuisMendo Thanks a lot :-) – Mr. Xcoder Aug 29 '17 at 13:06

Jelly,  12 11  10 bytes

Thanks to @cairdcoinheringaahing for some tips in chat. Thanks to @Dennis for saving one byte in chat.

ÆR%6ċÐ€1,5

Try it online!

ÆR%6µ1,5=þS

Try it online!

Jelly, 11 bytes

ÆR%6µċ5,ċ1$Try it online! How does this work? Explanation #1 ÆR%6ċÐ€1,5 As usual, full program. ÆR Get all the primes in the range [2...input]. %6 Modulo each by 6. 1,5 The two-element list [1, 5]. ċÐ€ Count the occurrences of each of ^ in the prime range. Explanation #2 ÆR%6µ1,5=þS As usual, full program. ÆR Get all the primes in the range [2...input]. %6 Modulo each by 6. µ Chain separator. 1,5 The two-element list [1, 5]. = Equals? þ Outer product. S Sum. Explanation #3 ÆR%6µċ5,ċ1$   As usual, full program.

ÆR            All the primes in the range [2...input].
%6          Modulo each by 6.
µ     $Some helpers for the chains. , Two element list. ċ5 The number of 5s. ċ1 The number of 1s. Java 8, 1411401381061011009694 81 bytes n->{int r[]={0,0},c;for(;n-->4;r[n%6/4]+=c)for(c=n;c>1;c=c-1&~n%c>>-1);return r;} Returns an integer-array with two values, in reversed order compared to the challenge description: [plusPrime, minusPrime]. Port of @Xynos' C# answer, after I golfed 39 40 42 bytes. Huge help from @Nevay for another whopping -55 bytes. Explanation: Try it here. (Final test case of 4000000 is exceeding the 60 sec time limit slightly.) n->{ // Method with integer parameter and integer-array return-type int r[]={0,0}, // Return integer-array, starting at [0,0] c; // Temp integer for(;n-->4; // Loop (1) as long as the input is larger than 4 // and decrease n by 1 before every iteration r[n%6/4]+=c) // After every iteration, increase the plus or minus prime by c // (where c is either 0 or 1) for(c=n; // Reset c to n c>1; // And inner loop (2) as long as c is larger than 1 c= // Change c to: c-1&~n%c>>-1; // inverting the bits of n, [~n] // modulo-c that result, [%c] // then bit-shift right that by -1, [>>-1] // and then bitwise-AND that result with c-1 [c-1&] ); // End of inner loop (2) // End of loop (1) (implicit / single-line body) return r; // Return result integer-array } // End of method • 106 bytes: n->{int r[]={0,0},i=4,j,c;for(;i++<n;){for(j=c=1;j*j<i;)c=i%(j+=2)<1?0:c;if(i%2*c>0)r[i%6%5]++;}return r;} – Nevay Aug 30 '17 at 13:12 • 101 bytes: n->{int r[]={0,0},i=4,j,c;for(;i++<n;r[i%6%5%2]-=-i%2*c>>-1)for(j=c=1;j*j<i;)c|=i%(j+=2)-1;return r;} – Nevay Aug 30 '17 at 13:41 • 96 bytes: n->{int r[]={0,0},i=4,j,c;for(;i++<n;r[i%6%5%2]+=i&c)for(j=c=1;j*j++<i;)c&=-i%++j>>-1;return r;} (-1 thanks to your j++,++j) – Nevay Aug 30 '17 at 14:23 • 94 bytes: n->{int r[]={0,0},i=4,j,c;for(;i++<n;r[i%6/4]+=i&c)for(j=c=1;j*j++<i;)c&=-i%++j>>-1;return r;} ([plusPrime, minusPrime]). – Nevay Aug 30 '17 at 14:32 • 81 bytes: n->{int r[]={0,0},c;for(;n-->4;r[n%6/4]+=c)for(c=n;c>1;)c=c-1&~n%c>>-1;return r;} – Nevay Aug 30 '17 at 23:37 JavaScript (ES6), 83828068 66 bytes Turned out a fully recursive solution was much shorter than mapping an array! Output order is [-,+]. Craps out with an overflow error somewhere around 3490. f=(n,a=[0,0])=>n>4?f(n-1,a,(g=y=>n%--y?g(y):y<2)(n)&&++a[n%6%5]):a Try it o.innerText=( f=(n,a=[0,0])=>n>4?f(n-1,a,(g=y=>n%--y?g(y):y<2)(n)&&++a[n%6%5]):a )(i.value=6);oninput=_=>o.innerText=i.value>5?f(+i.value):[0,0] <input id=i min=6 type=number><pre id=o> CJam, 19 bytes ri){mp},6f%_5e=p1e= Program that takes the input from STDIN, and outputs the two numbers separated by newline through STDOUT. Try it online! Explanation ri){mp},6f%_5e=p1e= ri Read integer k ) Add 1 , Filter the (implicit) array [0 1 ... k] ... {mp} ... on the function "is prime" f Map over the resulting array... % ... the function "modulus" ... 6 ... with extra parameter 6 _ Duplicate the resulting array e= Count occurrences ... 5 ... of number 5 p Print with newline e= Count occurrences ... 1 ... of number 1. Implicitly display R + numbers, 666058 40 bytes -16 bytes thanks to Jarko Dubbeldam! I subsequently golfed another two bytes off. cat(table(numbers::Primes(4,scan())%%6)) Prints PlusPrimes MinusPrimes to stdout; reads from stdin. table tabulates the count of each occurrence of the values in its input vector, in ascending order of value. Hence, since there are only two values, namely 1 and 5 (mod 6), this is exactly the function we need, along with numbers::Primes, which returns all primes between 4 and the input. Try it online! Base R, 97918986 65 bytes a bunch of bytes saved by Jarko here, too function(n)table((5:n)[sapply(5:n,function(x)all(x%%2:x^.5))]%%6) This is nearly identical to the above, except it calculates all the primes in base R rather than using a package, and it returns by function output rather than printing it out. You can see in the output that it returns a table with names 1 and 5, with the counts below. Try it online! • 47 bytes – JAD Aug 30 '17 at 8:32 • (Dennis added numbers to TIO, so that works now :)) – JAD Aug 30 '17 at 8:32 • 42 bytes – JAD Aug 30 '17 at 8:34 • all(x%%2:x^.5>0), anything nonzero is already truthy, so all(x%%2:x^.5) works too – JAD Aug 30 '17 at 10:47 • @JarkoDubbeldam very nice! Turns out since all the values are greater than 4 we can get rid of the >4 since we won't have 2 in there anymore as a prime, so this golfs to 40 bytes instead. – Giuseppe Aug 30 '17 at 13:30 Pari/GP, 41 bytes n->vecsum([[i>3,i<3]|i<-primes([4,n])%6]) Try it online! JavaScript (SpiderMonkey), 151, 140, 131 bytes n=>[...Array(n+1).keys()].splice(5).filter(a=>!/^1?$|^(11+?)\1+$/.test("1".repeat(a))).reduce((r,a)=>(a%6<2?r++:r++,r),[0,0]) Try it online! Thanks to shaggy for helping with a bug fix and golfing. Explanation: n=> // Create a lambda, taking n [...Array(n+1).keys()] // Create a list from 0 to n+1 .splice(5) // remove first five elements .filter(a=> // filter the list to get primes !/^1?$|^(11+?)\1+\$/.test("1".repeat(a))) // using the famous regex here: https://stackoverflow.com/questions/2795065/how-to-determine-if-a-number-is-a-prime-with-regex
.reduce((r,a)=>                               // reduce the list
(a%6<2?r++:r++,r),                   // by counting plus primes
[0,0])                                     // and minus primes
• Retturns 17,15 for 149 (Should be 18,15). You need to increase the size of your array by 1: TIO. Incidentally, this is just "vanilla" ES6, nothing specific to SpiderMonkey in it. Also, you can use Stack Snippets for JS, rather than TIO. And, you have a lot of spaces you can remove. – Shaggy Aug 30 '17 at 15:45
• Another couple of quick savings for you, to get you down to 131 bytes. – Shaggy Aug 30 '17 at 16:50
• @Shaggy I did not realise you could use reduce like that. – Pureferret Aug 31 '17 at 10:17