Primes with digits in nondecreasing order
Primes with digits in nondecreasing order is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- 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
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
Julia
<lang julia>using Primes
const range = 2:999
for base in [2:10...;[10, 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 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 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
Phix
function nd(string s) return not find(true,sq_lt(s[2..$],s[1..$-1])) 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
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 hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 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. */
@ndcps= ' primes whose decimal digits are in non─decreasing order that' ,
'are < ' commas(hi)
if cols>0 then say ' index │'center(@ndcps, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') ndcps= 0; idx= 1 /*initialize # of non─decreasing primes*/ $= /*a list of non─decreasing digit primes*/
do j=1 while @.j<hi; 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*/
ndcps= ndcps + 1 /*bump number of non─decreasing primes.*/
if cols==0 then iterate /*Build the list (to be shown later)? */
c= commas(p) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add a prime ──► list, allow big nums.*/
if ndcps//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(ndcps) @ndcps 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 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? */
/* [↑] 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 that are < 1,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 2 3 5 7 11 13 17 19 23 29 11 │ 37 47 59 67 79 89 113 127 137 139 21 │ 149 157 167 179 199 223 227 229 233 239 31 │ 257 269 277 337 347 349 359 367 379 389 41 │ 449 457 467 479 499 557 569 577 599 677 Found 50 primes whose decimal digits are in non─decreasing order that are < 1,000
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "Primes with digits in nondecreasing order:" + nl
row = 0 num = 0 limit1 = 1000
for n = 1 to limit1
flag = 1
strn = string(n)
if isprime(n)
for m = 1 to len(strn)-1
if strn[m] > strn[m+1]
flag = 0
exit
else
flag = 1
ok
next
if flag = 1
num = num + 1
row = row+1
see "" + n + " "
if row%10 = 0
see nl
ok
ok
ok
next
see "Found " + num + " primes with digits in nondecreasing order" + nl see "done..." + nl </lang>
- Output:
working... Primes 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 primes with digits in nondecreasing order done...