Numbers whose binary and ternary digit sums are prime
- Task
- Show numbers which binary and ternary digit 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 "*"
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
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
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
Haskell
<lang haskell>import Data.Bifunctor (first) import Data.List.Split (chunksOf) import Data.Numbers.Primes (isPrime)
BINARY AND TERNARY DIGIT SUMS BOTH PRIME -------
bothDigitSumsPrime :: Int -> Bool bothDigitSumsPrime =
let p base = isPrime . digitSum base in ((&&) . p 3) <*> p 2
digitSum :: Int -> Int -> Int digitSum base = go
where go 0 = 0 go n = uncurry (+) (first go $ quotRem n base)
TEST -------------------------
main :: IO () main =
let xs = [show x | x <- [1 .. 199], bothDigitSumsPrime x] in putStrLn $ show (length xs) <> " matches in [1..199]\n\n" <> table xs
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
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(bases):
True if the digits of n in each given base have prime sums. def test(x): def p(base): return isPrime(digitSum(base)(x)) return p
def go(n): return all( map(test(n), 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([2, 3])(n) ] 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 right-justified rows of n 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 hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 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. */
@b2b3= ' numbers < ' commas(hi) " whose binary and ternary digit sums are prime"
if cols>0 then say ' index │'center(@b2b3, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') finds= 0; idx= 1 /*initialize # of finds and the index. */ $= /*a list of numbers found (so far). */
do j=1 to hi-1 /*find #s whose B2 & B3 sums are prime.*/ b2= sumDig( tBase(j, 2) ); if \!.b2 then iterate /*convert to base2, sum digits*/ b3= sumDig( tBase(j, 3) ); if \!.b3 then iterate /* " " base3 " " */ finds= finds + 1 /*bump the number of found integers. */ 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 an integer ──► $ list, allow big#*/ if finds//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(finds) @b2b3 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: !.=0; @= '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'
#= words(@); do p=1 for #; _= 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 │ numbers < 200 whose binary and ternary digit sums are prime ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 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 numbers < 200 whose binary and ternary digit sums are prime
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...
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.