Ascending primes: Difference between revisions
m (J: might as well throw in a benchmark -- but some other implementations will be faster than this, some will be slower and it's not like this is a performance critical task) |
m (→{{header|J}}) |
||
| Line 98: | Line 98: | ||
23689 13789 23789 123479 124679 235679 145679 345679 234589 345689 |
23689 13789 23789 123479 124679 235679 145679 345679 234589 345689 |
||
134789 125789 235789 245789 1245689 1234789 1235789 1456789 12356789 23456789 |
134789 125789 235789 245789 1245689 1234789 1235789 1456789 12356789 23456789 |
||
timex'(#~ 1 p: ])10#.&>([:~.@;extend each)^:# >:i.9' NB. seconds |
timex'(#~ 1 p: ])10#.&>([:~.@;extend each)^:# >:i.9' NB. seconds (take with grain of salt) |
||
0.003818 |
0.003818 |
||
</lang> |
</lang> |
||
Revision as of 23:00, 8 March 2022
Generate and show all primes with strictly ascending decimal digits.
Aside: Try solving without peeking at existing solutions. I had a weird idea for generating a prime sieve faster, which needless to say didn't pan out. The solution may be p(r)etty trivial but generating them quickly is at least mildly interesting. Tip: filtering all 7,027,260 primes below 123,456,789 probably won't kill you, but there is at least one significantly better and much faster way, needing a mere 511 odd/prime tests.
- See also
- Related
- Primes with digits in nondecreasing order (infinite series allowing duplicate digits, whereas this isn't and doesn't)
- Pandigital prime (whereas this is the smallest, with gaps in the used digits being permitted)
ALGOL 68
Uses Pete's hint to enumerate the 512 possible numbers.
The numbers are generated in order of the first digit, so we have to sort them.
As there are only 512 possible numbers to consider, it doesn't attempt the optimisation that the final digit can't be 4, 6 or 8 and can only be 2 or 5 if it is the only digit (also, I always forget that can't be even thing...).
<lang algol68>BEGIN # find all primes with strictly increasing digits #
PR read "primes.incl.a68" PR # include prime utilities #
PR read "rows.incl.a68" PR # include array utilities #
[ 1 : 512 ]INT primes; # there will be at most 512 (2^9) primes #
INT p count := 0; # number of primes found so far #
FOR d1 FROM 0 TO 1 DO
INT n1 = d1;
FOR d2 FROM 0 TO 1 DO
INT n2 = IF d2 = 1 THEN ( n1 * 10 ) + 2 ELSE n1 FI;
FOR d3 FROM 0 TO 1 DO
INT n3 = IF d3 = 1 THEN ( n2 * 10 ) + 3 ELSE n2 FI;
FOR d4 FROM 0 TO 1 DO
INT n4 = IF d4 = 1 THEN ( n3 * 10 ) + 4 ELSE n3 FI;
FOR d5 FROM 0 TO 1 DO
INT n5 = IF d5 = 1 THEN ( n4 * 10 ) + 5 ELSE n4 FI;
FOR d6 FROM 0 TO 1 DO
INT n6 = IF d6 = 1 THEN ( n5 * 10 ) + 6 ELSE n5 FI;
FOR d7 FROM 0 TO 1 DO
INT n7 = IF d7 = 1 THEN ( n6 * 10 ) + 7 ELSE n6 FI;
FOR d8 FROM 0 TO 1 DO
INT n8 = IF d8 = 1 THEN ( n7 * 10 ) + 8 ELSE n7 FI;
FOR d9 FROM 0 TO 1 DO
INT n9 = IF d9 = 1 THEN ( n8 * 10 ) + 9 ELSE n8 FI;
IF n9 > 0 THEN
IF is probably prime( n9 ) THEN
# have a prime with strictly ascending digits #
primes[ p count +:= 1 ] := n9
FI
FI
OD
OD
OD
OD
OD
OD
OD
OD
OD;
QUICKSORT primes FROMELEMENT 1 TOELEMENT p count; # sort the primes #
FOR i TO p count DO # display the primes #
print( ( " ", whole( primes[ i ], -8 ) ) );
IF i MOD 10 = 0 THEN print( ( newline ) ) FI
OD
END</lang>
- Output:
2 3 5 7 13 17 19 23 29 37
47 59 67 79 89 127 137 139 149 157
167 179 239 257 269 347 349 359 367 379
389 457 467 479 569 1237 1249 1259 1279 1289
1367 1459 1489 1567 1579 1789 2347 2357 2389 2459
2467 2579 2689 2789 3457 3467 3469 4567 4679 4789
5689 12347 12379 12457 12479 12569 12589 12689 13457 13469
13567 13679 13789 15679 23459 23567 23689 23789 25679 34589
34679 123457 123479 124567 124679 125789 134789 145679 234589 235679
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789
J
<lang J> $(#~ 1 p: ])10#.&>([:~.@;extend each)^:# >:i.9 100
10 10$(#~ 1 p: ])10#.&>([:~.@;extend each)^:# >:i.9
2 3 13 23 5 7 17 37 47 67
127 137 347 157 257 457 167 367 467 1237
2347 2357 3457 1367 2467 3467 1567 4567 12347 12457
13457 13567 23567 123457 124567 19 29 59 79 89
139 239 149 349 359 269 569 179 379 479
389 1249 1259 1459 2459 3469 1279 1579 2579 4679
1289 2389 1489 2689 5689 1789 2789 4789 23459 13469
12569 12379 12479 13679 34679 15679 25679 12589 34589 12689
23689 13789 23789 123479 124679 235679 145679 345679 234589 345689
134789 125789 235789 245789 1245689 1234789 1235789 1456789 12356789 23456789
timex'(#~ 1 p: ])10#.&>([:~.@;extend each)^:# >:i.9' NB. seconds (take with grain of salt)
0.003818 </lang>
Phix
with javascript_semantics function ascending_primes(sequence res, atom p=0) for d=remainder(p,10)+1 to 9 do integer np = p*10+d if odd(d) and is_prime(np) then res &= np end if res = ascending_primes(res,np) end for return res end function sequence r = apply(true,sprintf,{{"%8d"},sort(ascending_primes({2}))}) printf(1,"There are %,d ascending primes:\n%s\n",{length(r),join_by(r,1,10," ")})
- Output:
There are 100 ascending primes:
2 3 5 7 13 17 19 23 29 37
47 59 67 79 89 127 137 139 149 157
167 179 239 257 269 347 349 359 367 379
389 457 467 479 569 1237 1249 1259 1279 1289
1367 1459 1489 1567 1579 1789 2347 2357 2389 2459
2467 2579 2689 2789 3457 3467 3469 4567 4679 4789
5689 12347 12379 12457 12479 12569 12589 12689 13457 13469
13567 13679 13789 15679 23459 23567 23689 23789 25679 34589
34679 123457 123479 124567 124679 125789 134789 145679 234589 235679
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789
Raku
<lang perl6>put (
flat 2, 3, 5, 7, sort +*, gather {
(1 .. 8).map: { recurse $_ };
sub recurse ($str) {
.take for ($str X~ (3, 7, 9)).grep: { .is-prime && [<] .comb };
recurse $str * 10 + $_ for $str % 10 ^.. 9;
}
}
).batch(10)».fmt("%8d").join: "\n";
printf "%.3f seconds", now - INIT now;</lang>
- Output:
2 3 5 7 13 17 19 23 29 37
47 59 67 79 89 127 137 139 149 157
167 179 239 257 269 347 349 359 367 379
389 457 467 479 569 1237 1249 1259 1279 1289
1367 1459 1489 1567 1579 1789 2347 2357 2389 2459
2467 2579 2689 2789 3457 3467 3469 4567 4679 4789
5689 12347 12379 12457 12479 12569 12589 12689 13457 13469
13567 13679 13789 15679 23459 23567 23689 23789 25679 34589
34679 123457 123479 124567 124679 125789 134789 145679 234589 235679
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789
0.075 seconds
Wren
Although they use a lot of memory, sieves usually produce good results in Wren and here we only need to sieve for primes up to 3456789 as there are just 9 possible candidates with 8 digits and 1 possible candidate with 9 digits which we can test for primality individually. The following runs in around 0.43 seconds. <lang ecmascript>import "./math" for Int import "./seq" for Lst import "./fmt" for Fmt
var isAscending = Fn.new { |n|
if (n < 10) return true
var digits = Int.digits(n)
for (i in 1...digits.count) {
if (digits[i] <= digits[i-1]) return false
}
return true
}
var higherPrimes = [] var candidates = [
12345678, 12345679, 12345689, 12345789, 12346789, 12356789, 12456789, 13456789, 23456789, 123456789
] for (cand in candidates) if (Int.isPrime(cand)) higherPrimes.add(cand)
var primes = Int.primeSieve(3456789) var ascPrimes = [] for (p in primes) if (isAscending.call(p)) ascPrimes.add(p) ascPrimes.addAll(higherPrimes) System.print("There are %(ascPrimes.count) ascending primes, namely:") for (chunk in Lst.chunks(ascPrimes, 10)) Fmt.print("$8d", chunk)</lang>
- Output:
There are 100 ascending primes, namely:
2 3 5 7 13 17 19 23 29 37
47 59 67 79 89 127 137 139 149 157
167 179 239 257 269 347 349 359 367 379
389 457 467 479 569 1237 1249 1259 1279 1289
1367 1459 1489 1567 1579 1789 2347 2357 2389 2459
2467 2579 2689 2789 3457 3467 3469 4567 4679 4789
5689 12347 12379 12457 12479 12569 12589 12689 13457 13469
13567 13679 13789 15679 23459 23567 23689 23789 25679 34589
34679 123457 123479 124567 124679 125789 134789 145679 234589 235679
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789
XPL0
Brute force solution: 4.3 seconds on Pi4. <lang XPL0>func IsPrime(N); \Return 'true' if N is prime int N, I; [if N <= 2 then return N = 2; if (N&1) = 0 then \even >2\ return false; for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false; I:= I+1; ];
return true; ];
func Ascending(N); \Return 'true' if digits are ascending int N, D; [N:= N/10; D:= rem(0); while N do
[N:= N/10; if rem(0) >= D then return false; D:= rem(0); ];
return true; ];
int Cnt, N; [Cnt:= 0; Format(9, 0); for N:= 2 to 123_456_789 do
if Ascending(N) then
if IsPrime(N) then
[RlOut(0, float(N));
Cnt:= Cnt+1;
if rem(Cnt/10) = 0 then CrLf(0);
];
]</lang>
- Output:
2 3 5 7 13 17 19 23 29 37
47 59 67 79 89 127 137 139 149 157
167 179 239 257 269 347 349 359 367 379
389 457 467 479 569 1237 1249 1259 1279 1289
1367 1459 1489 1567 1579 1789 2347 2357 2389 2459
2467 2579 2689 2789 3457 3467 3469 4567 4679 4789
5689 12347 12379 12457 12479 12569 12589 12689 13457 13469
13567 13679 13789 15679 23459 23567 23689 23789 25679 34589
34679 123457 123479 124567 124679 125789 134789 145679 234589 235679
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789