Numbers whose binary and ternary digit sums are prime: Difference between revisions
m (→{{header|REXX}}: added comments.) |
(Added Sidef) |
||
Line 1,281: | Line 1,281: | ||
Found 61 such numbers |
Found 61 such numbers |
||
done... |
done... |
||
</pre> |
|||
=={{header|Sidef}}== |
|||
<lang ruby>1..^200 -> grep {|n| [2,3].all { n.sumdigits(_).is_prime } }</lang> |
|||
{{out}} |
|||
<pre> |
|||
[5, 6, 7, 10, 11, 12, 13, 17, 18, 19, 21, 25, 28, 31, 33, 35, 36, 37, 41, 47, 49, 55, 59, 61, 65, 67, 69, 73, 79, 82, 84, 87, 91, 93, 97, 103, 107, 109, 115, 117, 121, 127, 129, 131, 133, 137, 143, 145, 151, 155, 157, 162, 167, 171, 173, 179, 181, 185, 191, 193, 199] |
|||
</pre> |
</pre> |
||
Revision as of 22:26, 5 July 2021
- Task
Show positive integers whose binary and ternary digits sum are prime, where n < 200
ALGOL 68
<lang algol68>BEGIN # find numbers whose digit sums in binary and ternary are prime #
# reurns a sieve of primes up to n # PROC sieve = ( INT n )[]BOOL: BEGIN [ 1 : n ]BOOL p; p[ 1 ] := FALSE; p[ 2 ] := TRUE; FOR i FROM 3 BY 2 TO n DO p[ i ] := TRUE OD; FOR i FROM 4 BY 2 TO n DO p[ i ] := FALSE OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO IF p[ i ] THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := FALSE OD FI OD; p END # prime list # ; # returns the digit sum of n in base b # PRIO DIGITSUM = 9; OP DIGITSUM = ( INT n, b )INT: BEGIN INT d sum := 0; INT v := ABS n; WHILE v > 0 DO d sum +:= v MOD b; v OVERAB b OD; d sum END # DIGITSUM # ; INT max number = 200; []BOOL prime = sieve( max number ); INT n count := 0; FOR n TO max number DO INT d sum 2 = n DIGITSUM 2; IF prime[ d sum 2 ] THEN INT d sum 3 = n DIGITSUM 3; IF prime[ d sum 3 ] THEN # the base 2 and base 3 digit sums of n are both prime # print( ( " ", whole( n, -3 ), IF prime[ n ] THEN "*" ELSE " " FI ) ); n count +:= 1; IF n count MOD 14 = 0 THEN print( ( newline ) ) FI FI FI OD; print( ( newline ) ); print( ( "Found ", whole( n count, 0 ), " numbers whose binary and ternary digit sums are prime", newline ) ); print( ( " those that are themselves prime are suffixed with a ""*""", newline ) )
END</lang>
- Output:
5* 6 7* 10 11* 12 13* 17* 18 19* 21 25 28 31* 33 35 36 37* 41* 47* 49 55 59* 61* 65 67* 69 73* 79* 82 84 87 91 93 97* 103* 107* 109* 115 117 121 127* 129 131* 133 137* 143 145 151* 155 157* 162 167* 171 173* 179* 181* 185 191* 193* 199* Found 61 numbers whose binary and ternary digit sums are prime those that are themselves prime are suffixed with a "*"
ALGOL-M
<lang algolm>begin integer function mod(a,b); integer a,b; mod := a-(a/b)*b;
integer function digitsum(n,base); integer n,base; digitsum := if n=0 then 0 else mod(n,base)+digitsum(n/base,base);
integer function isprime(n); integer n; begin
integer i; isprime := 0; if n < 2 then go to stop; for i := 2 step 1 until n-1 do begin if mod(n,i) = 0 then go to stop; end; isprime := 1;
stop:
i := i;
end;
integer i,d2,d3,n; n := 0; for i := 0 step 1 until 199 do begin
d2 := digitsum(i,2); d3 := digitsum(i,3); if isprime(d2) <> 0 and isprime(d3) <> 0 then begin if n/10 <> (n-1)/10 then write(i) else writeon(i); n := n + 1; end;
end; end</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
ALGOL W
<lang algolw>begin % find numbers whose binary and ternary digit sums are prime %
% returns the digit sum of n in base b % integer procedure digitSum( integer value n, base ) ; begin integer v, dSum; v := abs n; dSum := 0; while v > 0 do begin dSum := dSum + v rem base; v := v div base end while_v_gt_0 ; dSum end digitSum ; integer MAX_PRIME, MAX_NUMBER; MAX_PRIME := 199; begin logical array prime( 1 :: MAX_PRIME ); integer nCount; % sieve the primes to MAX_PRIME % prime( 1 ) := false; prime( 2 ) := true; for i := 3 step 2 until MAX_PRIME do prime( i ) := true; for i := 4 step 2 until MAX_PRIME do prime( i ) := false; for i := 3 step 2 until truncate( sqrt( MAX_PRIME ) ) do begin integer ii; ii := i + i; if prime( i ) then for np := i * i step ii until MAX_PRIME do prime( np ) := false end for_i ; % find the numbers % nCount := 0; for i := 1 until MAX_PRIME do begin if prime( digitSum( i, 2 ) ) and prime( digitSum( i, 3 ) ) then begin % have another matching number % writeon( i_w := 3, s_w := 0, " ", i ); nCount := nCount + 1; if nCount rem 14 = 0 then write() end if_have_a_suitable_number end for_i ; write( i_w := 1, s_w := 0, "Found ", nCount, " numbers with prime binary and ternary digit sums up to ", MAX_PRIME ) end
end.</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199 Found 61 numbers with prime binary and ternary digit sums up to 199
APL
<lang APL>(⊢(/⍨)(∧/((2=0+.=⍳|⊢)¨2 3(+/⊥⍣¯1)¨⊢))¨) ⍳200</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
Arturo
<lang rebol>loop split.every: 10
select 1..199 'n [ and? prime? sum digits.base: 2 n prime? sum digits.base: 3 n ] 'a -> print map a => [pad to :string & 4]</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
AWK
<lang AWK>
- syntax: GAWK -f NUMBERS_WHICH_BINARY_AND_TERNARY_DIGIT_SUM_ARE_PRIME.AWK
- converted from C
BEGIN {
start = 0 stop = 199 for (i=start; i<=stop; i++) { if (is_prime(sum_digits(i,2)) && is_prime(sum_digits(i,3))) { printf("%4d%1s",i,++count%10?"":"\n") } } printf("\nBinary and ternary digit sums are both prime %d-%d: %d\n",start,stop,count) exit(0)
} function sum_digits(n,base, sum) {
do { sum += n % base } while (n = int(n/base)) return(sum)
} 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)
} </lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199 Binary and ternary digit sums are both prime 0-199: 61
BASIC
None of the digit sums are higher than 9, so the easiest thing to do is to hardcode which ones are prime.
<lang BASIC>10 DEFINT I,J,K,P 20 DIM P(9): DATA 0,1,1,0,1,0,1,0,0 30 FOR I=1 TO 9: READ P(I): NEXT 40 FOR I=0 TO 199 50 J=0: K=I 60 IF K>0 THEN J=J+K MOD 2: K=K\2: GOTO 60 ELSE IF P(J)=0 THEN 90 70 J=0: K=I 80 IF K>0 THEN J=J+K MOD 3: K=K\3: GOTO 80 ELSE IF P(J) THEN PRINT I, 90 NEXT I</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
BCPL
<lang bcpl>get "libhdr"
let digitsum(n, base) =
n=0 -> 0, n rem base + digitsum(n/base, base)
let isprime(n) = valof $( if n<2 then resultis false
for i=2 to n-1 do if n rem i = 0 then resultis false resultis true
$)
let accept(n) =
isprime(digitsum(n,2)) & isprime(digitsum(n,3))
let start() be $( let c = 0
for i=0 to 199 do if accept(i) do $( writef("%I4",i) c := c + 1 if c rem 10 = 0 then wrch('*N') $) wrch('*N')
$)</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
C
<lang c>#include <stdio.h>
- include <stdint.h>
/* good enough for small numbers */ uint8_t prime(uint8_t n) {
uint8_t f; if (n < 2) return 0; for (f = 2; f < n; f++) { if (n % f == 0) return 0; } return 1;
}
/* digit sum in given base */ uint8_t digit_sum(uint8_t n, uint8_t base) {
uint8_t s = 0; do {s += n % base;} while (n /= base); return s;
}
int main() {
uint8_t n, s = 0; for (n = 0; n < 200; n++) { if (prime(digit_sum(n,2)) && prime(digit_sum(n,3))) { printf("%4d",n); if (++s>=10) { printf("\n"); s=0; } } } printf("\n"); return 0;
}</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
Cowgol
<lang cowgol>include "cowgol.coh";
sub prime(n: uint8): (p: uint8) is
p := 0; if n >= 2 then var f: uint8 := 2; while f < n loop if n % f == 0 then return; end if; f := f + 1; end loop; p := 1; end if;
end sub;
sub digit_sum(n: uint8, base: uint8): (sum: uint8) is
sum := 0; while n > 0 loop sum := sum + n % base; n := n / base; end loop;
end sub;
var n: uint8 := 0; while n < 200 loop;
if prime(digit_sum(n,2)) != 0 and prime(digit_sum(n,3)) != 0 then print_i8(n); print_nl(); end if; n := n + 1;
end loop;</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // binary and ternary digit sums are prime: Nigel Galloway. April 16th., 2021 let fN2,fN3=let rec fG n g=function l when l<n->l+g |l->fG n (g+l%n)(l/n) in (fG 2 0, fG 3 0) {0..200}|>Seq.filter(fun n->isPrime(fN2 n) && isPrime(fN3 n))|>Seq.iter(printf "%d "); printfn "" </lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199 Real: 00:00:00.005
Factor
<lang factor>USING: combinators combinators.short-circuit formatting io lists lists.lazy math math.parser math.primes sequences ;
- dsum ( n base -- sum ) >base [ digit> ] map-sum ;
- dprime? ( n base -- ? ) dsum prime? ;
- 23prime? ( n -- ? ) { [ 2 dprime? ] [ 3 dprime? ] } 1&& ;
- l23primes ( -- list ) 1 lfrom [ 23prime? ] lfilter ;
- 23prime. ( n -- )
{ [ ] [ >bin ] [ 2 dsum ] [ 3 >base ] [ 3 dsum ] } cleave "%-8d %-9s %-6d %-7s %d\n" printf ;
"Base 10 Base 2 (sum) Base 3 (sum)" print l23primes [ 200 < ] lwhile [ 23prime. ] leach</lang>
- Output:
Base 10 Base 2 (sum) Base 3 (sum) 5 101 2 12 3 6 110 2 20 2 7 111 3 21 3 10 1010 2 101 2 11 1011 3 102 3 12 1100 2 110 2 13 1101 3 111 3 17 10001 2 122 5 18 10010 2 200 2 19 10011 3 201 3 21 10101 3 210 3 25 11001 3 221 5 28 11100 3 1001 2 31 11111 5 1011 3 33 100001 2 1020 3 35 100011 3 1022 5 36 100100 2 1100 2 37 100101 3 1101 3 41 101001 3 1112 5 47 101111 5 1202 5 49 110001 3 1211 5 55 110111 5 2001 3 59 111011 5 2012 5 61 111101 5 2021 5 65 1000001 2 2102 5 67 1000011 3 2111 5 69 1000101 3 2120 5 73 1001001 3 2201 5 79 1001111 5 2221 7 82 1010010 3 10001 2 84 1010100 3 10010 2 87 1010111 5 10020 3 91 1011011 5 10101 3 93 1011101 5 10110 3 97 1100001 3 10121 5 103 1100111 5 10211 5 107 1101011 5 10222 7 109 1101101 5 11001 3 115 1110011 5 11021 5 117 1110101 5 11100 3 121 1111001 5 11111 5 127 1111111 7 11201 5 129 10000001 2 11210 5 131 10000011 3 11212 7 133 10000101 3 11221 7 137 10001001 3 12002 5 143 10001111 5 12022 7 145 10010001 3 12101 5 151 10010111 5 12121 7 155 10011011 5 12202 7 157 10011101 5 12211 7 162 10100010 3 20000 2 167 10100111 5 20012 5 171 10101011 5 20100 3 173 10101101 5 20102 5 179 10110011 5 20122 7 181 10110101 5 20201 5 185 10111001 5 20212 7 191 10111111 7 21002 5 193 11000001 3 21011 5 199 11000111 5 21101 5
FOCAL
<lang focal>01.10 S P(2)=1;S P(3)=1;S P(5)=1;S P(7)=1 01.20 S V=10 01.30 F N=0,199;D 3 01.40 T ! 01.50 Q
02.10 S A=0 02.20 S M=N 02.30 S T=FITR(M/B) 02.40 S A=A+M-T*B 02.50 S M=T 02.60 I (-M)2.3
03.10 S B=2;D 2;S X=A 03.20 S B=3;D 2;S Y=A 03.30 I (-P(X)*P(Y))3.4;R 03.40 T %4,N 03.50 S V=V-1 03.60 I (-V)3.7;T !;S V=10 03.70 R</lang>
- Output:
= 5= 6= 7= 10= 11= 12= 13= 17= 18= 19 = 21= 25= 28= 31= 33= 35= 36= 37= 41= 47 = 49= 55= 59= 61= 65= 67= 69= 73= 79= 82 = 84= 87= 91= 93= 97= 103= 107= 109= 115= 117 = 121= 127= 129= 131= 133= 137= 143= 145= 151= 155 = 157= 162= 167= 171= 173= 179= 181= 185= 191= 193 = 199
Go
<lang go>package main
import (
"fmt" "rcu"
)
func main() {
var numbers []int for i := 2; i < 200; i++ { bds := rcu.DigitSum(i, 2) if rcu.IsPrime(bds) { tds := rcu.DigitSum(i, 3) if rcu.IsPrime(tds) { numbers = append(numbers, i) } } } fmt.Println("Numbers < 200 whose binary and ternary digit sums are prime:") for i, n := range numbers { fmt.Printf("%4d", n) if (i+1)%14 == 0 { fmt.Println() } } fmt.Printf("\n\n%d such numbers found\n", len(numbers))
}</lang>
- Output:
Numbers < 200 whose binary and ternary digit sums are prime: 5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199 61 such numbers found
Haskell
<lang haskell>import Data.Bifunctor (first) import Data.List.Split (chunksOf) import Data.Numbers.Primes (isPrime)
BINARY AND TERNARY DIGIT SUMS BOTH PRIME -------
digitSumsPrime :: Int -> [Int] -> Bool digitSumsPrime n = all (isPrime . digitSum n)
digitSum :: Int -> Int -> Int digitSum n base = go n
where go 0 = 0 go n = uncurry (+) (first go $ quotRem n base)
TEST -------------------------
main :: IO () main =
putStrLn $ show (length xs) <> " matches in [1..199]\n\n" <> table xs where xs = [1 .. 199] >>= \x -> [show x | digitSumsPrime x [2, 3]]
DISPLAY -----------------------
table :: [String] -> String table xs =
let w = length (last xs) in unlines $ unwords <$> chunksOf 10 (justifyRight w ' ' <$> xs)
justifyRight :: Int -> Char -> String -> String justifyRight n c = (drop . length) <*> (replicate n c <>)</lang>
61 matches in [1..199] 5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
J
<lang J>((1*./@p:2 3+/@(#.^:_1)"0])"0#]) i.200</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
Julia
<lang julia>using Primes
btsumsareprime(n) = isprime(sum(digits(n, base=2))) && isprime(sum(digits(n, base=3)))
foreach(p -> print(rpad(p[2], 4), p[1] % 20 == 0 ? "\n" : ""), enumerate(filter(btsumsareprime, 1:199)))
</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
MAD
<lang mad> NORMAL MODE IS INTEGER
INTERNAL FUNCTION(P) ENTRY TO PRIME. WHENEVER P.L.2, FUNCTION RETURN 0B THROUGH TEST, FOR DV=2, 1, DV.G.SQRT.(P)
TEST WHENEVER P-P/DV*DV.E.0, FUNCTION RETURN 0B
FUNCTION RETURN 1B END OF FUNCTION INTERNAL FUNCTION(N,BASE) ENTRY TO DGTSUM. SUM = 0 DN = N
DIGIT NX = DN/BASE
SUM = SUM + DN-NX*BASE DN = NX WHENEVER DN.G.0, TRANSFER TO DIGIT FUNCTION RETURN SUM END OF FUNCTION THROUGH NBR, FOR I=0, 1, I.GE.200 WHENEVER PRIME.(DGTSUM.(I,2)) .AND. PRIME.(DGTSUM.(I,3)) PRINT FORMAT FMT, I END OF CONDITIONAL
NBR CONTINUE
VECTOR VALUES FMT = $I3*$ END OF PROGRAM </lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
Nim
<lang Nim>import strutils
func isPrime(n: Positive): bool =
if n == 1: return false if n mod 2 == 0: 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 return true
func digitSum(n, b: Natural): int =
var n = n while n != 0: result += n mod b n = n div b
var count = 0 for n in 2..<200:
if digitSum(n, 2).isPrime and digitSum(n, 3).isPrime: inc count stdout.write ($n).align(3), if count mod 16 == 0: '\n' else: ' '
echo() echo "Found ", count, " numbers."</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199 Found 61 numbers.
Perl
<lang perl>use strict; use warnings; use feature 'say'; use List::Util 'sum'; use ntheory <is_prime todigitstring>;
sub test_digits { 0 != is_prime sum split , todigitstring(shift, shift) }
my @p; test_digits($_,2) and test_digits($_,3) and push @p, $_ for 1..199; say my $result = @p . " matching numbers:\n" . (sprintf "@{['%4d' x @p]}", @p) =~ s/(.{40})/$1\n/gr;</lang>
- Output:
61 matching numbers: 5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
PL/M
<lang plm>100H: /* CP/M CALLS */ BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS; EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT; PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
/* PRINT NUMBER */ PRINT$NUMBER: PROCEDURE (N);
DECLARE S (8) BYTE INITIAL ('.....',13,10,'$'); DECLARE (N, P) ADDRESS, C BASED P BYTE; P = .S(5);
DIGIT:
P = P - 1; C = N MOD 10 + '0'; N = N / 10; IF N > 0 THEN GO TO DIGIT; CALL PRINT(P);
END PRINT$NUMBER;
/* SIMPLE PRIMALITY TEST */ PRIME: PROCEDURE (N) BYTE;
DECLARE (N, I) BYTE; IF N < 2 THEN RETURN 0; DO I=2 TO N-1; IF N MOD I = 0 THEN RETURN 0; END; RETURN 1;
END PRIME;
/* SUM OF DIGITS */ DIGIT$SUM: PROCEDURE (N, BASE) BYTE;
DECLARE (N, BASE, SUM) BYTE; SUM = 0; DO WHILE N > 0; SUM = SUM + N MOD BASE; N = N / BASE; END; RETURN SUM;
END DIGIT$SUM;
/* TEST NUMBERS 0 .. 199 */ DECLARE I BYTE; DO I=0 TO 199;
IF PRIME(DIGIT$SUM(I,2)) AND PRIME(DIGIT$SUM(I,3)) THEN CALL PRINT$NUMBER(I);
END;
CALL EXIT; EOF</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
Plain English
<lang plainenglish>To run: Start up. Loop. If a counter is past 200, break. If the counter has prime digit sums in binary and ternary, write the counter then " " on the console without advancing. Repeat. Wait for the escape key. Shut down.
A sum is a number.
A base is a number.
To find a digit sum of a number given a base: Privatize the number. Loop. Divide the number by the base giving a quotient and a remainder. Add the remainder to the digit sum. Put the quotient into the number. If the number is 0, exit. Repeat.
To decide if a number has prime digit sums in binary and ternary: Find a digit sum of the number given 2. If the digit sum is not prime, say no. Find another digit sum of the number given 3. If the other digit sum is not prime, say no. Say yes.</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
Phix
function to_base(atom n, integer base) string result = "" while true do result &= remainder(n,base) n = floor(n/base) if n=0 then exit end if end while return result end function function prime23(integer n) return is_prime(sum(to_base(n,2))) and is_prime(sum(to_base(n,3))) end function sequence res = filter(tagset(199),prime23) printf(1,"%d numbers found: %V\n",{length(res),shorten(res,"",5)})
- Output:
61 numbers found: {5,6,7,10,11,"...",181,185,191,193,199}
Python
<lang python>Binary and Ternary digit sums both prime
- digitSumsPrime :: Int -> [Int] -> Bool
def digitSumsPrime(n):
True if the digits of n in each given base have prime sums. def go(bases): return all( isPrime(digitSum(b)(n)) for b in bases ) return go
- digitSum :: Int -> Int -> Int
def digitSum(base):
The sum of the digits of n in a given base. def go(n): q, r = divmod(n, base) return go(q) + r if n else 0 return go
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Matching integers in the range [1..199] xs = [ str(n) for n in range(1, 200) if digitSumsPrime(n)([2, 3]) ] print(f'{len(xs)} matches in [1..199]\n') print(table(10)(xs))
- ----------------------- GENERIC ------------------------
- chunksOf :: Int -> [a] -> a
def chunksOf(n):
A series of lists of length n, subdividing the contents of xs. Where the length of xs is not evenly divible, the final list will be shorter than n. def go(xs): return ( xs[i:n + i] for i in range(0, len(xs), n) ) if 0 < n else None return go
- isPrime :: Int -> Bool
def isPrime(n):
True if n is prime. if n in (2, 3): return True if 2 > n or 0 == n % 2: return False if 9 > n: return True if 0 == n % 3: return False
def p(x): return 0 == n % x or 0 == n % (2 + x)
return not any(map(p, range(5, 1 + int(n ** 0.5), 6)))
- table :: Int -> [String] -> String
def table(n):
A list of strings formatted as rows of n (right justified) columns. def go(xs): w = len(xs[-1]) return '\n'.join( ' '.join(row) for row in chunksOf(n)([ s.rjust(w, ' ') for s in xs ]) ) return go
- MAIN ---
if __name__ == '__main__':
main()
</lang>
61 matches in [1..199] 5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
Raku
<lang perl6>say (^200).grep(-> $n {all (2,3).map({$n.base($_).comb.sum.is-prime}) }).batch(10)».fmt('%3d').join: "\n";</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199
REXX
<lang rexx>/*REXX program finds and displays integers whose base 2 and base 3 digit sums are prime.*/ parse arg n cols . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 200 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */ title= ' positive integers whose binary and ternary digit sums are prime, N < ' commas(n) if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) /*maybe show title.*/ if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') /*maybe show sep. */ found= 0; idx= 1 /*initialize # of finds and the index. */ $= /*a list of numbers found (so far). */
do j=1 for n-1 /*find #s whose B2 & B3 sums are prime.*/ b2= sumDig( tBase(j, 2) ); if \!.b2 then iterate /*convert to base2, sum digits.*/ /* ◄■■■■■■■■ a filter. */ b3= sumDig( tBase(j, 3) ); if \!.b3 then iterate /* " " base3 " " */ /* ◄■■■■■■■■ a filter. */ found= found + 1 /*bump the number of found integers. */ if cols<1 then iterate /*Only showing the summary? Then skip.*/ $= $ right( commas(j), w) /*add a commatized integer ───► $ list.*/ if found//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), '─') /*show foot sep ? */ say say 'Found ' commas(found) title /*show summary. */ 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 ? sumDig: procedure; parse arg x 1 s 2;do j=2 for length(x)-1;s=s+substr(x,j,1);end;return s /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @= 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
!.=0; do p=1 for words(@); _= word(@, p); !._= 1; end; return
/*──────────────────────────────────────────────────────────────────────────────────────*/ tBase: procedure; parse arg x,toBase; y=; $= 0123456789
do while x>=toBase; y= substr($, x//toBase+1, 1)y; x= x % toBase end /*while*/ return substr($, x+1, 1)y</lang>
- output when using the default inputs:
index │ positive integers whose binary and ternary digit sums are prime, N < 200 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 5 6 7 10 11 12 13 17 18 19 11 │ 21 25 28 31 33 35 36 37 41 47 21 │ 49 55 59 61 65 67 69 73 79 82 31 │ 84 87 91 93 97 103 107 109 115 117 41 │ 121 127 129 131 133 137 143 145 151 155 51 │ 157 162 167 171 173 179 181 185 191 193 61 │ 199 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 61 positive integers whose binary and ternary digit sums are prime, N < 200
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "Numbers < 200 whose binary and ternary digit sums are prime:" + nl
decList = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] baseList = ["0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"]
num = 0 limit = 200
for n = 1 to limit
strBin = decimaltobase(n,2) strTer = decimaltobase(n,3) sumBin = 0 for m = 1 to len(strBin) sumBin = sumBin + number(strBin[m]) next sumTer = 0 for m = 1 to len(strTer) sumTer = sumTer + number(strTer[m]) next if isprime(sumBin) and isprime(sumTer) num = num + 1 see "" + num + ". {" + n + "," + strBin + ":" + sumBin + "," + strTer + ":" + sumTer + "}" + nl ok
next
see "Found " + num + " such numbers" + nl see "done..." + nl
func decimaltobase(nr,base)
binList = [] binary = 0 remainder = 1 while(nr != 0) remainder = nr % base ind = find(decList,remainder) rem = baseList[ind] add(binList,rem) nr = floor(nr/base) end binlist = reverse(binList) binList = list2str(binList) binList = substr(binList,nl,"") return binList
</lang>
- Output:
working... Numbers < 200 whose binary and ternary digit sums are prime: 1. {5,101:2,12:3} 2. {6,110:2,20:2} 3. {7,111:3,21:3} 4. {10,1010:2,101:2} 5. {11,1011:3,102:3} 6. {12,1100:2,110:2} 7. {13,1101:3,111:3} 8. {17,10001:2,122:5} 9. {18,10010:2,200:2} 10. {19,10011:3,201:3} 11. {21,10101:3,210:3} 12. {25,11001:3,221:5} 13. {28,11100:3,1001:2} 14. {31,11111:5,1011:3} 15. {33,100001:2,1020:3} 16. {35,100011:3,1022:5} 17. {36,100100:2,1100:2} 18. {37,100101:3,1101:3} 19. {41,101001:3,1112:5} 20. {47,101111:5,1202:5} 21. {49,110001:3,1211:5} 22. {55,110111:5,2001:3} 23. {59,111011:5,2012:5} 24. {61,111101:5,2021:5} 25. {65,1000001:2,2102:5} 26. {67,1000011:3,2111:5} 27. {69,1000101:3,2120:5} 28. {73,1001001:3,2201:5} 29. {79,1001111:5,2221:7} 30. {82,1010010:3,10001:2} 31. {84,1010100:3,10010:2} 32. {87,1010111:5,10020:3} 33. {91,1011011:5,10101:3} 34. {93,1011101:5,10110:3} 35. {97,1100001:3,10121:5} 36. {103,1100111:5,10211:5} 37. {107,1101011:5,10222:7} 38. {109,1101101:5,11001:3} 39. {115,1110011:5,11021:5} 40. {117,1110101:5,11100:3} 41. {121,1111001:5,11111:5} 42. {127,1111111:7,11201:5} 43. {129,10000001:2,11210:5} 44. {131,10000011:3,11212:7} 45. {133,10000101:3,11221:7} 46. {137,10001001:3,12002:5} 47. {143,10001111:5,12022:7} 48. {145,10010001:3,12101:5} 49. {151,10010111:5,12121:7} 50. {155,10011011:5,12202:7} 51. {157,10011101:5,12211:7} 52. {162,10100010:3,20000:2} 53. {167,10100111:5,20012:5} 54. {171,10101011:5,20100:3} 55. {173,10101101:5,20102:5} 56. {179,10110011:5,20122:7} 57. {181,10110101:5,20201:5} 58. {185,10111001:5,20212:7} 59. {191,10111111:7,21002:5} 60. {193,11000001:3,21011:5} 61. {199,11000111:5,21101:5} Found 61 such numbers done...
Sidef
<lang ruby>1..^200 -> grep {|n| [2,3].all { n.sumdigits(_).is_prime } }</lang>
- Output:
[5, 6, 7, 10, 11, 12, 13, 17, 18, 19, 21, 25, 28, 31, 33, 35, 36, 37, 41, 47, 49, 55, 59, 61, 65, 67, 69, 73, 79, 82, 84, 87, 91, 93, 97, 103, 107, 109, 115, 117, 121, 127, 129, 131, 133, 137, 143, 145, 151, 155, 157, 162, 167, 171, 173, 179, 181, 185, 191, 193, 199]
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt import "/seq" for Lst
var numbers = [] for (i in 2..199) {
var bds = Int.digitSum(i, 2) if (Int.isPrime(bds)) { var tds = Int.digitSum(i, 3) if (Int.isPrime(tds)) numbers.add(i) }
} System.print("Numbers < 200 whose binary and ternary digit sums are prime:") for (chunk in Lst.chunks(numbers, 14)) Fmt.print("$4d", chunk) System.print("\nFound %(numbers.count) such numbers.")</lang>
- Output:
Numbers < 200 whose binary and ternary digit sums are prime: 5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199 Found 61 such numbers.
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; ];
func SumDigits(N, Base); \Return sum of digits in N for Base int N, Base, Sum; [Sum:= 0; repeat N:= N/Base;
Sum:= Sum + rem(0);
until N=0; return Sum; ];
int Count, N; [Count:= 0; for N:= 0 to 200-1 do
if IsPrime(SumDigits(N,2)) & IsPrime(SumDigits(N,3)) then [IntOut(0, N); Count:= Count+1; if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\); ];
CrLf(0); IntOut(0, Count); Text(0, " such numbers found below 200. "); ]</lang>
- Output:
5 6 7 10 11 12 13 17 18 19 21 25 28 31 33 35 36 37 41 47 49 55 59 61 65 67 69 73 79 82 84 87 91 93 97 103 107 109 115 117 121 127 129 131 133 137 143 145 151 155 157 162 167 171 173 179 181 185 191 193 199 61 such numbers found below 200.