I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Nice primes

From Rosetta Code
Nice primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
  1.   Take an positive integer   n
  2.   sumn   is the sum of the decimal digits of   n
  3.   If  sumn's  length is greater than   1   (unity),   repeat step 2 for   n = sumn
  4.   Stop when  sumn's  length is equal to   1   (unity)


If   n   and   sumn   are prime,   then   n   is a   Nice prime

Let     500   <   n   <   1000


Example
       853 (prime)
       8 + 5 + 3 = 16
       1 + 6 = 7 (prime)


Also see



ALGOL W[edit]

begin % find some nice primes - primes whose digital root is prime           %
 % returns the digital root of n in base 10  %
integer procedure digitalRoot( integer value n ) ;
if n = 0 then 0
else begin
integer root;
root := ( abs n ) rem 9;
if root = 0 then 9 else root
end digitalRoot ;
 % sets p( 1 :: n ) to a sieve of primes up to n %
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
begin
p( 1 ) := false; p( 2 ) := true;
for i := 3 step 2 until n do p( i ) := true;
for i := 4 step 2 until n do p( i ) := false;
for i := 3 step 2 until truncate( sqrt( n ) ) do begin
integer ii; ii := i + i;
if p( i ) then for pr := i * i step ii until n do p( pr ) := false
end for_i ;
end Eratosthenes ;
integer MIN_PRIME, MAX_PRIME;
MIN_PRIME := 501;
MAX_PRIME := 999;
 % find the nice primes in the exclusive range 500 < prime < 1000 %
begin
logical array p ( 1 :: MAX_PRIME );
integer nCount;
 % construct a sieve of primes up to the maximum required  %
Eratosthenes( p, MAX_PRIME );
 % show the primes that are nice  %
write( i_w := 1, s_w := 0, "Nice primes from ", MIN_PRIME, " to ", MAX_PRIME );
for i := MIN_PRIME until MAX_PRIME do begin
if p( i ) then begin
integer dr;
dr := digitalRoot( i );
if p( dr ) then begin
nCount := nCount + 1;
write( i_w := 3, s_w := 0, nCount, ":", i, " dr(", i_w := 1, dr, ")" )
end if_dr_p
end if_p_i
end for_i
end
end.
 
Output:
Nice primes from 501 to 999
  1:509  dr(5)
  2:547  dr(7)
  3:563  dr(5)
  4:569  dr(2)
  5:587  dr(2)
  6:599  dr(5)
  7:601  dr(7)
  8:617  dr(5)
  9:619  dr(7)
 10:641  dr(2)
 11:653  dr(5)
 12:659  dr(2)
 13:673  dr(7)
 14:677  dr(2)
 15:691  dr(7)
 16:709  dr(7)
 17:727  dr(7)
 18:743  dr(5)
 19:761  dr(5)
 20:797  dr(5)
 21:821  dr(2)
 22:839  dr(2)
 23:853  dr(7)
 24:857  dr(2)
 25:887  dr(5)
 26:907  dr(7)
 27:911  dr(2)
 28:929  dr(2)
 29:941  dr(5)
 30:947  dr(2)
 31:977  dr(5)
 32:983  dr(2)
 33:997  dr(7)

AWK[edit]

 
# syntax: GAWK -f NICE_PRIMES.AWK
BEGIN {
start = 500
stop = 1000
for (i=start; i<=stop; i++) {
if (is_prime(i)) {
s = i
while (s >= 10) {
s = sum_digits(s)
}
if (s ~ /^[2357]$/) {
count++
printf("%d %d\n",i,s)
}
}
}
printf("Nice primes %d-%d: %d\n",start,stop,count)
exit(0)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
function sum_digits(x, sum,y) {
while (x) {
y = x % 10
sum += y
x = int(x/10)
}
return(sum)
}
 
Output:
509 5
547 7
563 5
569 2
587 2
599 5
601 7
617 5
619 7
641 2
653 5
659 2
673 7
677 2
691 7
709 7
727 7
743 5
761 5
797 5
821 2
839 2
853 7
857 2
887 5
907 7
911 2
929 2
941 5
947 2
977 5
983 2
997 7
Nice primes 500-1000: 33

C[edit]

Translation of: C++
#include <stdbool.h>
#include <stdio.h>
 
bool is_prime(unsigned int n) {
if (n < 2) {
return false;
}
if (n % 2 == 0) {
return n == 2;
}
if (n % 3 == 0) {
return n == 3;
}
for (unsigned int p = 5; p * p <= n; p += 4) {
if (n % p == 0) {
return false;
}
p += 2;
if (n % p == 0) {
return false;
}
}
return true;
}
 
unsigned int digital_root(unsigned int n) {
return n == 0 ? 0 : 1 + (n - 1) % 9;
}
 
int main() {
const unsigned int from = 500, to = 1000;
unsigned int count = 0;
unsigned int n;
 
printf("Nice primes between %d and %d:\n", from, to);
for (n = from; n < to; ++n) {
if (is_prime(digital_root(n)) && is_prime(n)) {
++count;
//std::cout << n << (count % 10 == 0 ? '\n' : ' ');
printf("%d", n);
if (count % 10 == 0) {
putc('\n', stdout);
} else {
putc(' ', stdout);
}
}
}
printf("\n%d nice primes found.\n", count);
 
return 0;
}
Output:
Nice primes between 500 and 1000:
509 547 563 569 587 599 601 617 619 641
653 659 673 677 691 709 727 743 761 797
821 839 853 857 887 907 911 929 941 947
977 983 997
33 nice primes found.

C++[edit]

#include <iostream>
 
bool is_prime(unsigned int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (unsigned int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
 
unsigned int digital_root(unsigned int n) {
return n == 0 ? 0 : 1 + (n - 1) % 9;
}
 
int main() {
const unsigned int from = 500, to = 1000;
std::cout << "Nice primes between " << from << " and " << to << ":\n";
unsigned int count = 0;
for (unsigned int n = from; n < to; ++n) {
if (is_prime(digital_root(n)) && is_prime(n)) {
++count;
std::cout << n << (count % 10 == 0 ? '\n' : ' ');
}
}
std::cout << '\n' << count << " nice primes found.\n";
}
Output:
Nice primes between 500 and 1000:
509 547 563 569 587 599 601 617 619 641
653 659 673 677 691 709 727 743 761 797
821 839 853 857 887 907 911 929 941 947
977 983 997 
33 nice primes found.

F#[edit]

This task uses Extensible Prime Generator (F#)

 
// Nice primes. Nigel Galloway: March 22nd., 2021
let fN g=1+((g-1)%9) in primes32()|>Seq.skipWhile((>)500)|>Seq.takeWhile((>)1000)|>Seq.filter(fN>>isPrime)|>Seq.iter(printf "%d "); printfn ""
 
Output:
509 547 563 569 587 599 601 617 619 641 653 659 673 677 691 709 727 743 761 797 821 839 853 857 887 907 911 929 941 947 977 983 997

Factor[edit]

Using the following formula to find the digital root of a base 10 number:

dr10(n) = 0                                 if n = 0,
dr10(n) = 1 + ((n - 1) mod 9)     if n ≠ 0.

(n = 0 may not need to be special-cased depending on the behavior of your language's modulo operator.)

USING: math math.primes prettyprint sequences ;
 
: digital-root ( m -- n ) 1 - 9 mod 1 + ;
 
500 1000 primes-between [ digital-root prime? ] filter .
Output:
V{
    509
    547
    563
    569
    587
    599
    601
    617
    619
    641
    653
    659
    673
    677
    691
    709
    727
    743
    761
    797
    821
    839
    853
    857
    887
    907
    911
    929
    941
    947
    977
    983
    997
}

Forth[edit]

Translation of: Factor
Works with: Gforth
: prime? ( n -- ? ) here + [email protected] 0= ;
: notprime! ( n -- ) here + 1 swap c! ;
 
: prime_sieve ( n -- )
here over erase
0 notprime!
1 notprime!
2
begin
2dup dup * >
while
dup prime? if
2dup dup * do
i notprime!
dup +loop
then
1+
repeat
2drop ;
 
: digital_root ( m -- n ) 1 - 9 mod 1 + ;
 
: print_nice_primes ( m n -- )
." Nice primes between " dup . ." and " over 1 .r ." :" cr
over prime_sieve
0 -rot
do
i prime? if
i digital_root prime? if
i 3 .r
1+ dup 10 mod 0= if cr else space then
then
then
loop
cr . ." nice primes found." cr ;
 
1000 500 print_nice_primes
bye
Output:
Nice primes between 500 and 1000:
509 547 563 569 587 599 601 617 619 641
653 659 673 677 691 709 727 743 761 797
821 839 853 857 887 907 911 929 941 947
977 983 997 
33 nice primes found. 

Go[edit]

Translation of: Wren
package main
 
import "fmt"
 
func isPrime(n int) bool {
switch {
case n < 2:
return false
case n%2 == 0:
return n == 2
case n%3 == 0:
return n == 3
default:
d := 5
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
 
func sumDigits(n int) int {
sum := 0
for n > 0 {
sum += n % 10
n /= 10
}
return sum
}
 
func main() {
fmt.Println("Nice primes in the interval (500, 900) are:")
c := 0
for i := 501; i <= 999; i += 2 {
if isPrime(i) {
s := i
for s >= 10 {
s = sumDigits(s)
}
if s == 2 || s == 3 || s == 5 || s == 7 {
c++
fmt.Printf("%2d: %d -> Σ = %d\n", c, i, s)
}
}
}
}
Output:
Same as Wren example.


J[edit]

   primeQ=: 1&p:
   digital_root=: +/@:(10&#.inv)^:_   NB. sum the digits to convergence
   niceQ=: [: *./ [: primeQ (, digital_root)
   (#~niceQ&>)(+i.)500
509 547 563 569 587 599 601 617 619 641 653 659 673 677 691 709 727 743 761 797 821 839 853 857 887 907 911 929 941 947 977 983 997

   NB. testing only the primes on the range
   p:inv 500 1000  NB. index of the next largest prime in an ordered list of primes
95 168

   (#~ (2 3 5 7 e.~ digital_root&>)) p: 95 + i. 168 - 95
509 547 563 569 587 599 601 617 619 641 653 659 673 677 691 709 727 743 761 797 821 839 853 857 887 907 911 929 941 947 977 983 997

Julia[edit]

See Strange_numbers#Julia for the filter_open_interval function.

using Primes
 
isnice(n, base=10) = isprime(n) && (mod1(n - 1, base - 1) + 1) in [2, 3, 5, 7, 11, 13, 17, 19]
 
filter_open_interval(500, 1000, isnice)
 
Output:
Finding numbers matching isnice for open interval (500, 1000):

509  547  563  569  587  599  601  617  619  641  653  659  673  677  691  709  727  743  
761  797  821  839  853  857  887  907  911  929  941  947  977  983  997

The total found was 33

Kotlin[edit]

Translation of: C
fun isPrime(n: Long): Boolean {
if (n < 2) {
return false
}
if (n % 2 == 0L) {
return n == 2L
}
if (n % 3 == 0L) {
return n == 3L
}
 
var p = 5
while (p * p <= n) {
if (n % p == 0L) {
return false
}
p += 2
if (n % p == 0L) {
return false
}
p += 4
}
return true
}
 
fun digitalRoot(n: Long): Long {
if (n == 0L) {
return 0
}
return 1 + (n - 1) % 9
}
 
fun main() {
val from = 500L
val to = 1000L
var count = 0
 
println("Nice primes between $from and $to:")
var n = from
while (n < to) {
if (isPrime(digitalRoot(n)) && isPrime(n)) {
count += 1
print(n)
if (count % 10 == 0) {
println()
} else {
print(' ')
}
}
 
n += 1
}
println()
println("$count nice primes found.")
}
Output:
Nice primes between 500 and 1000:
509 547 563 569 587 599 601 617 619 641
653 659 673 677 691 709 727 743 761 797
821 839 853 857 887 907 911 929 941 947
977 983 997 
33 nice primes found.

Perl[edit]

Library: ntheory
use strict;
use warnings;
 
use ntheory 'is_prime';
use List::Util qw(sum);
 
sub digital_root {
my ($n) = @_;
do { $n = sum split '', $n } until 1 == length $n;
$n
}
 
my($low, $high, $cnt, @nice_primes) = (500,1000);
is_prime($_) and is_prime(digital_root($_)) and push @nice_primes, $_ for $low+1 .. $high-1;
 
$cnt = @nice_primes;
print "Nice primes between $low and $high (total of $cnt):\n" .
(sprintf "@{['%5d' x $cnt]}", @nice_primes[0..$cnt-1]) =~ s/(.{55})/$1\n/gr;
Output:
Nice primes between 500 and 1000 (total of 33):
  509  547  563  569  587  599  601  617  619  641  653
  659  673  677  691  709  727  743  761  797  821  839
  853  857  887  907  911  929  941  947  977  983  997

Phix[edit]

Translation of: Factor
function pdr(integer n) return is_prime(n) and is_prime(1+remainder(n-1,9)) end function
sequence res = filter(tagset(1000,500),pdr)
printf(1,"%d nice primes found:\n  %s\n",{length(res),join_by(apply(res,sprint),1,11," ","\n ")})
Output:
33 nice primes found:
  509  547  563  569  587  599  601  617  619  641  653
  659  673  677  691  709  727  743  761  797  821  839
  853  857  887  907  911  929  941  947  977  983  997

Raku[edit]

sub digroot ($r) { .tail given $r, { [+] .comb } ... { .chars == 1 } }
my @is-nice = lazy (0..*).map: { .&is-prime && .&digroot.&is-prime ?? $_ !! False };
say @is-nice[500 ^..^ 1000].grep(*.so).batch(11)».fmt("%4d").join: "\n";
Output:
 509  547  563  569  587  599  601  617  619  641  653
 659  673  677  691  709  727  743  761  797  821  839
 853  857  887  907  911  929  941  947  977  983  997

Alternately, with somewhat better separation of concerns.

sub digroot ($r) { ($r, { .comb.sum }{ .chars == 1 }).tail }
sub is-nice ($_) { .is-prime && .&digroot.is-prime }
say (500 ^..^ 1000).grep( *.&is-nice ).batch(11)».fmt("%4d").join: "\n";

Same output.

REXX[edit]

/*REXX program finds and displays  nice primes, primes whose digital root is also prime.*/
parse arg lo hi cols . /*obtain optional argument from the CL.*/
if lo=='' | lo=="," then lo= 500 /*Not specified? Then use the default.*/
if hi=='' | hi=="," then hi= 1000 /* " " " " " " */
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
call genP /*build array of semaphores for primes.*/
w= 10 /*width of a number in any column. */
@nice= ' nice primes that are between ' commas(lo) " and " commas(hi)
if cols>0 then say ' index │'center(@nice ' (not inclusive)', 1 + cols*(w+1) )
if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
Nprimes= 0; idx= 1 /*initialize # of nice primes and index*/
$= /*a list of nice primes (so far). */
do j=lo+1 to hi-1; if \!.j then iterate /*search for nice primes within range*/
digRoot= 1 + (j - 1) // 9 /*obtain the digital root of J. */
if \!.digRoot then iterate /*Is digRoot prime? No, then skip it.*/
Nprimes= Nprimes + 1 /*bump the number of nice primes. */
if cols==0 then iterate /*Build the list (to be shown later)? */
c= commas(j) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add a nice prime ──► list, allow big#*/
if Nprimes//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/
 
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─')
say
say 'Found ' commas(Nprimes) @nice ' (not inclusive).'
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: !.= 0 /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
 !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1 /* " " " " flags. */
#=5; s.#= @.# **2 /*number of primes so far; prime². */
/* [↓] generate more primes ≤ high.*/
do [email protected].#+2 by 2 to hi /*find odd primes from here on. */
parse var j '' -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
/* [↑] the above 3 lines saves time.*/
do k=5 while s.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; s.#= j*j;  !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return
output   when using the default inputs:
 index │                         nice primes that are between  500  and  1,000  (not inclusive)
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │        509        547        563        569        587        599        601        617        619        641
  11   │        653        659        673        677        691        709        727        743        761        797
  21   │        821        839        853        857        887        907        911        929        941        947
  31   │        977        983        997
───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────

Found  33  nice primes that are between  500  and  1,000  (not inclusive).

Ring[edit]

 
load "stdlib.ring"
 
num = 0
limit1 = 500
limit2 = 1000
 
see "working..." + nl
see "Nice numbers are:" + nl
 
for n = limit1 to limit2
strn = string(n)
while true
sumn = 0
for m = 1 to len(strn)
sumn = sumn + number(strn[m])
next
if len(string(sumn)) = 1
exit
ok
strn = string(sumn)
end
if isprime(n) and isprime(sumn)
num = num + 1
see "" + num + ": " + n + " > Σ = " + sumn + nl
ok
next
 
see "done..." + nl
 
Output:
working...
Nice numbers are:
1: 509 > Σ = 5
2: 547 > Σ = 7
3: 563 > Σ = 5
4: 569 > Σ = 2
5: 587 > Σ = 2
6: 599 > Σ = 5
7: 601 > Σ = 7
8: 617 > Σ = 5
9: 619 > Σ = 7
10: 641 > Σ = 2
11: 653 > Σ = 5
12: 659 > Σ = 2
13: 673 > Σ = 7
14: 677 > Σ = 2
15: 691 > Σ = 7
16: 709 > Σ = 7
17: 727 > Σ = 7
18: 743 > Σ = 5
19: 761 > Σ = 5
20: 797 > Σ = 5
21: 821 > Σ = 2
22: 839 > Σ = 2
23: 853 > Σ = 7
24: 857 > Σ = 2
25: 887 > Σ = 5
26: 907 > Σ = 7
27: 911 > Σ = 2
28: 929 > Σ = 2
29: 941 > Σ = 5
30: 947 > Σ = 2
31: 977 > Σ = 5
32: 983 > Σ = 2
33: 997 > Σ = 7
done...

Rust[edit]

Translation of: Factor
// [dependencies]
// primal = "0.3"
 
fn digital_root(n: u64) -> u64 {
if n == 0 {
0
} else {
1 + (n - 1) % 9
}
}
 
fn nice_primes(from: usize, to: usize) {
primal::Sieve::new(to)
.primes_from(from)
.take_while(|x| *x < to)
.filter(|x| primal::is_prime(digital_root(*x as u64)))
.for_each(|x| println!("{}", x));
}
 
fn main() {
nice_primes(500, 1000);
}
Output:
509
547
563
569
587
599
601
617
619
641
653
659
673
677
691
709
727
743
761
797
821
839
853
857
887
907
911
929
941
947
977
983
997

Wren[edit]

Library: Wren-math
Library: Wren-trait
Library: Wren-fmt
import "/math" for Int
import "/trait" for Stepped
import "/fmt" for Fmt
 
var sumDigits = Fn.new { |n|
var sum = 0
while (n > 0) {
sum = sum + (n % 10)
n = (n/10).floor
}
return sum
}
 
System.print("Nice primes in the interval (500, 900) are:")
var c = 0
for (i in Stepped.new(501..999, 2)) {
if (Int.isPrime(i)) {
var s = i
while (s >= 10) s = sumDigits.call(s)
if (Int.isPrime(s)) {
c = c + 1
Fmt.print("$2d: $d -> Σ = $d", c, i, s)
}
}
}
Output:
Nice primes in the interval (500, 900) are:
 1: 509 -> Σ = 5
 2: 547 -> Σ = 7
 3: 563 -> Σ = 5
 4: 569 -> Σ = 2
 5: 587 -> Σ = 2
 6: 599 -> Σ = 5
 7: 601 -> Σ = 7
 8: 617 -> Σ = 5
 9: 619 -> Σ = 7
10: 641 -> Σ = 2
11: 653 -> Σ = 5
12: 659 -> Σ = 2
13: 673 -> Σ = 7
14: 677 -> Σ = 2
15: 691 -> Σ = 7
16: 709 -> Σ = 7
17: 727 -> Σ = 7
18: 743 -> Σ = 5
19: 761 -> Σ = 5
20: 797 -> Σ = 5
21: 821 -> Σ = 2
22: 839 -> Σ = 2
23: 853 -> Σ = 7
24: 857 -> Σ = 2
25: 887 -> Σ = 5
26: 907 -> Σ = 7
27: 911 -> Σ = 2
28: 929 -> Σ = 2
29: 941 -> Σ = 5
30: 947 -> Σ = 2
31: 977 -> Σ = 5
32: 983 -> Σ = 2
33: 997 -> Σ = 7