Plus-Primzahlen gegen Minus-Primzahlen

35

Die meisten von uns wissen ...

dass alle Primzahlen p>3von der Form sind enter image description here

Aber wie viele Plus-Primzahlen ( 6n+1) und wie viele Minus-Primzahlen ( 6n-1) befinden sich in einem bestimmten Bereich?

Die Herausforderung

Gegeben eine ganze Zahl k>5, zählen , wie viele primes<=ksind PlusPrimes und wie viele sind MinusPrimes .

Beispiele

für k=100wir haben
[5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89] 12 MinusPrimes
und
[7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97] 11 PlusPrimes

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

Regeln

Ihr Code muss 2 Ganzzahlen ausgeben : eine für die MinusPrimes und eine für die PlusPrimes in beliebiger Reihenfolge (bitte geben Sie an, welche welche ist).
Das ist : Die kürzeste Antwort in Bytes gewinnt!

Testfälle

Eingabe -> Ausgabe [ MinusPrimes , PlusPrimes ]

6->[1,0]  
7->[1,1]   
86->[11,10]  
986->[86,78]  
5252->[351,344]  
100000->[4806,4784]   
4000000->[141696, 141448]

quelle
45
Ich wusste es nicht! :(
Stewie Griffin
13
@StewieGriffin, es ist leicht zu verstehen, wenn Sie die Modulsequenz betrachten: Ist 0%6ein Vielfaches von 6, 1%6kann nicht bestimmt werden, 2%6ist ein Vielfaches von 2, 3%6ist ein Vielfaches von 3, 4%6ist ein Vielfaches von 2 und 5%6kann nicht bestimmt werden.
zzzzBov
3
@zzzzBov , die wirklich hilfreich sein würden , wenn ich wusste , warum Modul eine Folge hatte, und was es für Primzahlen gemeint ... Ich wünsche , High - School - Zahlentheorie gelehrt ...
sokratisches Phoenix
@SocraticPhoenix, Modul bedeutet "Rest nach Division". 0, 6, 12 usw. erzeugen alle 0 nach Division durch 6; 1, 7, 13 alle ergeben 1. Da wir nach Zahlen suchen, die nicht in Faktoren unterteilt werden können, wissen wir, dass eine Zahl durch eine ganze Zahl größer als 1 teilbar ist, dass die Zahl keine Primzahl ist.
zzzzBov

Antworten:

10

05AB1E , 10 9 Bytes

1 Byte gespeichert dank Erik the Outgolfer gespart

Ausgänge als [PlusPrimes, MinusPrimes]

LDpÏ6%5Ñ¢

Probieren Sie es online! oder als Testsuite

Erläuterung

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

MATL , 10 Bytes

Zq6\!5lh=s

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

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
Luis Mendo
quelle
6

Python 2 , 77 Bytes

-2 Bytes dank 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]

Probieren Sie es online!

Vorherige Lösung, 83 81 79 Bytes

-1 Byte dank Mr. Xcoder
-2 Byte dank Halvard Hummel

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

Probieren Sie es online!
Beide Ausgabe als [MinusPrimes, PlusPrimes]

Stange
quelle
83
Mr. Xcoder
81 Bytes
Halvard Hummel
80?
Neil
Ich habe zu viele JavaScript-Arrays verstanden - ich hatte vergessen, dass Python-Listen oft keine []s benötigen .
Neil
Teilen Sie also n durch alle Zahlen von i bis n-1, um festzustellen, ob es sich um eine Primzahl handelt, und generieren Sie dann alle Ganzzahlen (5,11, ...) und (7,13, ...) fragliche Nummer ist da, und zähle sie. Scheint effizient. ;)
Yakk
5

Gelee , 7 Bytes

s6ÆPSm4

Plus, dann minus.

Probieren Sie es online!

Wie es funktioniert

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.
Dennis
quelle
5

Mathematica, 51 Bytes

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

Probieren Sie es online!

@ngenisis hat es abgespielt und dabei 4 Bytes gespart

Mathematica, 47 Bytes

sPrime~Array~PrimePi@s~Mod~6~Count~#&/@{5,1}
J42161217
quelle
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
5

Japt, 15 13 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, 19 17 16 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.
Shaggy
quelle
3

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)
Conor O'Brien
quelle
3

Retina, 53 51 bytes

.+
$*
1
$`1¶
G`1111
A`^(11+)\1+$
1{6}

*M`111
\b1\b

Try it online! Explanation:

.+
$*

Convert to unary.

1
$`1¶

Count from 1 up to n.

G`1111

Delete numbers less than 4.

A`^(11+)\1+$

Delete composite numbers.

1{6}

Take the remainder modulo 6.

*M`111

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

\b1\b

Print the number of numbers with a remainder of 1.

Neil
quelle
3

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.

Cristian Lupascu
quelle
I was inspired by your answer and updated mine (in Haskell)!
jferard
@jferard I'm very glad to hear that! :)
Cristian Lupascu
You can use count on the range without the splat operator (save 1 byte).
G B
3

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

Ramillies
quelle
that's fine. good job!
I think you mean inefficient? Nice method though!
Jonathan Allan
That was a crude attempt at irony :—).
Ramillies
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
Forgot to do that here, thanks for bringing it to my attention!
Ramillies
2

Actually, 21 bytes

u5x`p░⌠6@%1=;`╖*ƒ⌡Ml╜

Try it online!

Outputs the PlusPrimes first, followed by the MinusPrimes

Explanation:

u5x`p░⌠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)
Mego
quelle
2

Stacked, 37 bytes

[~>$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.

Conor O'Brien
quelle
2

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]

Poelie
quelle
2

Japt, 18 16 bytes

-2 bytes thanks to @Oliver

õ_j ©Z%6
5â £è¥X

Try it online!

Outputs in the format [PlusPrimes, MinusPrimes].

Justin Mariner
quelle
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
@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
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
I decided to run with it and then shaved another byte off.
Shaggy
You can use to get [1,5]
Oliver
2

C#, 202 179 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[1]++;else++r[0];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

MysticVagabond
quelle
Can you add a tio link?
Mr. Xcoder
Sorry for golfing byte-to-byte, 194 bytes: public int[]a(int n){int[]r=new int[2];for(int i=5;i<=n;i++)if(i%2*b(i)>0)if(i%6<5)r[1]++;else++r[0];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
193 bytes: public int[]a(int n){int[]r=new int[2];for(int i=5;i<=n;i++)if(i%2*b(i)>0)if(i%6<5)r[1]++;else++r[0];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
lmao youre loving this arent you ;)
MysticVagabond
1
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
2

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

jferard
quelle
1

Pyth, 15 bytes

/K%R6fP_TSQ5/K1

Test Suite.

Pyth, 16 bytes

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_TSQdsM`15   (17 bytes)
m/%R6.MP_ZSQd,1 5   (17 bytes)
m/%R6.MP_ZSQdj15T   (17 bytes)
m/%R6.MP_ZSQd[1 5   (17 bytes)
Mr. Xcoder
quelle
2
Congrats on 10k!!
Luis Mendo
@LuisMendo Thanks a lot :-)
Mr. Xcoder
1

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!

Jelly, 11 bytes

Æ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.
Mr. Xcoder
quelle
1

Java 8, 141 140 138 106 101 100 96 94 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
Kevin Cruijssen
quelle
1
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
1
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
1
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
1
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
1
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
1

JavaScript (ES6), 83 82 80 68 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>

Shaggy
quelle
0

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
Luis Mendo
quelle
0

R + numbers, 66 60 58 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, 97 91 89 86 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!

Giuseppe
quelle
47 bytes
JAD
(Dennis added numbers to TIO, so that works now :))
JAD
42 bytes
JAD
all(x%%2:x^.5>0), anything nonzero is already truthy, so all(x%%2:x^.5) works too
JAD
@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
0

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[1]++:r[0]++,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[1]++:r[0]++,r),                   // by counting plus primes
           [0,0])                                     // and minus primes
Pureferret
quelle
1
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
1
Another couple of quick savings for you, to get you down to 131 bytes.
Shaggy
@Shaggy I did not realise you could use reduce like that.
Pureferret