Nice primes: Difference between revisions
Thundergnat (talk | contribs) →{{header|Raku}}: Alternate |
m →{{header|REXX}}: changed a comment. |
||
Line 513: | Line 513: | ||
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ |
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ |
||
say |
say |
||
say 'Found ' commas(Nprimes) |
say 'Found ' commas(Nprimes) @nice ' (not inclusive).' |
||
exit 0 /*stick a fork in it, we're all done. */ |
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 ? |
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
genP: !.= 0 /*placeholders for primes |
genP: !.= 0 /*placeholders for primes (semaphores).*/ |
||
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ |
@.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. */ |
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ |
Revision as of 18:43, 21 March 2021
- Take an positive integer n
- sumn is the sum of the decimal digits of n
- If sumn's length is greater than 1 (unity), repeat step 2 for n = sumn
- 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
-
- The OEIS article: A78403 Primes such that digital root is prime.
ALGOL W
<lang algolw>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. </lang>
- 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
<lang AWK>
- 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)
} </lang>
- 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++
<lang cpp>#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";
}</lang>
- 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.
Factor
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.)
<lang factor>USING: math math.primes prettyprint sequences ;
- digital-root ( m -- n ) 1 - 9 mod 1 + ;
500 1000 primes-between [ digital-root prime? ] filter .</lang>
- 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
<lang forth>: prime? ( n -- ? ) here + c@ 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</lang>
- 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
<lang go>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) } } }
}</lang>
- Output:
Same as Wren example.
J
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
See Strange_numbers#Julia for the filter_open_interval function. <lang julia>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)
</lang>
- 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
Perl
<lang perl>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;</lang>
- 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
<lang Phix>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 ")})</lang>
- 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
<lang perl6>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";</lang>
- 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. <lang perl6>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";</lang> Same output.
REXX
<lang rexx>/*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.*/ 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 j=@.#+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 five 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</lang>
- 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
<lang ring> 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 </lang>
- 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
<lang rust>// [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);
}</lang>
- 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
<lang ecmascript>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) } }
}</lang>
- 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