Nice primes: Difference between revisions
m (changed the OEIS number.) |
m (changed a number.) |
||
Line 20: | Line 20: | ||
;Also see: |
;Also see: |
||
::* The OEIS article: [http://oeis.org/ |
::* The OEIS article: [http://oeis.org/A78403 A78403 Primes such that digital root is prime]. |
||
<br><br> |
<br><br> |
||
Revision as of 20:10, 10 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 ) ; begin integer digits, sum; digits := abs n; while begin sum := 0; while digits > 0 do begin sum := sum + ( digits rem 10 ); digits := digits div 10 end % while digits > 0 % ; sum > 9 end do digits := sum; sum 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)
Factor
<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 }
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.
REXX
<lang rexx>/*REXX program finds/lists triplet strange primes (<HI) where the triplets' sum is prime*/ parse arg lo hi . /*obtain optional argument from the CL.*/ if lo== | lo=="," then lo= 500 /*Not specified? Then use the default.*/ if hi== | hi=="," then hi= 1000 /* " " " " " " */ say 'list of nice primes:' /*display a title for the output list. */ call genP /*build array of semaphores for primes.*/ finds= 0 /*# of triplet strange primes (so far).*/ say
do j=lo+1 to hi-1; if \!.j then iterate /*search for nice primes within range*/ sum= dgRoot(j) /*obtain the digital root of J. */ if \!.sum then iterate /*Is the sum prime? No, then skip it.*/ finds= finds + 1 /*bump the number of nice primes. */ say pad 'decimal digits of ' right(j, w) ' sum to: ' sum end /*j*/
say; @nice= ' nice primes that are between ' say 'Found ' commas(finds) @nice commas(lo) " and " commas(hi) ' (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; pad= left(, 9); w= length(hi) /*placeholders for primes; width of #'s*/
@.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
/*──────────────────────────────────────────────────────────────────────────────────────*/ dgRoot: procedure; parse arg $ 2 x; do length(x); parse var x _ 2 x; $= $ + _
end /*length*/ if length($)>1 then return dgRoot($) return $</lang>
- output when using the default inputs:
list of nice primes: decimal digits of 509 sum to: 5 decimal digits of 547 sum to: 7 decimal digits of 563 sum to: 5 decimal digits of 569 sum to: 2 decimal digits of 587 sum to: 2 decimal digits of 599 sum to: 5 decimal digits of 601 sum to: 7 decimal digits of 617 sum to: 5 decimal digits of 619 sum to: 7 decimal digits of 641 sum to: 2 decimal digits of 653 sum to: 5 decimal digits of 659 sum to: 2 decimal digits of 673 sum to: 7 decimal digits of 677 sum to: 2 decimal digits of 691 sum to: 7 decimal digits of 709 sum to: 7 decimal digits of 727 sum to: 7 decimal digits of 743 sum to: 5 decimal digits of 761 sum to: 5 decimal digits of 797 sum to: 5 decimal digits of 821 sum to: 2 decimal digits of 839 sum to: 2 decimal digits of 853 sum to: 7 decimal digits of 857 sum to: 2 decimal digits of 887 sum to: 5 decimal digits of 907 sum to: 7 decimal digits of 911 sum to: 2 decimal digits of 929 sum to: 2 decimal digits of 941 sum to: 5 decimal digits of 947 sum to: 2 decimal digits of 977 sum to: 5 decimal digits of 983 sum to: 2 decimal digits of 997 sum to: 7 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 = " + sumn + nl ok
next
see "done..." + nl </lang>
- Output:
working... Nice numbers are: 1: 509 sumn = 5 2: 547 sumn = 7 3: 563 sumn = 5 4: 569 sumn = 2 5: 587 sumn = 2 6: 599 sumn = 5 7: 601 sumn = 7 8: 617 sumn = 5 9: 619 sumn = 7 10: 641 sumn = 2 11: 653 sumn = 5 12: 659 sumn = 2 13: 673 sumn = 7 14: 677 sumn = 2 15: 691 sumn = 7 16: 709 sumn = 7 17: 727 sumn = 7 18: 743 sumn = 5 19: 761 sumn = 5 20: 797 sumn = 5 21: 821 sumn = 2 22: 839 sumn = 2 23: 853 sumn = 7 24: 857 sumn = 2 25: 887 sumn = 5 26: 907 sumn = 7 27: 911 sumn = 2 28: 929 sumn = 2 29: 941 sumn = 5 30: 947 sumn = 2 31: 977 sumn = 5 32: 983 sumn = 2 33: 997 sumn = 7 done...
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