Unprimeable numbers

From Rosetta Code
Unprimeable numbers 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.
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



Go[edit]

Simple brute force (no sieves, memoization or bigint.ProbablyPrime) as there is not much need for speed here.

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]))
}
}
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


Julia[edit]

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
 
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

Pascal[edit]

Translation of: Go
Works with: Free 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

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.
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[edit]

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 there different digits quite early.

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.
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 6[edit]

Works with: Rakudo version 2019.11
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 }
}
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

Phix[edit]

Translation of: Go
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
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

REXX[edit]

Some effort was put into the optimization of the generation of primes   (the   genP   subroutine).

/*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*/
L= length(j) /*obtain the length of the number J. */
meat= left(j, L-1) /*obtain the first L-1 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 not prime? " " */
end /*e_*/
 
meat= right(j, L-1) /*obtain the last L-1 digits of J. */
/* [↑] 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 not prime? " " */
end /*f_*/ /* [↑] examine the front digit of J. */
do a_= 2 to L-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 not prime? " " */
end /*n_*/
end /*a_*/
#= # + 1 /*bump the count of unprimeable numbers*/
if #<n then $$= $$ j /*maybe add unprimeable # to $$ list.*/
if #==x then $.ox= j /*assign the Xth unprimeable number.*/
_= right(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 ", 135, '═')
say strip($$); say
end
if x>0 then say ' the ' th(x) " unprimeable number is: " commas($.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; nP=6 /*assign low primes; # primes. */
 !.=0;  !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /*assign some low semaphore primes. */
do lim=100 until lim*lim>=hp; end /*only keep primes up to the sqrt(hp). */
do [email protected].nP+4 by 2 to hp /*only find odd primes from here on. */
if j// 3==0 then iterate /*is J divisible by 3? Then not prime.*/
parse var j '' -1 _;if _==5 then iterate /*Is last digit a "5"? " " " */
if j// 7==0 then iterate /*is J divisible by 7? Then not prime.*/
if j//11==0 then iterate /*is J divisible by 11? Then not prime.*/
if j//13==0 then iterate /*is J divisible by 13? Then not prime.*/
do k=7 while k*k<=j /*divide by some known low 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. */
nP= nP+1; if nP<=lim then @.nP=j; !.j=1 /*bump prime count; assign prime to @.*/
end /*j*/; return
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

     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

Sidef[edit]

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)
}
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

zkl[edit]

Translation of: Sidef
Library: GMP
GNU Multiple Precision Arithmetic Library and fast prime checking
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
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])) }
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

br>(arithmetic)