Primes with digits in nondecreasing order
- Task
Find n primes with digits in non-decreasing order, where n < 1000
ALGOL 68
<lang algol68>BEGIN # find primes where the digits are non-descending #
INT max number = 1000; # sieve the primes to max number # [ 1 : max number ]BOOL prime; prime[ 1 ] := FALSE; prime[ 2 ] := TRUE; FOR i FROM 3 BY 2 TO max number DO prime[ i ] := TRUE OD; FOR i FROM 4 BY 2 TO max number DO prime[ i ] := FALSE OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( max number ) DO IF prime[ i ] THEN FOR s FROM i * i BY i + i TO max number DO prime[ s ] := FALSE OD FI OD; # we can easily generate candidate numbers with a few nested loops # INT p count := 0; # apart from 1 digit primes, the final digit can only be 1, 3, 7 or 9 # # however we don't optimise that here # FOR h FROM 0 TO 9 DO FOR i FROM h TO 9 DO INT hi = ( h * 10 ) + i; FOR j FROM i TO 9 DO INT hij = ( 10 * hi ) + j; FOR k FROM IF j = 0 THEN 1 ELSE j FI TO 9 WHILE INT hijk = ( hij * 10 ) + k; hijk <= max number DO IF prime[ hijk ] THEN p count +:= 1; print( ( " ", whole( hijk, -6 ) ) ); IF p count MOD 12 = 0 THEN print( ( newline ) ) FI FI OD # k # OD # j # OD # i # OD # h # ; print( ( newline , newline , "Found " , whole( p count, 0 ) , " non-descending primes up to " , whole( max number, 0 ) , newline ) )
END</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Found 50 non-descending primes up to 1000
Arturo
<lang rebol>primes: select 1..1000 => prime? nondecreasing?: function [n][
ds: digits n if 1 = size ds -> return true lastDigit: first ds loop 1..dec size ds 'i [ digit: ds\[i] if digit < lastDigit -> return false lastDigit: digit ]
return true
]
loop split.every: 10 select primes => nondecreasing? 'a ->
print map a => [pad to :string & 4]</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677
AWK
<lang AWK>
- syntax: GAWK -f PRIMES_WITH_DIGITS_IN_NONDECREASING_ORDER.AWK
BEGIN {
start = 1 stop = 1000 for (i=start; i<=stop; i++) { if (is_prime(i)) { flag = 1 for (j=1; j<length(i); j++) { if (substr(i,j,1) > substr(i,j+1,1)) { flag = 0 } } if (flag == 1) { printf("%4d%1s",i,++count%10?"":"\n") } } } printf("\nPrimes with digits in nondecreasing order %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)
} </lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Primes with digits in nondecreasing order 1-1000: 50
C#
The chars array explicitly enforces the case order, not relying on the language's idea of what letters are before or after each other. <lang csharp>using System.Linq; using System.Collections.Generic; using static System.Console; using static System.Math;
class Program {
static int ba; static string chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// convert an int into a string using the current ba static string from10(int b) { string res = ""; int re; while (b > 0) { b = DivRem(b, ba, out re); res = chars[(byte)re] + res; } return res; }
// parse a string into an int, using current ba (not used here) static int to10(string s) { int res = 0; foreach (char i in s) res = res * ba + chars.IndexOf(i); return res; }
// note: comparing the index of the chars instead of the chars themsleves, which avoids case issues static bool nd(string s) { if (s.Length < 2) return true; char l = s[0]; for (int i = 1; i < s.Length; i++) if (chars.IndexOf(l) > chars.IndexOf(s[i])) return false; else l = s[i] ; return true; }
static void Main(string[] args) { int c, lim = 1000; string s; foreach (var b in new List<int>{ 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 17, 27, 31, 62 }) { ba = b; c = 0; foreach (var a in PG.Primes(lim)) if (nd(s = from10(a))) Write("{0,4} {1}", s, ++c % 20 == 0 ? "\n" : ""); WriteLine("\nBase {0}: found {1} non-decreasing primes under {2:n0}\n", b, c, from10(lim)); } } }
class PG { public static IEnumerable<int> Primes(int lim) {
var flags = new bool[lim + 1]; int j; yield return 2; for (j = 4; j <= lim; j += 2) flags[j] = true; j = 3; for (int d = 8, sq = 9; sq <= lim; j += 2, sq += d += 8) if (!flags[j]) { yield return j; for (int k = sq, i = j << 1; k <= lim; k += i) flags[k] = true; } for (; j <= lim; j += 2) if (!flags[j]) yield return j; } }</lang>
- Output:
11 111 11111 1111111 Base 2: found 4 non-decreasing primes under 1111101000 2 12 111 122 1112 1222 Base 3: found 6 non-decreasing primes under 1101001 2 3 11 13 23 113 133 223 233 1223 1333 2333 11123 11233 11333 12233 22223 Base 4: found 17 non-decreasing primes under 33220 2 3 12 23 34 111 122 133 1112 1123 1233 1244 2223 2344 3444 11122 12222 Base 5: found 17 non-decreasing primes under 13000 2 3 5 11 15 25 35 45 111 115 125 135 155 225 245 255 335 345 445 455 1115 1125 1145 1235 1245 1335 1345 1355 1445 1555 2225 2335 2345 2555 3445 3455 3555 Base 6: found 37 non-decreasing primes under 4344 2 3 5 14 16 23 25 56 113 115 124 133 146 155 166 245 256 335 344 346 445 566 1112 1123 1136 1156 1222 1226 1235 1345 1444 1466 2234 2236 2333 2335 2366 2555 Base 7: found 38 non-decreasing primes under 2626 2 3 5 7 13 15 23 27 35 37 45 57 111 117 123 145 147 155 177 225 227 235 247 255 277 337 345 357 445 467 557 577 667 1113 1127 1137 1145 1167 1223 1225 1245 1335 1347 1357 1467 1555 1567 Base 8: found 47 non-decreasing primes under 1750 2 3 5 7 12 14 18 25 34 45 47 58 67 78 117 122 124 128 135 155 177 234 238 267 278 337 344 355 377 447 557 568 667 678 788 1112 1114 1118 1147 1158 1178 1222 1255 1268 1288 Base 9: found 45 non-decreasing primes under 1331 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Base 10: found 50 non-decreasing primes under 1000 2 3 5 7 B D 11 13 17 1D 1F 25 29 2B 2F 35 3B 3D 47 49 4F 59 67 6B 6D 7F 89 8B 9D AD BF DF EF 115 119 11B 125 133 137 139 13D 14B 15B 15D 167 16F 17B 17F 18D 199 1AF 1BB 1CD 1CF 1DF 223 22D 233 239 23B 24B 257 259 25F 269 26B 277 28D 2AB 2BD 2CF 2DD 2EF 335 337 33B 33D 347 355 359 35B 35F 36D 377 38B 38F 3AD 3DF Base 16: found 88 non-decreasing primes under 3E8 2 3 5 7 B D 12 16 1C 1E 23 27 29 2D 38 3A 3G 45 4B 4F 5C 5G 67 6B 78 7C 8D 8F 9A 9E AB BC FG 111 115 117 11B 128 12E 137 139 13D 14A 14G 155 159 15F 166 16A 17B 17D 188 18E 19F 1BB 1BF 1CG 1DD 1EE 1GG 225 227 23C 23E 247 24D 24F 25A 25E 26B 27C 28D 29C 2AD 2CF 33B 346 34C 35F 368 36E 37B Base 17: found 82 non-decreasing primes under 37E 2 3 5 7 B D H J N 12 14 1A 1E 1G 1K 1Q 25 27 2D 2H 2J 2P 38 3G 3K 3M 3Q 45 4J 4N 5E 5G 5M 6B 6H 6J 78 7A 7M 8B 8D 8H 8N 8P 9E 9K 9Q AB AD AN BE BG BK CD CN CP DG DM EJ EN FG FQ GH GP HK IN KN LQ MN MP NQ OP PQ 111 115 11D 11H 124 12E 12Q 13B 13D 13H 13J 14G 14K 14M 14Q 15D 15H 15J 15N 16G 16K 17B 17J 17N 188 18M 18Q 19B 19J 19P Base 27: found 103 non-decreasing primes under 1A1 2 3 5 7 B D H J N T 16 1A 1C 1G 1M 1S 1U 25 29 2B 2H 2L 2R 34 38 3A 3E 3G 3K 47 4D 4F 4P 4R 58 5C 5I 5O 5Q 67 6B 6D 6P 7A 7C 7G 7M 7O 89 8F 8L 8N 8T 9E 9S AL AR BC BI BQ CH CP CT DG DI DS DU EF EN ER ET FM FQ GP GR HK HU IJ IT JO JS JU KL KN KR LM LQ MR NQ NU OP OT TU 115 Base 31: found 94 non-decreasing primes under 118 2 3 5 7 B D H J N T V b f h l r x z 15 19 1B 1H 1L 1R 1Z 1d 1f 1j 1l 1p 23 27 2D 2F 2P 2R 2X 2d 2h 2n 2t 2v 35 37 3B 3D 3P 3b 3f 3h 3l 3r 3t 49 4F 4L 4N 4T 4X 4Z 4j 4x 57 5L 5R 5b 5d 5h 5n 5v 67 6B 6H 6P 6T 6b 6l 6n 6x 6z 79 7F 7N 7R 7T 7X 7j 7r 7v 8D 8P 8R 8j 8p 8z 9B 9D 9J 9T 9Z 9f 9h 9n 9t 9x 9z AB AL AN AR AX Ad Af Ar Av BJ BR Bb Bj Bp Bv Bz CD CH CP CT Ch Cr DF DH DL DN DX Dl Dp Dr Dv EF EJ Ed Eh Ep Ez FH FN Fb Ff Fl Fr Fz Base 62: found 150 non-decreasing primes under G8
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // Primes with digits in nondecreasing order: Nigel Galloway. May 16th., 2021 let rec fN g=function n when n<10->(n<=g) |n when (n%10)<=g->fN(n%10)(n/10) |_->false let fN=fN 9 in primes32()|>Seq.takeWhile((>)1000)|>Seq.filter fN|>Seq.iter(printf "%d "); printfn "" </lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677
Factor
<lang factor>USING: grouping lists lists.lazy math math.primes.lists present prettyprint ;
lprimes [ present [ <= ] monotonic? ] lfilter [ 1000 < ] lwhile [ . ] leach</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677
FreeBASIC
<lang freebasic>#include "isprime.bas"
function is_ndp( byval n as integer ) as boolean
'reads from the least significant digit first dim as integer d=10, ld do ld = d d = n mod 10 if d > ld then return false n = n\10 loop until n = 0 return true
end function
for i as uinteger = 2 to 999
if isprime(i) andalso is_ndp(i) then print i;" ";
next i : print</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677
Julia
Note for the case-sensitive digits base 62 example: Julia defaults to 'A' < 'a' in sorting. So Aa is in order, but aA is not nondecreasing. <lang julia>using Primes
const range = 2:999
for base in [2:10...;[16, 17, 27, 31, 62]]
primes = filter(n -> isprime(n) && issorted(digits(n, base=base), rev=true), range) println("\nBase $base: ", length(primes), " non-descending primes between 1 and ", string(last(primes), base=base), ":") foreach(p -> print(lpad(string(p[2], base=base), 5), p[1] % 16 == 0 ? "\n" : ""), enumerate(primes))
end
</lang>
- Output:
Base 2: 4 non-descending primes between 1 and 1111111: 11 111111111111111 Base 3: 6 non-descending primes between 1 and 1222: 2 12 111 122 1112 1222 Base 4: 17 non-descending primes between 1 and 22223: 2 3 11 13 23 113 133 223 233 1223 1333 233311123112331133312233 22223 Base 5: 17 non-descending primes between 1 and 12222: 2 3 12 23 34 111 122 133 1112 1123 1233 1244 2223 2344 344411122 12222 Base 6: 37 non-descending primes between 1 and 3555: 2 3 5 11 15 25 35 45 111 115 125 135 155 225 245 255 335 345 445 455 1115 1125 1145 1235 1245 1335 1345 1355 1445 1555 2225 2335 2345 2555 3445 3455 3555 Base 7: 38 non-descending primes between 1 and 2555: 2 3 5 14 16 23 25 56 113 115 124 133 146 155 166 245 256 335 344 346 445 566 1112 1123 1136 1156 1222 1226 1235 1345 1444 1466 2234 2236 2333 2335 2366 2555 Base 8: 47 non-descending primes between 1 and 1567: 2 3 5 7 13 15 23 27 35 37 45 57 111 117 123 145 147 155 177 225 227 235 247 255 277 337 345 357 445 467 557 577 667 1113 1127 1137 1145 1167 1223 1225 1245 1335 1347 1357 1467 1555 1567 Base 9: 45 non-descending primes between 1 and 1288: 2 3 5 7 12 14 18 25 34 45 47 58 67 78 117 122 124 128 135 155 177 234 238 267 278 337 344 355 377 447 557 568 667 678 788 1112 1114 1118 1147 1158 1178 1222 1255 1268 1288 Base 10: 50 non-descending primes between 1 and 677: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Base 16: 88 non-descending primes between 1 and 3df: 2 3 5 7 b d 11 13 17 1d 1f 25 29 2b 2f 35 3b 3d 47 49 4f 59 67 6b 6d 7f 89 8b 9d ad bf df ef 115 119 11b 125 133 137 139 13d 14b 15b 15d 167 16f 17b 17f 18d 199 1af 1bb 1cd 1cf 1df 223 22d 233 239 23b 24b 257 259 25f 269 26b 277 28d 2ab 2bd 2cf 2dd 2ef 335 337 33b 33d 347 355 359 35b 35f 36d 377 38b 38f 3ad 3df Base 17: 82 non-descending primes between 1 and 37b: 2 3 5 7 b d 12 16 1c 1e 23 27 29 2d 38 3a 3g 45 4b 4f 5c 5g 67 6b 78 7c 8d 8f 9a 9e ab bc fg 111 115 117 11b 128 12e 137 139 13d 14a 14g 155 159 15f 166 16a 17b 17d 188 18e 19f 1bb 1bf 1cg 1dd 1ee 1gg 225 227 23c 23e 247 24d 24f 25a 25e 26b 27c 28d 29c 2ad 2cf 33b 346 34c 35f 368 36e 37b Base 27: 103 non-descending primes between 1 and 19p: 2 3 5 7 b d h j n 12 14 1a 1e 1g 1k 1q 25 27 2d 2h 2j 2p 38 3g 3k 3m 3q 45 4j 4n 5e 5g 5m 6b 6h 6j 78 7a 7m 8b 8d 8h 8n 8p 9e 9k 9q ab ad an be bg bk cd cn cp dg dm ej en fg fq gh gp hk in kn lq mn mp nq op pq 111 115 11d 11h 124 12e 12q 13b 13d 13h 13j 14g 14k 14m 14q 15d 15h 15j 15n 16g 16k 17b 17j 17n 188 18m 18q 19b 19j 19p Base 31: 94 non-descending primes between 1 and 115: 2 3 5 7 b d h j n t 16 1a 1c 1g 1m 1s 1u 25 29 2b 2h 2l 2r 34 38 3a 3e 3g 3k 47 4d 4f 4p 4r 58 5c 5i 5o 5q 67 6b 6d 6p 7a 7c 7g 7m 7o 89 8f 8l 8n 8t 9e 9s al ar bc bi bq ch cp ct dg di ds du ef en er et fm fq gp gr hk hu ij it jo js ju kl kn kr lm lq mr nq nu op ot tu 115 Base 62: 150 non-descending primes between 1 and Fz: 2 3 5 7 B D H J N T V b f h l r x z 15 19 1B 1H 1L 1R 1Z 1d 1f 1j 1l 1p 23 27 2D 2F 2P 2R 2X 2d 2h 2n 2t 2v 35 37 3B 3D 3P 3b 3f 3h 3l 3r 3t 49 4F 4L 4N 4T 4X 4Z 4j 4x 57 5L 5R 5b 5d 5h 5n 5v 67 6B 6H 6P 6T 6b 6l 6n 6x 6z 79 7F 7N 7R 7T 7X 7j 7r 7v 8D 8P 8R 8j 8p 8z 9B 9D 9J 9T 9Z 9f 9h 9n 9t 9x 9z AB AL AN AR AX Ad Af Ar Av BJ BR Bb Bj Bp Bv Bz CD CH CP CT Ch Cr DF DH DL DN DX Dl Dp Dr Dv EF EJ Ed Eh Ep Ez FH FN Fb Ff Fl Fr Fz
Nim
<lang Nim>import strformat, sugar
func isPrime(n: Natural): bool =
if n < 2: 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 result = true
func isNonDecreasing(n: int): bool =
var n = n var prev = 10 while n != 0: let d = n mod 10 if d > prev: return false prev = d n = n div 10 result = true
let result = collect(newSeq):
for n in 2..999: if n.isPrime and n.isNonDecreasing: n
echo &"Found {result.len} primes:" for i, n in result:
stdout.write &"{n:3}", if (i + 1) mod 10 == 0: '\n' else: ' '</lang>
- Output:
Found 50 primes: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677
Phix
function nd(string s) return s=sort(s) end function sequence res = filter(apply(true,sprintf,{{"%d"},get_primes_le(1000)}),nd) printf(1,"%d non-decreasing primes < 1,000: %s\n",{length(res),join(shorten(res,"",5))})
- Output:
50 non-decreasing primes < 1,000: 2 3 5 7 11 ... 557 569 577 599 677
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Primes_with_digits_in_nondecreasing_order use warnings;
my @primes = grep {
! /(.)(.)(??{$1 > $2 ? : '(*FAIL)'})/ and (1 x $_) !~ /^(11+)\1+$/ } 2 .. 999;
print "@primes\n" =~ s/.{50}\K /\n/gr, "\ncount: " . @primes, "\n";</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 count: 50
Python
<lang python>Primes with monotonic (rising or equal) digits
from operator import le from itertools import takewhile
- monotonicDigits :: Int -> Int -> Bool
def monotonicDigits(base):
True if the decimal digits of n are monotonic under (<=) def go(n): return monotonic(le)( showIntAtBase(base)(digitFromInt)(n)() ) return go
- monotonic :: (a -> a -> Bool) -> [a] -> Bool
def monotonic(op):
True if the op returns True for each successive pair of values in xs. def go(xs): return all(map(op, xs, xs[1:])) return go
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Primes below 1000 in which any decimal digit is lower than or equal to any digit to its right. xs = [ str(n) for n in takewhile( lambda n: 1000 > n, filter(monotonicDigits(10), primes()) ) ] w = len(xs[-1]) print(f'{len(xs)} matches for base 10:\n') print('\n'.join( ' '.join(row) for row in chunksOf(10)([ x.rjust(w, ' ') for x in 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
- digitFromInt :: Int -> Char
def digitFromInt(n):
A character representing a small integer value. return '0123456789abcdefghijklmnopqrstuvwxyz'[n] if ( 0 <= n < 36 ) else '?'
- primes :: [Int]
def primes():
Non finite sequence of prime numbers. n = 2 dct = {} while True: if n in dct: for p in dct[n]: dct.setdefault(n + p, []).append(p) del dct[n] else: yield n dct[n * n] = [n] n = 1 + n
- showIntAtBase :: Int -> (Int -> Char) -> Int ->
- String -> String
def showIntAtBase(base):
String representation of an integer in a given base, using a supplied function for the string representation of digits. def wrap(toChr, n, rs): def go(nd, r): n, d = nd r_ = toChr(d) + r return go(divmod(n, base), r_) if 0 != n else r_ return 'unsupported base' if 1 >= base else ( 'negative number' if 0 > n else ( go(divmod(n, base), rs)) ) return lambda toChr: lambda n: lambda rs: ( wrap(toChr, n, rs) )
- MAIN ---
if __name__ == '__main__':
main()
</lang>
- Output:
50 matches for base 10: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677
Raku
<lang perl6>my $range = ^1000;
for flat 2..10, 17, 27, 31 -> $base {
say "\nBase $base: {+$_} non-decending primes between $range.minmax.map( *.base: $base ).join(' and '):\n{ .batch(20)».fmt("%{.tail.chars}s").join: "\n" }" given $range.grep( *.is-prime ).map( *.base: $base ).grep: { [le] .comb }
}</lang>
- Output:
Base 2: 4 non-decending primes between 0 and 1111100111: 11 111 11111 1111111 Base 3: 6 non-decending primes between 0 and 1101000: 2 12 111 122 1112 1222 Base 4: 17 non-decending primes between 0 and 33213: 2 3 11 13 23 113 133 223 233 1223 1333 2333 11123 11233 11333 12233 22223 Base 5: 17 non-decending primes between 0 and 12444: 2 3 12 23 34 111 122 133 1112 1123 1233 1244 2223 2344 3444 11122 12222 Base 6: 37 non-decending primes between 0 and 4343: 2 3 5 11 15 25 35 45 111 115 125 135 155 225 245 255 335 345 445 455 1115 1125 1145 1235 1245 1335 1345 1355 1445 1555 2225 2335 2345 2555 3445 3455 3555 Base 7: 38 non-decending primes between 0 and 2625: 2 3 5 14 16 23 25 56 113 115 124 133 146 155 166 245 256 335 344 346 445 566 1112 1123 1136 1156 1222 1226 1235 1345 1444 1466 2234 2236 2333 2335 2366 2555 Base 8: 47 non-decending primes between 0 and 1747: 2 3 5 7 13 15 23 27 35 37 45 57 111 117 123 145 147 155 177 225 227 235 247 255 277 337 345 357 445 467 557 577 667 1113 1127 1137 1145 1167 1223 1225 1245 1335 1347 1357 1467 1555 1567 Base 9: 45 non-decending primes between 0 and 1330: 2 3 5 7 12 14 18 25 34 45 47 58 67 78 117 122 124 128 135 155 177 234 238 267 278 337 344 355 377 447 557 568 667 678 788 1112 1114 1118 1147 1158 1178 1222 1255 1268 1288 Base 10: 50 non-decending primes between 0 and 999: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Base 17: 82 non-decending primes between 0 and 37D: 2 3 5 7 B D 12 16 1C 1E 23 27 29 2D 38 3A 3G 45 4B 4F 5C 5G 67 6B 78 7C 8D 8F 9A 9E AB BC FG 111 115 117 11B 128 12E 137 139 13D 14A 14G 155 159 15F 166 16A 17B 17D 188 18E 19F 1BB 1BF 1CG 1DD 1EE 1GG 225 227 23C 23E 247 24D 24F 25A 25E 26B 27C 28D 29C 2AD 2CF 33B 346 34C 35F 368 36E 37B Base 27: 103 non-decending primes between 0 and 1A0: 2 3 5 7 B D H J N 12 14 1A 1E 1G 1K 1Q 25 27 2D 2H 2J 2P 38 3G 3K 3M 3Q 45 4J 4N 5E 5G 5M 6B 6H 6J 78 7A 7M 8B 8D 8H 8N 8P 9E 9K 9Q AB AD AN BE BG BK CD CN CP DG DM EJ EN FG FQ GH GP HK IN KN LQ MN MP NQ OP PQ 111 115 11D 11H 124 12E 12Q 13B 13D 13H 13J 14G 14K 14M 14Q 15D 15H 15J 15N 16G 16K 17B 17J 17N 188 18M 18Q 19B 19J 19P Base 31: 94 non-decending primes between 0 and 117: 2 3 5 7 B D H J N T 16 1A 1C 1G 1M 1S 1U 25 29 2B 2H 2L 2R 34 38 3A 3E 3G 3K 47 4D 4F 4P 4R 58 5C 5I 5O 5Q 67 6B 6D 6P 7A 7C 7G 7M 7O 89 8F 8L 8N 8T 9E 9S AL AR BC BI BQ CH CP CT DG DI DS DU EF EN ER ET FM FQ GP GR HK HU IJ IT JO JS JU KL KN KR LM LQ MR NQ NU OP OT TU 115
REXX
<lang rexx>/*REXX program finds & displays primes whose decimal digits are in non─decreasing order.*/ parse arg n cols . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 1000 /*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= ' primes whose decimal digits are in' , 'non─decreasing order, N < ' commas(n)
if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') found= 0; idx= 1 /*initialize # of non─decreasing primes*/ $= /*a list of non─decreasing digit primes*/
do j=1 while @.j<n; p= @.j /*examine the primes within the range. */ do k=1 for length(p)-1 /*validate that it meets specifications*/ if substr(p, k, 1) > substr(p, k+1, 1) then iterate j /*compare dig with next.*/ end /*k*/ found= found + 1 /*bump number of non─decreasing primes.*/ if cols<0 then iterate /*Just do the summary? Then skip grid.*/ $= $ right( commas(j), w) /*add a commatized prime──►list (grid).*/ 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), '─') /*display foot sep. */ say say 'Found ' commas(found) title /*display foot title*/ 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: @.1=2; @.2=3; @.3=5; @.4=7 /*define some low primes. */
#= 3; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 to n-1 /*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? */ /* [↑] the above five lines saves time*/ do k=4 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 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
index │ primes whose decimal digits are in non─decreasing order, N < 1,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 1 2 3 4 5 6 7 8 9 10 11 │ 12 15 17 19 22 24 30 31 33 34 21 │ 35 37 39 41 46 48 49 50 51 52 31 │ 55 57 59 68 69 70 72 73 75 77 41 │ 87 88 91 92 95 102 104 106 109 123 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 50 primes whose decimal digits are in non─decreasing order, N < 1,000
Ring
<lang ring>load "stdlib.ring"
? "working..."
c = 0 limit = 1000
? "Primes under " + limit + " with digits in nondecreasing order:"
for n = 1 to limit
flag = 1 strn = string(n) if isprime(n) for m = 1 to len(strn) - 1 if strn[m] > strn[m + 1] flag = 0 exit ok next if flag = 1 see sf(n, 4) + " " c++ if c % 10 = 0 see nl ok ok ok
next
? nl + "Found " + c + " base 10 primes with digits in nondecreasing order" ? "done..."
- a very plain string formatter, intended to even up columnar outputs
def sf x, y
s = string(x) l = len(s) if l > y y = l ok return substr(" ", 11 - y + l) + s</lang>
- Output:
working... Primes under 1000 with digits in nondecreasing order: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Found 50 base 10 primes with digits in nondecreasing order done...
Visual Basic .NET
<lang vbnet>Imports System.Linq Imports System.Collections.Generic Imports System.Console Imports System.Math
Module Module1
Dim ba As Integer Dim chars As String = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
Iterator Function Primes(ByVal lim As Integer) As IEnumerable(Of Integer) Dim flags(lim) As Boolean, j As Integer : Yield 2 For j = 4 To lim Step 2 : flags(j) = True : Next : j = 3 Dim d As Integer = 8, sq As Integer = 9 While sq <= lim If Not flags(j) Then Yield j : Dim i As Integer = j << 1 For k As Integer = sq To lim step i : flags(k) = True : Next End If j += 2 : d += 8 : sq += d : End While While j <= lim If Not flags(j) Then Yield j j += 2 : End While End Function
' convert an int into a string using the current ba Function from10(ByVal b As Integer) As String Dim res As String = "", re As Integer While b > 0 : b = DivRem(b, ba, re) : res = chars(CByte(re)) & res : End While : Return res End Function
' parse a string into an int, using current ba (not used here) Function to10(ByVal s As String) As Integer Dim res As Integer = 0 For Each i As Char In s : res = res * ba + chars.IndexOf(i) : Next : Return res End Function
' note: comparing the index of the chars instead of the chars themsleves, which avoids case issues Function nd(ByVal s As String) As Boolean If s.Length < 2 Then Return True Dim l As Char = s(0) For i As Integer = 1 To s.Length - 1 If chars.IndexOf(l) > chars.IndexOf(s(i)) Then Return False Else l = s(i) Next : Return True End Function
Sub Main(ByVal args As String()) Dim c As Integer, lim As Integer = 1000, s As String For Each b As Integer In New List(Of Integer) From { 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 17, 27, 31, 62 } ba = b : c = 0 : For Each a As Integer In Primes(lim) s = from10(a) : If nd(s) Then c += 1 : Write("{0,4} {1}", s, If(c Mod 20 = 0, vbLf, "")) Next WriteLine(vbLf & "Base {0}: found {1} non-decreasing primes under {2:n0}" & vbLf, b, c, from10(lim)) Next End Sub
End Module</lang>
- Output:
Same as C#.
Wren
<lang ecmascript>import "/math" for Int import "/seq" for Lst import "/fmt" for Fmt
var nonDescending = Fn.new { |p|
var digits = [] while (p > 0) { digits.add(p % 10) p = (p/10).floor } for (i in 0...digits.count-1) { if (digits[i+1] > digits[i]) return false } return true
}
var primes = Int.primeSieve(999) var nonDesc = [] for (p in primes) if (nonDescending.call(p)) nonDesc.add(p) System.print("Primes below 1,000 with digits in non-decreasing order:") for (chunk in Lst.chunks(nonDesc, 10)) Fmt.print("$3d", chunk) System.print("\n%(nonDesc.count) such primes found.")</lang>
- Output:
Primes below 1,000 with digits in non-decreasing order: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 50 such primes found.