Sum of primes in odd positions is prime: Difference between revisions
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: oops, change subscript) |
(Added Algol 68) |
||
Line 8: | Line 8: | ||
<br><br> |
<br><br> |
||
=={{header|ALGOL 68}}== |
|||
{{libheader|ALGOL 68-primes}} |
|||
<lang algol68>BEGIN # find primes (up to 999) p(i) for odd i such that the sum of primes p(j), j = 1, 3, 5, ..., i is prime # |
|||
INT max prime = 999; |
|||
PR read "primes.incl.a68" PR |
|||
[]BOOL prime = PRIMESIEVE 50 000; # guess that the max sum will be <= 50 000 # |
|||
# count the primes up to max prime # |
|||
INT p count := 0; FOR i TO max prime DO IF prime[ i ] THEN p count +:= 1 FI OD; |
|||
# construct a list of the primes up to max prime # |
|||
[ 1 : p count ]INT low prime; |
|||
INT low pos := 0; |
|||
FOR i TO max prime DO IF prime[ i ] THEN low prime[ low pos +:= 1 ] := i FI OD; |
|||
# find the sums of the odd primes and test for primality # |
|||
print( ( " i p[i] sum", newline ) ); |
|||
INT odd prime sum := 0; |
|||
FOR i BY 2 TO UPB low prime DO |
|||
IF odd prime sum +:= low prime[ i ]; |
|||
IF odd prime sum <= UPB prime |
|||
THEN |
|||
prime[ odd prime sum ] |
|||
ELSE |
|||
print( ( "Need more primes: ", whole( odd prime sum, 0 ), newline ) ); |
|||
FALSE |
|||
FI |
|||
THEN |
|||
print( ( whole( i, -3 ), " ", whole( low prime[ i ], -4 ), " ", whole( odd prime sum, -6 ), newline ) ) |
|||
FI |
|||
OD |
|||
END</lang> |
|||
{{out}} |
|||
<pre> |
|||
i p[i] sum |
|||
1 2 2 |
|||
3 5 7 |
|||
11 31 89 |
|||
27 103 659 |
|||
35 149 1181 |
|||
67 331 5021 |
|||
91 467 9923 |
|||
95 499 10909 |
|||
99 523 11941 |
|||
119 653 17959 |
|||
143 823 26879 |
|||
</pre> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
Revision as of 10:00, 5 September 2021
- Task
Let p(i) be a sequence of prime numbers.
Consider the p(1),p(3),p(5), ... ,p(i), for each p(i) < 1,000 and i is odd.
Let sum be the sum of these primes.
If sum is prime then print i, p(i) and sum.
ALGOL 68
<lang algol68>BEGIN # find primes (up to 999) p(i) for odd i such that the sum of primes p(j), j = 1, 3, 5, ..., i is prime #
INT max prime = 999; PR read "primes.incl.a68" PR []BOOL prime = PRIMESIEVE 50 000; # guess that the max sum will be <= 50 000 # # count the primes up to max prime # INT p count := 0; FOR i TO max prime DO IF prime[ i ] THEN p count +:= 1 FI OD; # construct a list of the primes up to max prime # [ 1 : p count ]INT low prime; INT low pos := 0; FOR i TO max prime DO IF prime[ i ] THEN low prime[ low pos +:= 1 ] := i FI OD; # find the sums of the odd primes and test for primality # print( ( " i p[i] sum", newline ) ); INT odd prime sum := 0; FOR i BY 2 TO UPB low prime DO IF odd prime sum +:= low prime[ i ]; IF odd prime sum <= UPB prime THEN prime[ odd prime sum ] ELSE print( ( "Need more primes: ", whole( odd prime sum, 0 ), newline ) ); FALSE FI THEN print( ( whole( i, -3 ), " ", whole( low prime[ i ], -4 ), " ", whole( odd prime sum, -6 ), newline ) ) FI OD
END</lang>
- Output:
i p[i] sum 1 2 2 3 5 7 11 31 89 27 103 659 35 149 1181 67 331 5021 91 467 9923 95 499 10909 99 523 11941 119 653 17959 143 823 26879
Factor
<lang factor>USING: assocs assocs.extras kernel math.primes math.statistics prettyprint sequences.extras ;
1000 primes-upto <evens> dup cum-sum zip [ prime? ] filter-values .</lang>
- Output:
{ { 2 2 } { 5 7 } { 31 89 } { 103 659 } { 149 1181 } { 331 5021 } { 467 9923 } { 499 10909 } { 523 11941 } { 653 17959 } { 823 26879 } }
Go
<lang go>package main
import (
"fmt" "rcu"
)
func main() {
primes := rcu.Primes(999) sum := 0 fmt.Println(" i p[i] Σp[i]") fmt.Println("----------------") for i := 0; i < len(primes); i += 2 { sum += primes[i] if rcu.IsPrime(sum) { fmt.Printf("%3d %3d %6s\n", i+1, primes[i], rcu.Commatize(sum)) } }
}</lang>
- Output:
i p[i] Σp[i] ---------------- 1 2 2 3 5 7 11 31 89 27 103 659 35 149 1,181 67 331 5,021 91 467 9,923 95 499 10,909 99 523 11,941 119 653 17,959 143 823 26,879
jq
Works with gojq, the Go implementation of jq See e.g. Erdős-primes#jq for a suitable implementation of `is_prime`.
<lang jq>def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
def task:
[2, (range(3;1000;2)|select(is_prime))] | [.[range(0;length;2)]] | . as $oddPositionPrimes | foreach range(0; length) as $i ({i: -1}; .i += 2 | .sum += $oddPositionPrimes[$i]; select(.sum|is_prime) | "\(.i|lpad(3)) \($oddPositionPrimes[$i]|lpad(3)) \(.sum|lpad(5))" ) ;
" i p[$i] sum", task</lang>
- Output:
i p[$i] sum 1 2 2 3 5 7 11 31 89 27 103 659 35 149 1181 67 331 5021 91 467 9923 95 499 10909 99 523 11941 119 653 17959 143 823 26879
Julia
<lang julia>using Primes p = primes(1000) arr = filter(n -> isprime(n[2]), accumulate((x, y) -> (y, x[2] + y), p[1:2:length(p)], init = (0, 0))) println(join(arr, "\n"))
</lang>
- Output:
(2, 2) (5, 7) (31, 89) (103, 659) (149, 1181) (331, 5021) (467, 9923) (499, 10909) (523, 11941) (653, 17959) (823, 26879)
Nim
<lang Nim>import strformat
template isOdd(n: Natural): bool = (n and 1) != 0 template isEven(n: Natural): bool = (n and 1) == 0
func isPrime(n: Positive): bool =
if n == 1: return false if n.isEven: return n == 2 if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false inc d, 2 if n mod d == 0: return false inc d, 4 result = true
- Compute the sums of primes at odd position.
echo " i p(i) sum" var idx = 0 var sum = 0 var p = 1 while p < 1000:
inc p if p.isPrime: inc idx if idx.isOdd: inc sum, p if sum.isPrime: echo &"{idx:3} {p:3} {sum:5}"</lang>
- Output:
i p(i) sum 1 2 2 3 5 7 11 31 89 27 103 659 35 149 1181 67 331 5021 91 467 9923 95 499 10909 99 523 11941 119 653 17959 143 823 26879
Perl
<lang perl>use strict; use warnings; use ntheory 'is_prime';
my $c; my @odd = grep { 0 != ++$c % 2 } grep { is_prime $_ } 2 .. 999; my @sums = $odd[0]; push @sums, $sums[-1] + $_ for @odd[1..$#odd];
$c = 1; for (0..$#sums) {
printf "%6d%6d%6d\n", $c, $odd[$_], $sums[$_] if is_prime $sums[$_]; $c += 2;
}</lang>
- Output:
1 2 2 3 5 7 11 31 89 27 103 659 35 149 1181 67 331 5021 91 467 9923 95 499 10909 99 523 11941 119 653 17959 143 823 26879
Phix
with javascript_semantics sequence primes = get_primes_le(1000) integer total = 0 printf(1," i p sum\n") printf(1,"----------------\n") for i=1 to length(primes) by 2 do total += primes[i] if is_prime(total) then printf(1,"%3d %3d %,6d\n", {i, primes[i], total}) end if end for
- Output:
i p sum ---------------- 1 2 2 3 5 7 11 31 89 27 103 659 35 149 1,181 67 331 5,021 91 467 9,923 95 499 10,909 99 523 11,941 119 653 17,959 143 823 26,879
Raku
<lang perl6>my @odd = grep { ++$ !%% 2 }, grep &is-prime, 2 ..^ 1000; my @sums = [\+] @odd;
say .fmt('%5d') for grep { .[2].is-prime }, ( (1,3…*) Z @odd Z @sums );</lang>
- Output:
1 2 2 3 5 7 11 31 89 27 103 659 35 149 1181 67 331 5021 91 467 9923 95 499 10909 99 523 11941 119 653 17959 143 823 26879
REXX
<lang REXX>/*REXX pgm shows a prime index, the prime, & sum of odd indexed primes when sum is prime*/ parse arg hi . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 1000 /*Not specified? Then use the default.*/ call genP /*build array of semaphores for primes.*/
title= 'odd indexed primes the sum of the odd indexed primes'
say ' index │'center(title, 65) say '───────┼'center("" , 65, '─') found= 0 /*initialize # of odd indexed primes···*/ $= 0 /*sum of odd indexed primes (so far). */
do j=1 by 2; p= @.j; if p>hi then leave /*find odd indexed primes, sum = prime.*/ $= $ + p /*add this odd index prime to the sum. */ if \!.$ then iterate /*This sum not prime? Then skip it. */ found= found + 1 /*bump the number of solutions found. */ say center(j, 7)'│' right( commas(p), 13) right( commas($), 33) end /*j*/
say '───────┴'center("" , 65, '─') say say 'Found ' commas(found) ' 'subword(title, 1, 3) exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " semaphores. */ #=5; sq.#= @.# ** 2 /*number of primes so far; prime². */ do j=@.#+2 by 2 to hi*33; parse var j -1 _ /*obtain the last decimal dig.*/ if _==5 then iterate; if j//3==0 then iterate; if j//7==0 then iterate do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/ if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; sq.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
index │ odd indexed primes the sum of the odd indexed primes ───────┼───────────────────────────────────────────────────────────────── 1 │ 2 2 3 │ 5 7 11 │ 31 89 27 │ 103 659 35 │ 149 1,181 67 │ 331 5,021 91 │ 467 9,923 95 │ 499 10,909 99 │ 523 11,941 119 │ 653 17,959 143 │ 823 26,879 ───────┴───────────────────────────────────────────────────────────────── Found 11 odd indexed primes
Ring
<lang ring> load "stdlib.ring" see "working..." + nl see "i p sum" + nl
nr = 0 sum = 0 limit = 1000
for n = 2 to limit
if isprime(n) nr++ if nr%2 = 1 sum += n if isprime(sum) see "" + nr + " " + n + " " + sum + nl ok ok ok
next
see "done..." + nl </lang>
- Output:
working... i p sum 1 2 2 3 5 7 11 31 89 27 103 659 35 149 1181 67 331 5021 91 467 9923 95 499 10909 99 523 11941 119 653 17959 143 823 26879 done...
Wren
<lang ecmascript>import "/math" for Int import "/trait" for Indexed import "/fmt" for Fmt
var primes = Int.primeSieve(999) var sum = 0 System.print(" i p[i] Σp[i]") System.print("----------------") for (se in Indexed.new(primes, 2)) {
sum = sum + se.value if (Int.isPrime(sum)) Fmt.print("$3d $3d $,6d", se.index + 1, se.value, sum)
}</lang>
- Output:
i p[i] Σp[i] ---------------- 1 2 2 3 5 7 11 31 89 27 103 659 35 149 1,181 67 331 5,021 91 467 9,923 95 499 10,909 99 523 11,941 119 653 17,959 143 823 26,879
XPL0
<lang XPL0>func IsPrime(N); \Return 'true' if N is a prime number int N, I; [if N <= 1 then return false; for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true; ];
int I, Sum, N; [Text(0, "p(n) sum^m^j"); Sum:= 0; I:= 0; for N:= 2 to 1000-1 do
[if IsPrime(N) then [I:= I+1; if I&1 then \odd [Sum:= Sum + N; if IsPrime(Sum) then [IntOut(0, N); ChOut(0, ^ ); IntOut(0, Sum); CrLf(0)]; ]; ]; ];
]</lang>
- Output:
p(n) sum 2 2 5 7 31 89 103 659 149 1181 331 5021 467 9923 499 10909 523 11941 653 17959 823 26879