Sexy primes: Difference between revisions
m (→{{header|Perl 6}}: added zkl header) |
(→{{header|zkl}}: added code) |
||
| Line 269: | Line 269: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic |
|||
| ⚫ | |||
primes), because it is easy and fast to generate primes. |
|||
<lang zkl></lang> |
|||
[[Extensible prime generator#zkl]] could be used instead. |
|||
<lang zkl>var [const] BI=Import("zklBigNum"); // libGMP |
|||
const N=1_000_000; |
|||
ps,p := Data(N+1).fill(0), BI(2); |
|||
while(p.nextPrime()<=N){ ps[p]=1 } // bitmap of primes |
|||
ns:=[3..N-6,2].filter('wrap(n){ 2==(ps[n] + ps[n+6]) }); |
|||
msg(N,"pairs",ns,5,1); |
|||
ns:=[3..N-12,2].filter('wrap(n){ 3==(ps[n] + ps[n+6] + ps[n+12]) }); |
|||
msg(N,"triples",ns,5,2); |
|||
ns:=[3..N-18,2].filter('wrap(n){ 4==(ps[n] + ps[n+6] + ps[n+12] + ps[n+18]) }); |
|||
msg(N,"quadruplets",ns,5,3); |
|||
ns:=[3..N-24,2].filter('wrap(n){ 5==(ps[n] + ps[n+6] + ps[n+12] + ps[n+18] + ps[n+24]) }); |
|||
msg(N,"quintuplets",ns,1,4); |
|||
ns:=[7..N-6,2].filter('wrap(n){ ps[n] and 0==(ps[n-6] + ps[n+6]) }); |
|||
msg(N,"(make that unsexy primes)",ns,10,0); |
|||
fcn msg(N,s,ns,n,g){ |
|||
gs:=ns[-n,*].apply('wrap(n){ [0..g*6,6].apply('+(n)) }) |
|||
.pump(String,T("concat",","),"(%s) ".fmt); |
|||
println("Number of sexy prime %s less than %,d = %,d".fmt(s,N,ns.len())); |
|||
println("The last %d are:\n %s\n".fmt(n,gs)); |
|||
| ⚫ | |||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Number of sexy prime pairs less than 1,000,000 = 16,386 |
|||
The last 5 are: |
|||
(999371,999377) (999431,999437) (999721,999727) (999763,999769) (999953,999959) |
|||
Number of sexy prime triples less than 1,000,000 = 2,900 |
|||
The last 5 are: |
|||
(997427,997433,997439) (997541,997547,997553) (998071,998077,998083) (998617,998623,998629) (998737,998743,998749) |
|||
Number of sexy prime quadruplets less than 1,000,000 = 325 |
|||
The last 5 are: |
|||
(977351,977357,977363,977369) (983771,983777,983783,983789) (986131,986137,986143,986149) (990371,990377,990383,990389) (997091,997097,997103,997109) |
|||
Number of sexy prime quintuplets less than 1,000,000 = 1 |
|||
The last 1 are: |
|||
(5,11,17,23,29) |
|||
Number of sexy prime (make that unsexy primes) less than 1,000,000 = 48,624 |
|||
The last 10 are: |
|||
(999809) (999853) (999863) (999883) (999907) (999917) (999931) (999961) (999979) (999983) |
|||
</pre> |
</pre> |
||
Revision as of 00:32, 30 September 2018
| This page uses content from Wikipedia. The original article was at Sexy_prime. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
In mathematics, sexy primes are prime numbers that differ from each other by six.
For example, the numbers 5 and 11 are both sexy primes, because 11 minus 5 is 6.
The term "sexy prime" is a pun stemming from the Latin word for six: sex.
Sexy prime pairs: Sexy prime pairs are groups of two primes that differ by 6. e.g. (5 11), (7 13), (11 17)
See sequences: OEIS:A023201 and OEIS:A046117
Sexy prime triplets: Sexy prime triplets are groups of three primes where each differs from the next by 6. e.g. (5 11 17), (7 13 19), (17 23 29)
See sequences: OEIS:A046118, OEIS:A046119 and OEIS:A046120
Sexy prime quadruplets: Sexy prime quadruplets are groups of four primes where each differs from the next by 6. e.g. (5 11 17 23), (11 17 23 29)
See sequences: OEIS:A023271, OEIS:A046122, OEIS:A046123 and OEIS:A046124
Sexy prime quintuplets: Sexy prime quintuplets are groups of five primes with a common difference of 6. One of the terms must be divisible by 5, because 5 and 6 are relatively prime. Thus, the only possible sexy prime quintuplet is (5 11 17 23 29)
- Task
- For each of pairs, triplets, quadruplets and quintuplets, Find and display the count of each group type of sexy primes less than one million (1,000,000).
- Display the last 5 (or all if there are fewer), less than one million, of each sexy prime group type.
- Find and display the count of the unsexy primes less than one million.
- Find and display the last 10 unsexy primes less than one million.
Factor
<lang factor>USING: combinators.short-circuit fry io kernel literals make math math.primes math.ranges prettyprint qw sequences ; IN: rosetta-code.sexy-primes
CONSTANT: primes $[ 1,000,000 primes-upto ]
CONSTANT: tuplet-names qw{ pair triplet quadruplet quintuplet }
- tuplet ( m n -- seq ) dupd 1 - 6 * + 6 <range> ;
- sexy-tuplets ( n -- seq ) [ primes ] dip '[
[ _ tuplet dup [ prime? ] all? [ , ] [ drop ] if ] each
] { } make ;
- show-tuplets ( n -- )
"Number of sexy prime " write dup 2 - tuplet-names nth write
"s less than 1,000,000: " write sexy-tuplets dup length .
5 short tail* "Up to last 5: " write [ { } like pprint bl ]
each nl nl ;
- unsexy-primes ( -- seq ) primes [
{ [ 6 + prime? not ] [ 6 - prime? not ] } 1&&
] filter ;
- show-unsexy ( -- )
"Number of unsexy primes less than 1,000,000: " write unsexy-primes dup length . "Last 10: " write 10 tail* [ pprint bl ] each nl ;
- main ( -- ) 2 5 [a,b] [ show-tuplets ] each show-unsexy ;
MAIN: main</lang>
- Output:
Number of sexy prime pairs less than 1,000,000: 16386
Up to last 5: { 999371 999377 } { 999431 999437 } { 999721 999727 } { 999763 999769 } { 999953 999959 }
Number of sexy prime triplets less than 1,000,000: 2900
Up to last 5: { 997427 997433 997439 } { 997541 997547 997553 } { 998071 998077 998083 } { 998617 998623 998629 } { 998737 998743 998749 }
Number of sexy prime quadruplets less than 1,000,000: 325
Up to last 5: { 977351 977357 977363 977369 } { 983771 983777 983783 983789 } { 986131 986137 986143 986149 } { 990371 990377 990383 990389 } { 997091 997097 997103 997109 }
Number of sexy prime quintuplets less than 1,000,000: 1
Up to last 5: { 5 11 17 23 29 }
Number of unsexy primes less than 1,000,000: 48626
Last 10: 999809 999853 999863 999883 999907 999917 999931 999961 999979 999983
Go
<lang go>package main
import "fmt"
func sieve(limit uint64) []bool {
limit++
// True denotes composite, false denotes prime.
c := make([]bool, limit) // all false by default
c[0] = true
c[1] = true
// no need to bother with even numbers over 2 for this task
p := uint64(3) // Start from 3.
for {
p2 := p * p
if p2 >= limit {
break
}
for i := p2; i < limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
return c
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n)
if n < 0 {
s = s[1:]
}
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
if n >= 0 {
return s
}
return "-" + s
}
func minOf(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
// sieve up to 1 million
sv := sieve(1e6)
var pairs [][2]int
var trips [][3]int
var quads [][4]int
var quins [][5]int
var unsexy = []int{2, 3}
for i := 3; i < 1e6; i += 2 {
if i > 5 && i < 999994 && !sv[i] && sv[i-6] && sv[i+6] {
unsexy = append(unsexy, i)
continue
}
if i < 999994 && !sv[i] && !sv[i+6] {
pair := [2]int{i, i + 6}
pairs = append(pairs, pair)
} else {
continue
}
if i < 999988 && !sv[i+12] {
trip := [3]int{i, i + 6, i + 12}
trips = append(trips, trip)
} else {
continue
}
if i < 999982 && !sv[i+18] {
quad := [4]int{i, i + 6, i + 12, i + 18}
quads = append(quads, quad)
} else {
continue
}
if i < 999976 && !sv[i+24] {
quin := [5]int{i, i + 6, i + 12, i + 18, i + 24}
quins = append(quins, quin)
}
}
le := len(pairs)
fmt.Println("Number of sexy prime pairs less than 1,000,000 =", commatize(le))
n := minOf(le, 5)
fmt.Println("The last", n, "is/are:\n ", pairs[le-n:], "\n")
le = len(trips)
fmt.Println("Number of sexy prime triplets less than 1,000,000 =", commatize(le))
n = minOf(le, 5)
fmt.Println("The last", n, "is/are:\n ", trips[le-n:], "\n")
le = len(quads)
fmt.Println("Number of sexy prime quadruplets less than 1,000,000 =", commatize(le))
n = minOf(le, 5)
fmt.Println("The last", n, "is/are:\n ", quads[le-n:], "\n")
le = len(quins)
fmt.Println("Number of sexy prime quintuplets less than 1,000,000 =", commatize(le))
n = minOf(le, 5)
fmt.Println("The last", n, "is/are:\n ", quins[le-n:], "\n")
le = len(unsexy)
fmt.Println("Number of unsexy primes less than 1,000,000 =", commatize(le))
n = minOf(le, 10)
fmt.Println("The last", n, "is/are:\n ", unsexy[le-n:])
}</lang>
- Output:
Number of sexy prime pairs less than 1,000,000 = 16,386 The last 5 is/are: [[999371 999377] [999431 999437] [999721 999727] [999763 999769] [999953 999959]] Number of sexy prime triplets less than 1,000,000 = 2,900 The last 5 is/are: [[997427 997433 997439] [997541 997547 997553] [998071 998077 998083] [998617 998623 998629] [998737 998743 998749]] Number of sexy prime quadruplets less than 1,000,000 = 325 The last 5 is/are: [[977351 977357 977363 977369] [983771 983777 983783 983789] [986131 986137 986143 986149] [990371 990377 990383 990389] [997091 997097 997103 997109]] Number of sexy prime quintuplets less than 1,000,000 = 1 The last 1 is/are: [[5 11 17 23 29]] Number of unsexy primes less than 1,000,000 = 48,626 The last 10 is/are: [999809 999853 999863 999883 999907 999917 999931 999961 999979 999983]
Perl 6
<lang perl6>use Math::Primesieve; my $sieve = Math::Primesieve.new;
my $max = 1_000_000; my %primes = $sieve.primes($max) X=> 1;
my $primes = %primes.keys.categorize: { .&sexy }
say "Total primes less than {comma $max}: ", comma +%primes.keys;
for <pair 2 triplet 3 quadruplet 4 quintuplet 5> -> $sexy, $cnt {
say "Number of sexy prime {$sexy}s less than {comma $max}: ", comma +$primes{$sexy};
say " Last 5 sexy prime {$sexy}s less than {comma $max}: ",
join ' ', $primes{$sexy}.sort(+*).tail(5).grep(*.defined).map:
{ "({ $_ «+« (0,6 … 24)[^$cnt] })" }
say ;
}
say "Number of unsexy primes less than {comma $max}: ", comma +$primes<unsexy>; say " Last 10 unsexy primes less than {comma $max}: ", $primes<unsexy>.sort(+*).tail(10);
sub sexy ($i) {
(
(so all(%primes{$i «+« (6,12,18,24)})) ?? 'quintuplet' !! Nil,
(so all(%primes{$i «+« (6,12,18) })) ?? 'quadruplet' !! Nil,
(so all(%primes{$i «+« (6,12) })) ?? 'triplet' !! Nil,
(so %primes{$i + 6 }) ?? 'pair' !! Nil,
(so any(%primes{$i «+« (6,-6) })) ?? 'sexy' !! 'unsexy'
).grep: *.defined
}
sub comma { $^i.flip.comb(3).join(',').flip }</lang>
- Output:
Total primes less than 1,000,000: 78,498 Number of sexy prime pairs less than 1,000,000: 16,386 Last 5 sexy prime pairs less than 1,000,000: (999371 999377) (999431 999437) (999721 999727) (999763 999769) (999953 999959) Number of sexy prime triplets less than 1,000,000: 2,900 Last 5 sexy prime triplets less than 1,000,000: (997427 997433 997439) (997541 997547 997553) (998071 998077 998083) (998617 998623 998629) (998737 998743 998749) Number of sexy prime quadruplets less than 1,000,000: 325 Last 5 sexy prime quadruplets less than 1,000,000: (977351 977357 977363 977369) (983771 983777 983783 983789) (986131 986137 986143 986149) (990371 990377 990383 990389) (997091 997097 997103 997109) Number of sexy prime quintuplets less than 1,000,000: 1 Last 5 sexy prime quintuplets less than 1,000,000: (5 11 17 23 29) Number of unsexy primes less than 1,000,000: 48,626 Last 10 unsexy primes less than 1,000,000: (999809 999853 999863 999883 999907 999917 999931 999961 999979 999983)
zkl
Using GMP (GNU Multiple Precision Arithmetic Library, probabilistic primes), because it is easy and fast to generate primes.
Extensible prime generator#zkl could be used instead. <lang zkl>var [const] BI=Import("zklBigNum"); // libGMP const N=1_000_000; ps,p := Data(N+1).fill(0), BI(2); while(p.nextPrime()<=N){ ps[p]=1 } // bitmap of primes
ns:=[3..N-6,2].filter('wrap(n){ 2==(ps[n] + ps[n+6]) }); msg(N,"pairs",ns,5,1);
ns:=[3..N-12,2].filter('wrap(n){ 3==(ps[n] + ps[n+6] + ps[n+12]) }); msg(N,"triples",ns,5,2);
ns:=[3..N-18,2].filter('wrap(n){ 4==(ps[n] + ps[n+6] + ps[n+12] + ps[n+18]) }); msg(N,"quadruplets",ns,5,3);
ns:=[3..N-24,2].filter('wrap(n){ 5==(ps[n] + ps[n+6] + ps[n+12] + ps[n+18] + ps[n+24]) }); msg(N,"quintuplets",ns,1,4);
ns:=[7..N-6,2].filter('wrap(n){ ps[n] and 0==(ps[n-6] + ps[n+6]) }); msg(N,"(make that unsexy primes)",ns,10,0);
fcn msg(N,s,ns,n,g){
gs:=ns[-n,*].apply('wrap(n){ [0..g*6,6].apply('+(n)) })
.pump(String,T("concat",","),"(%s) ".fmt);
println("Number of sexy prime %s less than %,d = %,d".fmt(s,N,ns.len()));
println("The last %d are:\n %s\n".fmt(n,gs));
}</lang>
- Output:
Number of sexy prime pairs less than 1,000,000 = 16,386 The last 5 are: (999371,999377) (999431,999437) (999721,999727) (999763,999769) (999953,999959) Number of sexy prime triples less than 1,000,000 = 2,900 The last 5 are: (997427,997433,997439) (997541,997547,997553) (998071,998077,998083) (998617,998623,998629) (998737,998743,998749) Number of sexy prime quadruplets less than 1,000,000 = 325 The last 5 are: (977351,977357,977363,977369) (983771,983777,983783,983789) (986131,986137,986143,986149) (990371,990377,990383,990389) (997091,997097,997103,997109) Number of sexy prime quintuplets less than 1,000,000 = 1 The last 1 are: (5,11,17,23,29) Number of sexy prime (make that unsexy primes) less than 1,000,000 = 48,624 The last 10 are: (999809) (999853) (999863) (999883) (999907) (999917) (999931) (999961) (999979) (999983)