Unprimeable numbers: Difference between revisions
m (Separated Rust code into modules) |
|||
Line 1,814: | Line 1,814: | ||
9 ending: 212159 |
9 ending: 212159 |
||
</pre> |
</pre> |
||
=={{header|Racket}}== |
|||
<lang racket>#lang racket |
|||
(require math/number-theory) |
|||
(define cached-prime? |
|||
(let ((hsh# (make-hash))) (λ (p) (hash-ref! hsh# p (λ () (prime? p)))))) |
|||
(define (zero-digit n d) |
|||
(define p (expt 10 d)) |
|||
(+ (remainder n p) (* 10 p (quotient n (* p 10))))) |
|||
(define (primeable? n) |
|||
(or (cached-prime? n) |
|||
(for*/first ((d (in-range (add1 (order-of-magnitude n)))) |
|||
(n0 (in-value (zero-digit n d))) |
|||
(p (in-value (expt 10 d))) |
|||
(r (in-range 10)) |
|||
(n+ (in-value (+ n0 (* r p)))) |
|||
#:when (cached-prime? n+)) |
|||
n+))) |
|||
(define unprimeable? (negate primeable?)) |
|||
(module+ |
|||
main |
|||
(printf "First 35 unprimeable numbers: ~a~%" |
|||
(let recur ((i 0) (n 1) (acc null)) |
|||
(cond [(= i 35) (reverse acc)] |
|||
[(unprimeable? n) (recur (add1 i) (add1 n) (cons n acc))] |
|||
[else (recur i (add1 n) acc)]))) |
|||
(printf "600th unprimeable number: ~a~%" |
|||
(let recur ((i 0) (n 1) (u #f)) |
|||
(cond [(= i 600) u] |
|||
[(unprimeable? n) (recur (add1 i) (add1 n) n)] |
|||
[else (recur i (add1 n) u)]))) |
|||
(for ((d 10)) |
|||
(printf "Least unprimeable number ending in ~a = ~a~%" d |
|||
(for/first ((i (in-range (+ 100 d) +Inf.0 10)) #:when (unprimeable? i)) i)))) |
|||
(module+ test |
|||
(require rackunit) |
|||
(check-equal? (zero-digit 1234 2) 1034) |
|||
(check-equal? (primeable? 10) 11) |
|||
(check-true (unprimeable? 200)) |
|||
(check-false (unprimeable? 201)))</lang> |
|||
{{out}} |
|||
<pre>First 35 unprimeable numbers: (200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890) |
|||
600th unprimeable number: 5242 |
|||
Least unprimeable number ending in 0 = 200 |
|||
Least unprimeable number ending in 1 = 595631 |
|||
Least unprimeable number ending in 2 = 322 |
|||
Least unprimeable number ending in 3 = 1203623 |
|||
Least unprimeable number ending in 4 = 204 |
|||
Least unprimeable number ending in 5 = 325 |
|||
Least unprimeable number ending in 6 = 206 |
|||
Least unprimeable number ending in 7 = 872897 |
|||
Least unprimeable number ending in 8 = 208 |
|||
Least unprimeable number ending in 9 = 212159</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
Revision as of 11:12, 31 August 2020
You are encouraged to solve this task according to the task description, using any language you may know.
- Definitions
As used here, all unprimeable numbers (positive integers) are always expressed in base ten.
───── Definition from OEIS ─────:
Unprimeable numbers are composite numbers that always remain composite when a single decimal digit of the number is changed.
───── Definition from Wiktionary (referenced from Adam Spencer's book) ─────:
(arithmetic) that cannot be turned into a prime number by changing just one of its digits to any other
digit. (sic)
Unprimeable numbers are also spelled: unprimable.
All one─ and two─digit numbers can be turned into primes by changing a single decimal digit.
- Examples
190 isn't unprimeable, because by changing the zero digit into a three yields 193, which is a prime.
The number 200 is unprimeable, since none of the numbers 201, 202, 203, ··· 209 are prime, and all the other numbers obtained by changing a single digit to produce 100, 300, 400, ··· 900, or 210, 220, 230, ··· 290 which are all even.
It is valid to change 189 into 089 by changing the 1 (one) into
a 0 (zero), which then the leading zero can be removed, and then treated as if
the "new" number is 89.
- Task
-
- show the first 35 unprimeable numbers (horizontally, on one line, preferably with a title)
- show the 600th unprimeable number
- (optional) show the lowest unprimeable number ending in a specific decimal digit (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
- (optional) use commas in the numbers where appropriate
Show all output here, on this page.
- Also see
-
- the OEIS entry: A118118 (unprimeable)
- with some useful counts to compare unprimeable number
- the Wiktionary entry (reference from below): (arithmetic definition) unprimeable
- from the Adam Spencer book (page 200): Adam Spencer's World of Numbers (Xoum Publishing)
C
<lang c>#include <assert.h>
- include <locale.h>
- include <stdbool.h>
- include <stdint.h>
- include <stdio.h>
- include <stdlib.h>
typedef struct bit_array_tag {
uint32_t size; uint32_t* array;
} bit_array;
bool bit_array_create(bit_array* b, uint32_t size) {
uint32_t* array = calloc((size + 31)/32, sizeof(uint32_t)); if (array == NULL) return false; b->size = size; b->array = array; return true;
}
void bit_array_destroy(bit_array* b) {
free(b->array); b->array = NULL;
}
void bit_array_set(bit_array* b, uint32_t index, bool value) {
assert(index < b->size); uint32_t* p = &b->array[index >> 5]; uint32_t bit = 1 << (index & 31); if (value) *p |= bit; else *p &= ~bit;
}
bool bit_array_get(const bit_array* b, uint32_t index) {
assert(index < b->size); uint32_t* p = &b->array[index >> 5]; uint32_t bit = 1 << (index & 31); return (*p & bit) != 0;
}
typedef struct sieve_tag {
uint32_t limit; bit_array not_prime;
} sieve;
bool sieve_create(sieve* s, uint32_t limit) {
if (!bit_array_create(&s->not_prime, limit/2)) return false; for (uint32_t p = 3; p * p <= limit; p += 2) { if (bit_array_get(&s->not_prime, p/2 - 1) == false) { uint32_t inc = 2 * p; for (uint32_t q = p * p; q <= limit; q += inc) bit_array_set(&s->not_prime, q/2 - 1, true); } } s->limit = limit; return true;
}
void sieve_destroy(sieve* s) {
bit_array_destroy(&s->not_prime);
}
bool is_prime(const sieve* s, uint32_t n) {
assert(n <= s->limit); if (n == 2) return true; if (n < 2 || n % 2 == 0) return false; return bit_array_get(&s->not_prime, n/2 - 1) == false;
}
// return number of decimal digits uint32_t count_digits(uint32_t n) {
uint32_t digits = 0; for (; n > 0; ++digits) n /= 10; return digits;
}
// return the number with one digit replaced uint32_t change_digit(uint32_t n, uint32_t index, uint32_t new_digit) {
uint32_t p = 1; uint32_t changed = 0; for (; index > 0; p *= 10, n /= 10, --index) changed += p * (n % 10); changed += (10 * (n/10) + new_digit) * p; return changed;
}
// returns true if n unprimeable bool unprimeable(const sieve* s, uint32_t n) {
if (is_prime(s, n)) return false; uint32_t d = count_digits(n); for (uint32_t i = 0; i < d; ++i) { for (uint32_t j = 0; j <= 9; ++j) { uint32_t m = change_digit(n, i, j); if (m != n && is_prime(s, m)) return false; } } return true;
}
int main() {
const uint32_t limit = 10000000; setlocale(LC_ALL, ""); sieve s = { 0 }; if (!sieve_create(&s, limit)) { fprintf(stderr, "Out of memory\n"); return 1; } printf("First 35 unprimeable numbers:\n"); uint32_t n = 100; uint32_t lowest[10] = { 0 }; for (uint32_t count = 0, found = 0; n < limit && (found < 10 || count < 600); ++n) { if (unprimeable(&s, n)) { if (count < 35) { if (count != 0) printf(", "); printf("%'u", n); } ++count; if (count == 600) printf("\n600th unprimeable number: %'u\n", n); uint32_t last_digit = n % 10; if (lowest[last_digit] == 0) { lowest[last_digit] = n; ++found; } } } sieve_destroy(&s); for (uint32_t i = 0; i < 10; ++i) printf("Least unprimeable number ending in %u: %'u\n" , i, lowest[i]); return 0;
}</lang>
- Output:
First 35 unprimeable numbers: 200, 204, 206, 208, 320, 322, 324, 325, 326, 328, 510, 512, 514, 515, 516, 518, 530, 532, 534, 535, 536, 538, 620, 622, 624, 625, 626, 628, 840, 842, 844, 845, 846, 848, 890 600th unprimeable number: 5,242 Least unprimeable number ending in 0: 200 Least unprimeable number ending in 1: 595,631 Least unprimeable number ending in 2: 322 Least unprimeable number ending in 3: 1,203,623 Least unprimeable number ending in 4: 204 Least unprimeable number ending in 5: 325 Least unprimeable number ending in 6: 206 Least unprimeable number ending in 7: 872,897 Least unprimeable number ending in 8: 208 Least unprimeable number ending in 9: 212,159
C++
<lang cpp>#include <iostream>
- include <cstdint>
- include "prime_sieve.hpp"
typedef uint32_t integer;
// return number of decimal digits int count_digits(integer n) {
int digits = 0; for (; n > 0; ++digits) n /= 10; return digits;
}
// return the number with one digit replaced integer change_digit(integer n, int index, int new_digit) {
integer p = 1; integer changed = 0; for (; index > 0; p *= 10, n /= 10, --index) changed += p * (n % 10); changed += (10 * (n/10) + new_digit) * p; return changed;
}
// returns true if n unprimeable bool unprimeable(const prime_sieve& sieve, integer n) {
if (sieve.is_prime(n)) return false; int d = count_digits(n); for (int i = 0; i < d; ++i) { for (int j = 0; j <= 9; ++j) { integer m = change_digit(n, i, j); if (m != n && sieve.is_prime(m)) return false; } } return true;
}
int main() {
const integer limit = 10000000; prime_sieve sieve(limit);
// print numbers with commas std::cout.imbue(std::locale("")); std::cout << std::fixed;
std::cout << "First 35 unprimeable numbers:\n"; integer n = 100; integer lowest[10] = { 0 }; for (int count = 0, found = 0; n < limit && (found < 10 || count < 600); ++n) { if (unprimeable(sieve, n)) { if (count < 35) { if (count != 0) std::cout << ", "; std::cout << n; } ++count; if (count == 600) std::cout << "\n600th unprimeable number: " << n << '\n'; int last_digit = n % 10; if (lowest[last_digit] == 0) { lowest[last_digit] = n; ++found; } } } for (int i = 0; i < 10; ++i) std::cout << "Least unprimeable number ending in " << i << ": " << lowest[i] << '\n'; return 0;
}</lang>
Contents of prime_sieve.hpp: <lang cpp>#ifndef PRIME_SIEVE_HPP
- define PRIME_SIEVE_HPP
- include <algorithm>
- include <vector>
/**
* A simple implementation of the Sieve of Eratosthenes. * See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. */
class prime_sieve { public:
explicit prime_sieve(size_t); bool is_prime(size_t) const;
private:
std::vector<bool> is_prime_;
};
/**
* Constructs a sieve with the given limit. * * @param limit the maximum integer that can be tested for primality */
inline prime_sieve::prime_sieve(size_t limit) {
limit = std::max(size_t(3), limit); is_prime_.resize(limit/2, true); for (size_t p = 3; p * p <= limit; p += 2) { if (is_prime_[p/2 - 1]) { size_t inc = 2 * p; for (size_t q = p * p; q <= limit; q += inc) is_prime_[q/2 - 1] = false; } }
}
/**
* Returns true if the given integer is a prime number. The integer * must be less than or equal to the limit passed to the constructor. * * @param n an integer less than or equal to the limit passed to the * constructor * @return true if the integer is prime */
inline bool prime_sieve::is_prime(size_t n) const {
if (n == 2) return true; if (n < 2 || n % 2 == 0) return false; return is_prime_.at(n/2 - 1);
}
- endif</lang>
- Output:
First 35 unprimeable numbers: 200, 204, 206, 208, 320, 322, 324, 325, 326, 328, 510, 512, 514, 515, 516, 518, 530, 532, 534, 535, 536, 538, 620, 622, 624, 625, 626, 628, 840, 842, 844, 845, 846, 848, 890 600th unprimeable number: 5,242 Least unprimeable number ending in 0: 200 Least unprimeable number ending in 1: 595,631 Least unprimeable number ending in 2: 322 Least unprimeable number ending in 3: 1,203,623 Least unprimeable number ending in 4: 204 Least unprimeable number ending in 5: 325 Least unprimeable number ending in 6: 206 Least unprimeable number ending in 7: 872,897 Least unprimeable number ending in 8: 208 Least unprimeable number ending in 9: 212,159
Factor
<lang factor>USING: assocs formatting io kernel lists lists.lazy lists.lazy.examples math math.functions math.primes math.ranges math.text.utils prettyprint sequences tools.memory.private ;
- one-offs ( n -- seq )
dup 1 digit-groups [ swapd 10^ [ * ] keep [ - ] dip 2dup [ 9 * ] [ + ] [ <range> ] tri* ] with map-index concat ;
- (unprimeable?) ( n -- ? )
[ f ] [ one-offs [ prime? ] none? ] if-zero ;
- unprimeable? ( n -- ? )
dup prime? [ drop f ] [ (unprimeable?) ] if ;
- unprimeables ( -- list ) naturals [ unprimeable? ] lfilter ;
- ?set-at ( value key assoc -- )
2dup key? [ 3drop ] [ set-at ] if ;
- first-digits ( -- assoc )
unprimeables H{ } clone [ dup assoc-size 10 = ] [ [ unswons dup 10 mod ] dip [ ?set-at ] keep ] until nip ;
"The first 35 unprimeable numbers:" print bl bl 35 unprimeables ltake [ pprint bl ] leach nl nl
"The 600th unprimeable number:" print bl bl unprimeables 599 [ cdr ] times car commas print nl
"The first unprimeable number ending with" print first-digits [ commas " %d: %9s\n" printf ] assoc-each</lang>
- Output:
The first 35 unprimeable numbers: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600th unprimeable number: 5,242 The first unprimeable number ending with 0: 200 1: 595,631 2: 322 3: 1,203,623 4: 204 5: 325 6: 206 7: 872,897 8: 208 9: 212,159
Go
Simple brute force (no sieves, memoization or bigint.ProbablyPrime) as there is not much need for speed here. <lang go>package main
import (
"fmt" "strconv"
)
func isPrime(n int) bool {
switch { case n < 2: return false case n%2 == 0: return n == 2 case n%3 == 0: return n == 3 default: d := 5 for d*d <= n { if n%d == 0 { return false } d += 2 if n%d == 0 { return false } d += 4 } return true }
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n) le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } return s
}
func main() {
fmt.Println("The first 35 unprimeable numbers are:") count := 0 // counts all unprimeable numbers var firstNum [10]int // stores the first unprimeable number ending with each digit
outer:
for i, countFirst := 100, 0; countFirst < 10; i++ { if isPrime(i) { continue // unprimeable number must be composite } s := strconv.Itoa(i) le := len(s) b := []byte(s) for j := 0; j < le; j++ { for k := byte('0'); k <= '9'; k++ { if s[j] == k { continue } b[j] = k n, _ := strconv.Atoi(string(b)) if isPrime(n) { continue outer } } b[j] = s[j] // restore j'th digit to what it was originally } lastDigit := s[le-1] - '0' if firstNum[lastDigit] == 0 { firstNum[lastDigit] = i countFirst++ } count++ if count <= 35 { fmt.Printf("%d ", i) } if count == 35 { fmt.Print("\n\nThe 600th unprimeable number is: ") } if count == 600 { fmt.Printf("%s\n\n", commatize(i)) } }
fmt.Println("The first unprimeable number that ends in:") for i := 0; i < 10; i++ { fmt.Printf(" %d is: %9s\n", i, commatize(firstNum[i])) }
}</lang>
- Output:
200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600th unprimeable number is: 5,242 The first unprimeable number that ends in: 0 is: 200 1 is: 595,631 2 is: 322 3 is: 1,203,623 4 is: 204 5 is: 325 6 is: 206 7 is: 872,897 8 is: 208 9 is: 212,159
Haskell
<lang haskell>import Control.Lens ((.~), ix, (&)) import Data.Numbers.Primes (isPrime) import Data.List (find, intercalate) import Data.Char (intToDigit) import Data.Maybe (mapMaybe) import Data.List.Split (chunksOf) import Text.Printf (printf)
isUnprimable :: Int -> Bool isUnprimable = all (not . isPrime) . swapdigits
swapdigits :: Int -> [Int] swapdigits n = map read $ go $ pred $ length digits
where digits = show n go (-1) = [] go n = map (\x -> digits & (ix n) .~ intToDigit x) [0..9] <> go (pred n)
unPrimeable :: [Int] unPrimeable = filter isUnprimable [1..]
main :: IO () main = do
printf "First 35 unprimeable numbers:\n%s\n\n" $ show $ take 35 unPrimeable printf "600th unprimeable number: %d\n\n" $ unPrimeable !! 599 mapM_ (uncurry (printf "Lowest unprimeable number ending with %d: %10s\n")) $ mapMaybe lowest [0..9] where thousands = reverse . intercalate "," . chunksOf 3 . reverse lowest n = do x <- find (\x -> x `mod` 10 == n) unPrimeable pure (n, thousands $ show x)</lang>
- Output:
First 35 unprimeable numbers: [200,204,206,208,320,322,324,325,326,328,510,512,514,515,516,518,530,532,534,535,536,538,620,622,624,625,626,628,840,842,844,845,846,848,890] 600th unprimeable number: 5242 Lowest unprimeable number ending with 0: 200 Lowest unprimeable number ending with 1: 595,631 Lowest unprimeable number ending with 2: 322 Lowest unprimeable number ending with 3: 1,203,623 Lowest unprimeable number ending with 4: 204 Lowest unprimeable number ending with 5: 325 Lowest unprimeable number ending with 6: 206 Lowest unprimeable number ending with 7: 872,897 Lowest unprimeable number ending with 8: 208 Lowest unprimeable number ending with 9: 212,159
J
Reshaping data is a strength of j. <lang J> NB. replace concatenates at various ranks and in boxes to avoid fill NB. the curtailed prefixes (}:\) with all of 0..9 (i.10) with the beheaded suffixes (}.\.) NB. under the antibase 10 representation (10&#.inv) replace=: ([: ; <@}:\ ,"1 L:_1 ([: < (i.10) ,"0 1 }.)\.)&.(10&#.inv)
NB. primable tests if one of the replacements is prime primable=: (1 e. 1 p: replace)&>
unprimable=: -.@:primable
assert 0 1 -: unprimable 193 200 </lang>
NB. test 2e6 integers for unprimability A=: unprimable i. 2e6 UNPRIMABLE=: I. A NB. indexes of the 1s are the unprimable numbers 35 {. UNPRIMABLE NB. first 35 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 UNPRIMABLE {~ <: 600 NB. 600th 5242 NB. the first unprimable numbers ending with 0--9 NB. sorted by least significant digit after in-order grouping by the LSD key. (/: 10&|) ({./.~ 10&|) UNPRIMABLE 200 595631 322 1203623 204 325 206 872897 208 212159
Java
<lang java> public class UnprimeableNumbers {
private static int MAX = 10_000_000; private static boolean[] primes = new boolean[MAX];
public static void main(String[] args) { sieve(); System.out.println("First 35 unprimeable numbers:"); displayUnprimeableNumbers(35); int n = 600; System.out.printf("%nThe %dth unprimeable number = %,d%n%n", n, nthUnprimeableNumber(n)); int[] lowest = genLowest(); System.out.println("Least unprimeable number that ends in:"); for ( int i = 0 ; i <= 9 ; i++ ) { System.out.printf(" %d is %,d%n", i, lowest[i]); } } private static int[] genLowest() { int[] lowest = new int[10]; int count = 0; int test = 1; while ( count < 10 ) { test++; if ( unPrimable(test) && lowest[test % 10] == 0 ) { lowest[test % 10] = test; count++; } } return lowest; }
private static int nthUnprimeableNumber(int maxCount) { int test = 1; int count = 0; int result = 0; while ( count < maxCount ) { test++; if ( unPrimable(test) ) { count++; result = test; } } return result; }
private static void displayUnprimeableNumbers(int maxCount) { int test = 1; int count = 0; while ( count < maxCount ) { test++; if ( unPrimable(test) ) { count++; System.out.printf("%d ", test); } } System.out.println(); } private static boolean unPrimable(int test) { if ( primes[test] ) { return false; } String s = test + ""; for ( int i = 0 ; i < s.length() ; i++ ) { for ( int j = 0 ; j <= 9 ; j++ ) { if ( primes[Integer.parseInt(replace(s, i, j))] ) { return false; } } } return true; } private static String replace(String str, int position, int value) { char[] sChar = str.toCharArray(); sChar[position] = (char) value; return str.substring(0, position) + value + str.substring(position + 1); }
private static final void sieve() { // primes for ( int i = 2 ; i < MAX ; i++ ) { primes[i] = true; } for ( int i = 2 ; i < MAX ; i++ ) { if ( primes[i] ) { for ( int j = 2*i ; j < MAX ; j += i ) { primes[j] = false; } } } }
} </lang>
- Output:
First 35 unprimeable numbers: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600th unprimeable number = 5,242 Least unprimeable number that ends in: 0 is 200 1 is 595,631 2 is 322 3 is 1,203,623 4 is 204 5 is 325 6 is 206 7 is 872,897 8 is 208 9 is 212,159
Julia
<lang julia>using Primes, Lazy, Formatting
function isunprimeable(n)
dvec = digits(n) for pos in 1:length(dvec), newdigit in 0:9 olddigit, dvec[pos] = dvec[pos], newdigit isprime(foldr((i, j) -> i + 10j, dvec)) && return false dvec[pos] = olddigit end return true
end
println("First 35 unprimeables: ", take(35, filter(isunprimeable, Lazy.range())))
println("\nThe 600th unprimeable is ",
collect(take(600, filter(isunprimeable, Lazy.range())))[end])
println("\nDigit First unprimeable ending with that digit") println("-----------------------------------------")
for dig in 0:9
n = first(filter(x -> (x % 10 == dig) && isunprimeable(x), Lazy.range())) println(" $dig ", lpad(format(n, commas=true), 9))
end
</lang>
- Output:
First 35 unprimeables: (200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890) The 600th unprimeable is 5242 Digit First unprimeable ending with that digit ----------------------------------------- 0 200 1 595,631 2 322 3 1,203,623 4 204 5 325 6 206 7 872,897 8 208 9 212,159
Lua
<lang lua>-- FUNCS: local function T(t) return setmetatable(t, {__index=table}) end table.filter = function(t,f) local s=T{} for _,v in ipairs(t) do if f(v) then s[#s+1]=v end end return s end table.firstn = function(t,n) local s=T{} n=n>#t and #t or n for i = 1,n do s[i]=t[i] end return s end
-- SIEVE: local sieve, S = {}, 10000000 for i = 2,S do sieve[i]=true end for i = 2,S do if sieve[i] then for j=i*i,S,i do sieve[j]=nil end end end
-- UNPRIMABLE: local unprimables, lowests = T{}, T{} local floor, log10 = math.floor, math.log10
local function unprimable(n)
if sieve[n] then return false end local nd = floor(log10(n))+1 for i = 1, nd do local pow10 = 10^(nd-i) for j = 0, 9 do local p = (floor(n/10/pow10) * 10 + j) * pow10 + (n % pow10) if sieve[p] then return false end end end return true
end
local n, done = 1, 0 while done < 10 do
if unprimable(n) then unprimables:insert(n) if not lowests[n%10] then lowests[n%10] = n done = done + 1 end end n = n + 1
end
-- OUTPUT: local function commafy(i) return tostring(i):reverse():gsub("(%d%d%d)","%1,"):reverse():gsub("^,","") end print("The first 35 unprimable numbers are:") print(unprimables:firstn(35):concat(" ")) print() print("The 600th unprimable number is: " .. commafy(unprimables[600])) print() print("The lowest unprimable number that ends in..") for i = 0, 9 do
print(" " .. i .. " is: " .. commafy(lowests[i]))
end</lang>
- Output:
The first 35 unprimable numbers are: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600th unprimable number is: 5,242 The lowest unprimable number that ends in.. 0 is: 200 1 is: 595,631 2 is: 322 3 is: 1,203,623 4 is: 204 5 is: 325 6 is: 206 7 is: 872,897 8 is: 208 9 is: 212,159
Pascal
Small improvement.When the check of value ending in "0" is not unprimable than I can jump over by 10, since the check already has checked those numbers ending in "1".."9".But in case of unprimable I am using a reduced version of the check
Results in runtime reduced from 1.8 secs downto 0.667 now to 0.46
<lang pascal>program unprimable;
{$IFDEF FPC}{$Mode Delphi}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
const
base = 10;
type
TNumVal = array[0..base-1] of NativeUint; TConvNum = record NumRest : TNumVal; LowDgt, MaxIdx : NativeUint; end;
var //global
PotBase, EndDgtFound : TNumVal; TotalCnt, EndDgtCnt :NativeUint;
procedure Init; var
i,val : NativeUint;
Begin
val := 1; For i := low(TNumVal) to High(TNumVal) do Begin EndDgtFound[i] :=0; PotBase[i] := val; val := val * Base; end; TotalCnt := 0; EndDgtCnt := 0;
end;
Procedure ConvertNum(n: NativeUint;var NConv:TConvNum); //extract digit position replace by "0" to get NumRest // 173 -> 170 -> 103 -> 073 var
i, dgt,n_red,n_mod: NativeUint;
begin
i := 0; n_red := n; with NConv do Begin repeat n_mod := n_red DIV Base; dgt := n_red-Base*n_mod; n_red := n_mod; IF i = 0 then LowDgt := dgt; NumRest[i]:= n-dgt*PotBase[i]; inc(i); until (i > High(TNumVal)) OR (n<PotBase[i]); MaxIdx := i-1; end;
end;
procedure CheckOutPut(n: NativeUint); Begin
IF TotalCnt > 600 then EXIT; IF TotalCnt <= 35 then write(n,' '); IF TotalCnt = 600 then Begin writeln; writeln; writeln('the 600.th unprimable number: ',n); end;
end;
function isPrime(n : NativeUint):boolean;inline; var
p : NativeUint;
Begin
result := (N=2) OR (N=3); IF result then EXIT; //now result = false IF (n<2) OR (NOT(ODD(n))) or (n mod 3= 0) then EXIT; p := 5; while p*p <= n do Begin if n mod p = 0 then Exit; p += 2; if n mod p = 0 then Exit; p += 4 end; result := true;
end;
procedure InsertFound(LowDgt,n:NativeUInt); Begin
inc(TotalCnt); IF EndDgtFound[LowDgt] = 0 then Begin EndDgtFound[LowDgt] := n; inc(EndDgtCnt); end;
end;
function CheckUnprimable(n:NativeInt):boolean; var
ConvNum : TConvNum; val,dgt,i,dtfac: NativeUint;
Begin
ConvertNum(n,ConvNum); result := false; //lowest digit with ConvNum do Begin val := NumRest[0]; For dgt := 0 to Base-1 do IF isPrime(val+dgt) then EXIT; dgt := LowDgt;
result := true; i := MaxIdx; IF NumRest[i] >= Base then Begin
//****Only for base=10 if even or divisible by 5***
IF Not(ODD(dgt)) OR (dgt=5) then Begin InsertFound(dgt,n); EXIT; end; end;
result := false; For i := MaxIdx downto 1 do Begin dtfac := PotBase[i]; val := NumRest[i]; For dgt := 0 to Base-1 do Begin IF isPrime(val) then EXIT; inc(val,dtfac); end; end; InsertFound(LowDgt,n); result := true; end;
end;
function CheckUnprimableReduced(n:NativeInt):boolean; //lowest digit already tested before var
ConvNum : TConvNum; val,dgt,i,dtfac: NativeUint;
Begin
ConvertNum(n,ConvNum); result := true; with ConvNum do Begin i := MaxIdx; IF NumRest[i] >= Base then Begin dgt := LowDgt; IF Not(ODD(dgt)) OR (dgt=5) then Begin InsertFound(dgt,n); EXIT; end; end;
result := false; For i := i downto 1 do Begin dtfac := PotBase[i]; val := NumRest[i]; For dgt := 0 to Base-1 do Begin IF isPrime(val) then EXIT; inc(val,dtfac); end; end; InsertFound(LowDgt,n); result := true; end;
end;
var
n,i : NativeUint;
Begin
init; n := Base; repeat If CheckUnprimable(n) then Begin CheckOutPut(n); For i := 1 to Base-1 do Begin IF CheckUnprimableReduced(n+i) then CheckOutPut(n+i); end; end; inc(n,Base); until EndDgtCnt = Base; writeln; For i := 0 to Base-1 do Writeln ('lowest digit ',i:2,' found first ',EndDgtFound[i]:7); writeln; writeln('There are ',TotalCnt,' unprimable numbers upto ',n);
end.</lang>
- Output:
200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 the 600.th unprimable number: 5242 lowest digit 0 found first 200 lowest digit 1 found first 595631 lowest digit 2 found first 322 lowest digit 3 found first 1203623 lowest digit 4 found first 204 lowest digit 5 found first 325 lowest digit 6 found first 206 lowest digit 7 found first 872897 lowest digit 8 found first 208 lowest digit 9 found first 212159 There are 298326 unprimable numbers upto 1203630
version with sieve
Needs a lot of memory, but gets fast. One has to take into account, that you have to check the highest digit so 1e9 leads to 1e9-1 = 999,999,999.
Base 18= 2*3*3 :lowest digit 7 found first 10,921,015,789
bases that are prime find their different digits quite early.
<lang pascal>program unprimable;
{$IFDEF FPC}
{$Mode Delphi} {$OPTIMIZATION ON,ALL}
{$ELSE}
//Delphi {$APPTYPE CONSOLE}
{$ENDIF} uses
sysutils;
const
Base = 10; dgtcnt = 9; Limit = Base* Base*Base*Base*Base* Base*Base*Base*Base;
{
Base = 18; dgtcnt = 8; Limit = Base*Base*Base*Base* Base*Base*Base*Base; * }
PrimeLimit = Limit+Base;
{
Limit = 1000*1000*1000; dgtcnt = trunc(ln(Limit-1)/ln(Base)); PrimeLimit = Trunc(exp(ln(base)*(dgtcnt+1)))+Base;
} type
TNumVal = array[0..dgtcnt] of NativeUint; TConvNum = record NumRest, Digits : TNumVal; num, MaxIdx : NativeUint; end;
var //global
ConvNum:TConvNum; PotBase: TNumVal; EndDgtFound : array[0..Base-1] of NativeUint; TotalCnt, EndDgtCnt :NativeUint;
//http://rosettacode.org/wiki/Sieve_of_Eratosthenes#alternative_using_wheel
var
pPrimes : pBoolean; //always initialized with 0 => false at startup primes: array of boolean;
function BuildWheel: NativeUint; var
myPrimes : pBoolean; wheelprimes :array[0..31] of byte; wheelSize,wpno, pr,pw,i, k: NativeUint;
begin
myPrimes := @primes[0]; pr := 1; myPrimes[1]:= true; WheelSize := 1;
wpno := 0; repeat inc(pr);
pw := pr; if pw > wheelsize then dec(pw,wheelsize); If myPrimes[pw] then begin k := WheelSize+1; //turn the wheel (pr-1)-times for i := 1 to pr-1 do begin inc(k,WheelSize); if k<primeLimit then move(myPrimes[1],myPrimes[k-WheelSize],WheelSize) else begin move(myPrimes[1],myPrimes[k-WheelSize],PrimeLimit-WheelSize*i); break; end; end; dec(k); IF k > primeLimit then k := primeLimit; wheelPrimes[wpno] := pr; myPrimes[pr] := false;
inc(wpno); //the new wheelsize WheelSize := k;
//sieve multiples of the new found prime i:= pr; i := i*i; while i <= k do begin myPrimes[i] := false; inc(i,pr); end; end; until WheelSize >= PrimeLimit;
//re-insert wheel-primes 1 still stays prime while wpno > 0 do begin dec(wpno); myPrimes[wheelPrimes[wpno]] := true; end; myPrimes[0] := false; myPrimes[1] := false;
BuildWheel := pr+1; writeln;
end;
procedure Sieve; var
myPrimes : pBoolean; sieveprime, fakt : NativeUint;
begin
setlength(Primes,PrimeLimit+1); pPrimes := @Primes[0]; myPrimes := pPrimes;
//pPrimes[1] = true is needed to stop for sieveprime = 2 // at //Search next smaller possible prime
sieveprime := BuildWheel;
//alternative here
//fillchar(pPrimes,SizeOf(pPrimes),chr(ord(true)));sieveprime := 2; repeat if myPrimes[sieveprime] then begin //eliminate 'possible prime' multiples of sieveprime //must go downwards //2*2 would unmark 4 -> 4*2 = 8 wouldnt be unmarked fakt := PrimeLimit DIV sieveprime; IF fakt < sieveprime then BREAK; repeat //Unmark myPrimes[sieveprime*fakt] := false; //Search next smaller possible prime repeat dec(fakt); until myPrimes[fakt]; until fakt < sieveprime; end; inc(sieveprime); until false; //remove 1 myPrimes[1] := false;
end;
procedure Init; var
i,val : NativeUint;
Begin
val := 1; For i := low(TNumVal) to High(TNumVal) do Begin EndDgtFound[i] :=0; PotBase[i] := val; val := val * Base; end; TotalCnt := 0; EndDgtCnt := 0;
end;
procedure OutConvNum(const NConv:TConvNum); var
i : NativeInt;
Begin
with NConv do begin writeln(num,MaxIdx:10); For i := MaxIdx Downto MaxIdx do write(Digits[i]); writeln; For i := MaxIdx Downto MaxIdx do write(NumRest[i]:8); end
end;
procedure IncConvertNum(var NConv:TConvNum); var
i,k : NativeInt;
Begin
with NConv do begin i := 0; repeat k := Digits[i]+1; IF k < Base then Begin Digits[i] := k; BREAK; end else Begin Digits[i] := k-Base; inc(i); end; until i > MaxIdx; IF i > MaxIdx then Begin Digits[i] := 1; MaxIdx := i; end;
k := num+1; i := MaxIdx; repeat NumRest[i]:= k-Digits[i]*PotBase[i]; dec(i); until i < 0; num := k; end;
end;
procedure IncConvertNumBase(var NConv:TConvNum); var
i,k : NativeInt;
Begin
with NConv do begin i := 1; Digits[0] := 0; repeat k := Digits[i]+1; IF k < Base then Begin Digits[i] := k; BREAK; end else Begin Digits[i] := k-Base; inc(i); end; until i > MaxIdx; IF i > MaxIdx then Begin Digits[i] := 1; MaxIdx := i; end; k := num+Base; i := MaxIdx; repeat NumRest[i]:= k-Digits[i]*PotBase[i]; dec(i); until i < 0; num := k; end;
end;
Procedure ConvertNum(n: NativeUint;var NConv:TConvNum); //extract digit position replace by "0" to get NumRest // 173 -> 170 -> 103 -> 073 var
i, dgt,n_red,n_div: NativeUint;
begin
i := 0; with NConv do Begin num := n; n_red := n; repeat n_div := n_red DIV Base; dgt := n_red-Base*n_div; n_red := n_div; Digits[i] := dgt; NumRest[i]:= n-dgt*PotBase[i]; inc(i); until (n_red= 0)OR (i > High(TNumVal)); MaxIdx := i-1; end;
end;
procedure InsertFound(dgt,n:NativeUInt); Begin
IF EndDgtFound[dgt] = 0 then Begin EndDgtFound[dgt] := n; inc(EndDgtCnt); end;
end;
function CheckUnprimable(const ConvNum:TConvNum):boolean; var
myPrimes : pBoolean; val,dgt,i,dtfac: NativeUint;
Begin
myPrimes := pPrimes; result := false; with ConvNum do Begin //lowest digit. Check only resulting odd numbers num > base val := NumRest[0]; dgt := 1- (val AND 1); repeat IF myPrimes[val+dgt] then EXIT; inc(dgt,2); until dgt >= Base;
For i := 1 to MaxIdx do Begin val := NumRest[i]; dtfac := PotBase[i]; IF (val >= BASE) then Begin IF NOt(Odd(val)) AND NOT(ODD(dtfac)) then continue; For dgt := 0 to Base-1 do Begin IF myPrimes[val] then EXIT; inc(val,dtfac); end; end else Begin For dgt := 0 to Base-1 do Begin IF myPrimes[val] then EXIT; inc(val,dtfac); end; end end; inc(TotalCnt); result := true; end;
end;
var
n,i,Lmt,Lmt10 : NativeUint;
Begin
init; Sieve; n := Base; Lmt10 := 10; Lmt := Base; ConvertNum(n,ConvNum); writeln('Base ',ConvNum.num); //InsertFound takes a lot of time.So check it as long as neccessary while EndDgtCnt <Base do Begin If CheckUnprimable(ConvNum) then Begin InsertFound(ConvNum.Digits[0],n); For i := 1 to Base-1 do Begin inc(n); IncConvertNum(ConvNum); IF CheckUnprimable(ConvNum) then InsertFound(ConvNum.Digits[0],n); end; inc(n); IncConvertNum(ConvNum); end else Begin inc(n,Base); IncConvertNumBase(ConvNum); end; if n >= Lmt10 then Begin writeln('There are ',TotalCnt,' unprimable numbers upto ',n); Lmt10 := Lmt10*10; end; if (Base <> 10) AND (n >= Lmt) then Begin writeln('There are ',TotalCnt,' unprimable numbers upto ',n); Lmt := Lmt*Base; end; end; //All found repeat If CheckUnprimable(ConvNum) then Begin For i := 1 to Base-1 do Begin inc(n); IncConvertNum(ConvNum); CheckUnprimable(ConvNum) end; inc(n); IncConvertNum(ConvNum); end else Begin inc(n,Base); IncConvertNumBase(ConvNum); end;
if n >= Lmt10 then Begin writeln('There are ',TotalCnt,' unprimable numbers upto ',n); Lmt10 := Lmt10*10; end;
if (Base <> 10) AND (n >= Lmt) then Begin writeln('There are ',TotalCnt,' unprimable numbers upto ',n); Lmt := Lmt*Base; end; until n >= Limit; writeln; For i := 0 to Base-1 do Writeln ('lowest digit ',i:2,' found first ',EndDgtFound[i]:7); writeln; writeln('There are ',TotalCnt,' unprimable numbers upto ',n); setlength(Primes,0);
end.</lang>
- Output:
Base 10: --followed by base 18 There are 0 unprimable numbers upto 20 There are 0 unprimable numbers upto 100 There are 40 unprimable numbers upto 1000 There are 1306 unprimable numbers upto 10000 There are 19188 unprimable numbers upto 100000 There are 243803 unprimable numbers upto 1000000 There are 2855168 unprimable numbers upto 10000000 There are 31837357 unprimable numbers upto 100000000 There are 345335295 unprimable numbers upto 1000000000 lowest digit 0 found first 200 lowest digit 1 found first 595631 lowest digit 2 found first 322 lowest digit 3 found first 1203623 lowest digit 4 found first 204 lowest digit 5 found first 325 lowest digit 6 found first 206 lowest digit 7 found first 872897 lowest digit 8 found first 208 lowest digit 9 found first 212159 There are 345335295 unprimable numbers upto 1,000,000,000 Base 18 There are 0 unprimable numbers upto 36 There are 0 unprimable numbers upto 36 There are 0 unprimable numbers upto 108 There are 0 unprimable numbers upto 324 There are 0 unprimable numbers upto 1008 There are 120 unprimable numbers upto 5832 There are 300 unprimable numbers upto 10008 There are 7066 unprimable numbers upto 100008 There are 7498 unprimable numbers upto 104976 There are 118508 unprimable numbers upto 1000008 There are 248858 unprimable numbers upto 1889568 There are 1634278 unprimable numbers upto 10000008 There are 6287718 unprimable numbers upto 34012224 There are 20277016 unprimable numbers upto 100000008 There are 141171269 unprimable numbers upto 612220032 There are 237623105 unprimable numbers upto 1000000008 There are 2682010638 unprimable numbers upto 10000000008 There are 2968851319 unprimable numbers upto 11019960576 lowest digit 0 found first 1332 lowest digit 1 found first 2909178757 lowest digit 2 found first 1334 lowest digit 3 found first 1335 lowest digit 4 found first 1336 lowest digit 5 found first 9046616783 lowest digit 6 found first 1338 lowest digit 7 found first 10,921,015,789 <= wow! lowest digit 8 found first 1340 lowest digit 9 found first 1341 lowest digit 10 found first 1342 lowest digit 11 found first 4414723463 lowest digit 12 found first 1344 lowest digit 13 found first 456383101 lowest digit 14 found first 1346 lowest digit 15 found first 1347 lowest digit 16 found first 1348 lowest digit 17 found first 3609203741 There are 2968851319 unprimable numbers upto 11,019,960,576
Perl
<lang perl>use strict; use warnings; use feature 'say'; use ntheory 'is_prime'; use enum qw(False True);
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub is_unprimeable {
my($n) = @_; return False if is_prime($n); my $chrs = length $n; for my $place (0..$chrs-1) { my $pow = 10**($chrs - $place - 1); my $this = substr($n, $place, 1) * $pow; map { return False if $this != $_ and is_prime($n - $this + $_ * $pow) } 0..9; } True
}
my($n, @ups); do { push @ups, $n if is_unprimeable(++$n); } until @ups == 600; say "First 35 unprimeables:\n" . join ' ', @ups[0..34]; printf "\n600th unprimeable: %s\n", comma $ups[599];
map {
my $x = $_; while ($x += 10) { last if is_unprimeable($x) } say "First unprimeable that ends with $_: " . sprintf "%9s", comma $x;
} 0..9;</lang>
- Output:
First 35 unprimeables: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 600th unprimeable: 5,242 First unprimeable that ends with 0: 200 First unprimeable that ends with 1: 595,631 First unprimeable that ends with 2: 322 First unprimeable that ends with 3: 1,203,623 First unprimeable that ends with 4: 204 First unprimeable that ends with 5: 325 First unprimeable that ends with 6: 206 First unprimeable that ends with 7: 872,897 First unprimeable that ends with 8: 208 First unprimeable that ends with 9: 212,159
Phix
<lang Phix>printf(1,"The first 35 unprimeable numbers are:\n") integer count := 0, -- counts all unprimeable numbers
countFirst = 0, i = 100
sequence firstNum = repeat(0,10) -- stores the first unprimeable number ending with each digit atom t1 = time()+1 while countFirst<10 do
if not is_prime(i) then -- unprimeable number must be composite string s = sprintf("%d",i), b = s integer le := length(s) bool primeable = false for j=1 to le do for k='0' to '9' do if s[j]!=k then b[j] = k integer n = to_integer(b) if is_prime(n) then primeable = true exit end if end if end for if primeable then exit end if b[j] = s[j] -- restore j'th digit to what it was originally end for if not primeable then integer lastDigit = s[le]-'0'+1 if firstNum[lastDigit] == 0 then firstNum[lastDigit] = i countFirst += 1 end if count += 1 if count <= 35 then printf(1,"%d ", i) elsif count == 600 then printf(1,"\n\nThe 600th unprimeable number is: %,d\n\n",i) end if end if end if if time()>t1 then printf(1,"checking %d, %d `endswiths` found\r",{i,countFirst}) t1 = time()+1 end if i += 1
end while
printf(1,"The first unprimeable number that ends in:\n") for i=1 to 10 do
printf(1," %d is: %,9d\n", {i-1, firstNum[i]})
end for</lang>
- Output:
The first 35 unprimeable numbers are: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600th unprimeable number is: 5,242 The first unprimeable number that ends in: 0 is: 200 1 is: 595,631 2 is: 322 3 is: 1,203,623 4 is: 204 5 is: 325 6 is: 206 7 is: 872,897 8 is: 208 9 is: 212,159
Pike
Not the fastest way of doing this, but using string manipulation seemed like the obvious Pike way to do it. <lang Pike> bool is_unprimeable(int i) {
string s = i->digits(); for(int offset; offset < sizeof(s); offset++) {
foreach("0123456789"/1, string repl) { array chars = s/1; chars[offset] = repl; int testme = (int)(chars*""); if( testme->probably_prime_p() ) return false; }
} return true;
}
void main() {
int i, count; array unprimes = ({}); mapping first_enders = ([]); // first unprimeable ending with each digit while(sizeof(first_enders) != 10) {
i++; if( is_unprimeable(i) ) { count++; unprimes += ({ i }); string last_digit = i->digits()[<0..]; if( !first_enders[last_digit] ) first_enders[last_digit] = i; } werror("%d\r", i); // Progress output
} write("First 35 unprimeables: %s\n\n", (array(string))unprimes[0..34]*" "); write("The 600th unprimeable is %d\n\n", unprimes[599]); write("The first unprimeable number that ends in\n"); foreach(sort(indices(first_enders)), string e) {
write(" %s is: %9d\n", e, first_enders[e]);
}
}</lang> Output:
First 35 unprimeables: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600th unprimeable is 5242 The first unprimeable number that ends in 0 is: 200 1 is: 595631 2 is: 322 3 is: 1203623 4 is: 204 5 is: 325 6 is: 206 7 is: 872897 8 is: 208 9 is: 212159
Python
<lang python>from itertools import count, islice
def primes(_cache=[2, 3]):
yield from _cache for n in count(_cache[-1]+2, 2): if isprime(n): _cache.append(n) yield n
def isprime(n, _seen={0: False, 1: False}):
def _isprime(n): for p in primes(): if p*p > n: return True if n%p == 0: return False
if n not in _seen: _seen[n] = _isprime(n) return _seen[n]
def unprime():
for a in count(1): d = 1 while d <= a: base = (a//(d*10))*(d*10) + (a%d) # remove current digit if any(isprime(y) for y in range(base, base + d*10, d)): break d *= 10 else: yield a
print('First 35:')
print(' '.join(str(i) for i in islice(unprime(), 35)))
print('\nThe 600-th:') print(list(islice(unprime(), 599, 600))[0]) print()
first, need = [False]*10, 10 for p in unprime():
i = p%10 if first[i]: continue
first[i] = p need -= 1 if not need: break
for i,v in enumerate(first):
print(f'{i} ending: {v}')</lang>
- Output:
First 35: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600-th: 5242 0 ending: 200 1 ending: 595631 2 ending: 322 3 ending: 1203623 4 ending: 204 5 ending: 325 6 ending: 206 7 ending: 872897 8 ending: 208 9 ending: 212159
Racket
<lang racket>#lang racket
(require math/number-theory)
(define cached-prime?
(let ((hsh# (make-hash))) (λ (p) (hash-ref! hsh# p (λ () (prime? p))))))
(define (zero-digit n d)
(define p (expt 10 d)) (+ (remainder n p) (* 10 p (quotient n (* p 10)))))
(define (primeable? n)
(or (cached-prime? n) (for*/first ((d (in-range (add1 (order-of-magnitude n)))) (n0 (in-value (zero-digit n d))) (p (in-value (expt 10 d))) (r (in-range 10)) (n+ (in-value (+ n0 (* r p)))) #:when (cached-prime? n+)) n+)))
(define unprimeable? (negate primeable?))
(module+
main (printf "First 35 unprimeable numbers: ~a~%" (let recur ((i 0) (n 1) (acc null)) (cond [(= i 35) (reverse acc)] [(unprimeable? n) (recur (add1 i) (add1 n) (cons n acc))] [else (recur i (add1 n) acc)])))
(printf "600th unprimeable number: ~a~%" (let recur ((i 0) (n 1) (u #f)) (cond [(= i 600) u] [(unprimeable? n) (recur (add1 i) (add1 n) n)] [else (recur i (add1 n) u)])))
(for ((d 10)) (printf "Least unprimeable number ending in ~a = ~a~%" d (for/first ((i (in-range (+ 100 d) +Inf.0 10)) #:when (unprimeable? i)) i))))
(module+ test
(require rackunit) (check-equal? (zero-digit 1234 2) 1034) (check-equal? (primeable? 10) 11) (check-true (unprimeable? 200)) (check-false (unprimeable? 201)))</lang>
- Output:
First 35 unprimeable numbers: (200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890) 600th unprimeable number: 5242 Least unprimeable number ending in 0 = 200 Least unprimeable number ending in 1 = 595631 Least unprimeable number ending in 2 = 322 Least unprimeable number ending in 3 = 1203623 Least unprimeable number ending in 4 = 204 Least unprimeable number ending in 5 = 325 Least unprimeable number ending in 6 = 206 Least unprimeable number ending in 7 = 872897 Least unprimeable number ending in 8 = 208 Least unprimeable number ending in 9 = 212159
Raku
(formerly Perl 6)
<lang perl6>use ntheory:from<Perl5> <is_prime>; use Lingua::EN::Numbers;
sub is-unprimeable (\n) {
return False if n.&is_prime; my \chrs = n.chars; for ^chrs -> \place { my \pow = 10**(chrs - place - 1); my \this = n.substr(place, 1) * pow; ^10 .map: -> \dgt { next if this == dgt; return False if is_prime(n - this + dgt * pow) } } True
}
my @ups = lazy ^∞ .grep: { .&is-unprimeable };
say "First 35 unprimeables:\n" ~ @ups[^35];
say "\n{ordinal-digit(600, :u)} unprimeable: " ~ comma( @ups[599] ) ~ "\n";
^10 .map: -> \n {
print "First unprimeable that ends with {n}: " ~ sprintf "%9s\n", comma (n, *+10 … *).race.first: { .&is-unprimeable }
}</lang>
- Output:
First 35 unprimeables: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 600ᵗʰ unprimeable: 5,242 First unprimeable that ends with 0: 200 First unprimeable that ends with 1: 595,631 First unprimeable that ends with 2: 322 First unprimeable that ends with 3: 1,203,623 First unprimeable that ends with 4: 204 First unprimeable that ends with 5: 325 First unprimeable that ends with 6: 206 First unprimeable that ends with 7: 872,897 First unprimeable that ends with 8: 208 First unprimeable that ends with 9: 212,159
REXX
Some effort was put into the optimization of the generation of primes (the genP subroutine). <lang rexx>/*REXX program finds and displays unprimeable numbers (non─negative integers). */ parse arg n x hp . /*obtain optional arguments from the CL*/ if n== | n=="," then n= 35 /*Not specified? Then use the default.*/ if x== | x=="," then x= 600 /* " " " " " " */ if hp== | hp=="," then hp= 10000000 /* " " " " " " */ eds=4; ed.1= 1; ed.2= 3; ed.3= 7; ed.4= 9 /*the "end" digits which are prime; #>9*/ call genP hp /*generate primes up to & including HP.*/
- = 0 /*number of unprimeable numbers so far.*/
$$=; $.=. /*a list " " " " " */
/*1─ and 2─digit #'s are all primeable.*/ do j=100; if !.j then iterate /*Prime? Unprimeable must be composite*/ Lm= length(j) /*obtain the length-1 of the number J. */ meat= left(j, Lm) /*obtain the first Lm digits of J. */ /* [↑] examine the "end" digit of J. */ do e_=1 for eds; new= meat || ed.e_ /*obtain a different number (than J).*/ if new==j then iterate /*Is it the original number? Then skip.*/ if !.new then iterate j /*This new number a prime? " " */ end /*e_*/ /* [↑] examine a new 1st digit of J. */ do f_=0 for 10; new= (f_||meat) + 0 /*obtain a different number (than J).*/ if new==j then iterate /*Is it the original number? Then skip.*/ if !.new then iterate j /*This new number a prime? " " */ end /*f_*/ /* [↑] examine the front digit of J. */ do a_= 2 for Lm-1 /*traipse through the middle digits. */ meat= left(j, a_ - 1) /*use a number of left─most dec. digits*/ rest= substr(j, a_ + 1) /* " " " " right─most " " */ do n_=0 for 10 /*traipse through all 1─digit numbers. */ new= meat || n_ || rest /*construct new number, like a phoenix.*/ if new==j then iterate /*Is it the original number? Then skip.*/ if !.new then iterate j /*This new number a prime? " " */ end /*n_*/ end /*a_*/ #= # + 1 /*bump the count of unprimeable numbers*/ if #<=n then $$= $$ commas(j) /*maybe add unprimeable # to $$ list.*/ if #==x then $.ox= commas(j) /*assign the Xth unprimeable number.*/ parse var j -1 _ /*obtain the right─most dec digit of J.*/ if $._==. then $._= j /*the 1st unprimeable # that ends in _.*/ if $.3==. then iterate; if $.7==. then iterate /*test if specific #'s found.*/ if $.1==. then iterate; if $.9==. then iterate /* " " " " " */ leave /*if here, then we're done. */ end /*j*/
if n>0 then do; say center(' first ' n "unprimeable numbers ", 139, '═')
say strip($$); say end
if x>0 then say ' the ' th(x) " unprimeable number is: " $.ox say
do o=0 for 10; if length($.o)==0 then iterate say ' the first unprimeable number that ends in ' o " is:"right(commas($.o),11) end /*o*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do c=length(?)-3 to 1 by -3; ?=insert(',', ?, c); end; return ? th:procedure;parse arg x;return x||word('th st nd rd',1+(x//10)*(x//100%10\==1)*(x//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6= 13; @.7=17; @.8=19; @.9=23; @.10=29; #p=10
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1; !.19=1; !.23=1; !.29=1 do lim=100 until lim*lim>=hp /*only keep primes up to the sqrt(hp). */ end /*lim*/ /* [↑] find limit for storing primes. */ do j=@.#p+2 by 2 to hp /*only find odd primes from here on. */ parse var j -1 _;if _==5 then iterate /*Get last digit; is last digit a "5" ?*/ if j// 3==0 then iterate /*is J divisible by 3? Then not prime*/ if j// 7==0 then iterate /* " " " " 7? " " " */ if j//11==0 then iterate /* " " " " 11? " " " */ if j//13==0 then iterate /* " " " " 13? " " " */ if j//17==0 then iterate /* " " " " 17? " " " */ if j//19==0 then iterate /* " " " " 19? " " " */ if j//23==0 then iterate /* " " " " 23? " " " */ if j//29==0 then iterate /* " " " " 29? " " " */ do k=11 while k*k<=j /*divide by some generated odd primes. */ if j // @.k==0 then iterate j /*Is J divisible by P? Then not prime*/ end /*k*/ /* [↓] a prime (J) has been found. */ #p= #p+1; if #p<=lim then @.#p=j; !.j=1 /*bump prime count; assign prime to @.*/ end /*j*/; return</lang>
- output when using the default inputs:
(Shown at 5/6 size.)
══════════════════════════════════════════════════════ first 35 unprimeable numbers ══════════════════════════════════════════════════════ 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 the 600th unprimeable number is: 5,242 the first unprimeable number that ends in 0 is: 200 the first unprimeable number that ends in 1 is: 595,631 the first unprimeable number that ends in 2 is: 322 the first unprimeable number that ends in 3 is: 1,203,623 the first unprimeable number that ends in 4 is: 204 the first unprimeable number that ends in 5 is: 325 the first unprimeable number that ends in 6 is: 206 the first unprimeable number that ends in 7 is: 872,897 the first unprimeable number that ends in 8 is: 208 the first unprimeable number that ends in 9 is: 212,159
Rust
<lang rust>// main.rs mod bit_array; mod prime_sieve;
use prime_sieve::PrimeSieve;
// return number of decimal digits fn count_digits(mut n: u32) -> u32 {
let mut digits = 0; while n > 0 { n /= 10; digits += 1; } digits
}
// return the number with one digit replaced fn change_digit(mut n: u32, mut index: u32, new_digit: u32) -> u32 {
let mut p = 1; let mut changed = 0; while index > 0 { changed += p * (n % 10); p *= 10; n /= 10; index -= 1; } changed += (10 * (n / 10) + new_digit) * p; changed
}
fn unprimeable(sieve: &PrimeSieve, n: u32) -> bool {
if sieve.is_prime(n as usize) { return false; } let d = count_digits(n); for i in 0..d { for j in 0..10 { let m = change_digit(n, i, j); if m != n && sieve.is_prime(m as usize) { return false; } } } true
}
fn main() {
let mut count = 0; let mut n = 100; let mut lowest = vec![0; 10]; let mut found = 0; let sieve = PrimeSieve::new(10000000); println!("First 35 unprimeable numbers:"); while count < 600 || found < 10 { if unprimeable(&sieve, n) { if count < 35 { if count > 0 { print!(", "); } print!("{}", n); } count += 1; if count == 600 { println!("\n600th unprimeable number: {}", n); } let last_digit = n as usize % 10; if lowest[last_digit] == 0 { lowest[last_digit] = n; found += 1; } } n += 1; } for i in 0..10 { println!("Least unprimeable number ending in {}: {}", i, lowest[i]); }
}</lang>
<lang rust>// prime_sieve.rs use crate::bit_array;
pub struct PrimeSieve {
composite: bit_array::BitArray,
}
impl PrimeSieve {
pub fn new(limit: usize) -> PrimeSieve { let mut sieve = PrimeSieve { composite: bit_array::BitArray::new(limit / 2), }; let mut p = 3; while p * p <= limit { if !sieve.composite.get(p / 2 - 1) { let inc = p * 2; let mut q = p * p; while q <= limit { sieve.composite.set(q / 2 - 1, true); q += inc; } } p += 2; } sieve } pub fn is_prime(&self, n: usize) -> bool { if n < 2 { return false; } if n % 2 == 0 { return n == 2; } !self.composite.get(n / 2 - 1) }
}</lang>
<lang rust>// bit_array.rs pub struct BitArray {
array: Vec<u32>,
}
impl BitArray {
pub fn new(size: usize) -> BitArray { BitArray { array: vec![0; (size + 31) / 32], } } pub fn get(&self, index: usize) -> bool { let bit = 1 << (index & 31); (self.array[index >> 5] & bit) != 0 } pub fn set(&mut self, index: usize, new_val: bool) { let bit = 1 << (index & 31); if new_val { self.array[index >> 5] |= bit; } else { self.array[index >> 5] &= !bit; } }
}</lang>
- Output:
First 35 unprimeable numbers: 200, 204, 206, 208, 320, 322, 324, 325, 326, 328, 510, 512, 514, 515, 516, 518, 530, 532, 534, 535, 536, 538, 620, 622, 624, 625, 626, 628, 840, 842, 844, 845, 846, 848, 890 600th unprimeable number: 5242 Least unprimeable number ending in 0: 200 Least unprimeable number ending in 1: 595631 Least unprimeable number ending in 2: 322 Least unprimeable number ending in 3: 1203623 Least unprimeable number ending in 4: 204 Least unprimeable number ending in 5: 325 Least unprimeable number ending in 6: 206 Least unprimeable number ending in 7: 872897 Least unprimeable number ending in 8: 208 Least unprimeable number ending in 9: 212159
Sidef
<lang ruby>func is_unprimeable(n) {
var t = 10*floor(n/10) for k in (t+1 .. t+9 `by` 2) { return false if k.is_prime }
if (n.is_div(2) || n.is_div(5)) { return true if !is_prime(n%10) return true if (n % 10**n.ilog(10) > 9) }
for k in (1 .. n.ilog(10)) { var u = 10**k var v = (n - (u * (floor(n/u) % 10))) 0..9 -> any {|d| is_prime(v + d*u) } && return false }
return true
}
with (35) {|n|
say ("First #{n} unprimeables:\n", is_unprimeable.first(n).join(' '))
}
with (600) {|n|
say ("\n#{n}th unprimeable: ", is_unprimeable.nth(n), "\n")
}
for d in (0..9) {
say ("First unprimeable that ends with #{d}: ", 1..Inf -> lazy.map {|k| k*10 + d }.grep(is_unprimeable).first)
}</lang>
- Output:
First 35 unprimeables: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 600th unprimeable: 5242 First unprimeable that ends with 0: 200 First unprimeable that ends with 1: 595631 First unprimeable that ends with 2: 322 First unprimeable that ends with 3: 1203623 First unprimeable that ends with 4: 204 First unprimeable that ends with 5: 325 First unprimeable that ends with 6: 206 First unprimeable that ends with 7: 872897 First unprimeable that ends with 8: 208 First unprimeable that ends with 9: 212159
Wren
<lang ecmascript>import "/fmt" for Fmt import "/math" for Int
System.print("The first 35 unprimeable numbers are:") var count = 0 // counts all unprimeable numbers var firstNum = List.filled(10, 0) // stores the first unprimeable number ending with each digit var i = 100 var countFirst = 0 while (countFirst < 10) {
if (!Int.isPrime(i)) { // unprimeable number must be composite var s = "%(i)" var le = s.count var b = s.bytes.toList var outer = false for (j in 0...le) { for (k in 48..57) { if (s[j].bytes[0] != k) { b[j] = k var bb = b.reduce("") { |acc, byte| acc + String.fromByte(byte) } var n = Num.fromString(bb) if (Int.isPrime(n)) { outer = true break } } } if (outer) break b[j] = s[j].bytes[0] // restore j'th digit to what it was originally } if (!outer) { var lastDigit = s[-1].bytes[0] - 48 if (firstNum[lastDigit] == 0) { firstNum[lastDigit] = i countFirst = countFirst + 1 } count = count + 1 if (count <= 35) System.write("%(i) ") if (count == 35) System.write("\n\nThe 600th unprimeable number is: ") if (count == 600) System.print("%(Fmt.dc(0, i))\n") } } i = i + 1
}
System.print("The first unprimeable number that ends in:") for (i in 0...10) System.print(" %(i) is: %(Fmt.dc(9, firstNum[i]))")</lang>
- Output:
The first 35 unprimeable numbers are: 200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600th unprimeable number is: 5,242 The first unprimeable number that ends in: 0 is: 200 1 is: 595,631 2 is: 322 3 is: 1,203,623 4 is: 204 5 is: 325 6 is: 206 7 is: 872,897 8 is: 208 9 is: 212,159
zkl
GNU Multiple Precision Arithmetic Library and fast prime checking
<lang zkl>var [const] BI=Import("zklBigNum"); // libGMP
fcn isUnprimeable(n){ //--> n (!0) or Void, a filter
bn,t := BI(0),n/10*10; foreach k in ([t+1..t+9,2]){ if(bn.set(k).probablyPrime()) return(Void.Skip) } if(n==n/2*2 or n==n/5*5){ if(not bn.set(n%10).probablyPrime()) return(n); if( (n % (10).pow(n.toFloat().log10()) ) > 9) return(n); } foreach k in ([1 .. n.toFloat().log10()]){ u,v := (10).pow(k), (n - (u * ((n/u) % 10))); foreach d in (10){ if(bn.set(v + d*u).probablyPrime()) return(Void.Skip); } } n
} fcn isUnprimeableW{ [100..].tweak(isUnprimeable) } // --> iterator</lang> <lang zkl>isUnprimeableW().walk(35).concat(" ").println(); println("The 600th unprimeable number is: %,d".fmt(isUnprimeableW().drop(600).value));
s,ups := 10, List.createLong(10,0); foreach up in (isUnprimeableW())
{ d:=up%10; if(ups[d]==0){ ups[d]=up; if((s-=1)<=0) break; } }
println("The first unprimeable number that ends in:"); foreach n in (10){ println("%d is %8,d".fmt(n,ups[n])) }</lang>
- Output:
200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890 The 600th unprimeable number is: 5,242 The first unprimeable number that ends in: 0 is 200 1 is 595,631 2 is 322 3 is 1,203,623 4 is 204 5 is 325 6 is 206 7 is 872,897 8 is 208 9 is 212,159
(arithmetic)