Unprimeable numbers
- 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)
- the Wiktionary entry (reference from below): (arithmetic definition) unprimeable
- from the Adam Spencer book (page 200): Adam Spencer's World of Numbers (Xoum Publishing)
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
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".
Results in runtime reduced from 1.8 secs downto 0.667
<lang pascal>program unprimable;
{$IFDEF FPC}{$Mode Delphi}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
const
base = 10;
type
TNumDigit = array[0..base-1] of NativeUint; TConvNum = record NumRest, Pot10 : TNumDigit; LowDgt, MaxIdx : NativeUint; end;
var //global
EndDgtFound : TNumDigit; TotalCnt, EndDgtCnt :NativeUint;
procedure Init(var N:TConvNum); var
i,val : NativeUint;
Begin
val := 1; For i := low(TNumDigit) to High(TNumDigit) do Begin EndDgtFound[i] :=0; N.Pot10[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, val: NativeUint;
begin
i := 0; with NConv do Begin repeat val := (n DIV Pot10[i]) MOD Base; IF i = 0 then LowDgt := val; NumRest[i]:= n-val*Pot10[i]; inc(i); until (i > High(TNumDigit)) OR (n<Pot10[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(' 600.th ',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;
function CheckUnprimable(n:NativeInt;var ConvNum:TConvNum):boolean; var
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 IF Not(ODD(dgt)) OR (dgt=5) then Begin IF EndDgtFound[LowDgt] = 0 then Begin EndDgtFound[LowDgt] := n; inc(EndDgtCnt); end; inc(TotalCnt); EXIT; end; end; result := false; For i := MaxIdx downto 1 do Begin dtfac := Pot10[i]; val := NumRest[i]; For dgt := 0 to Base-1 do Begin IF isPrime(val) then EXIT; inc(val,dtfac); end; end; IF EndDgtFound[LowDgt] = 0 then Begin EndDgtFound[LowDgt] := n; inc(EndDgtCnt); end; inc(TotalCnt); result := true; end;
end;
var
ConvNum : TConvNum; n,i : NativeUint;
Begin
init(ConvNum); n := 10; repeat IF Not(isPrime(n)) then If CheckUnprimable(n,ConvNum) then Begin CheckOutPut(n); For i := 1 to Base-1 do IF CheckUnprimable(n+i,ConvNum) then CheckOutPut(n+i) end; inc(n,Base); until EndDgtCnt = Base; writeln; For i := 0 to Base-1 do Writeln ('Enddigit ',i,' found first ',EndDgtFound[i]:7);
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 600.th 5242 Enddigit 0 found first 200 Enddigit 1 found first 595631 Enddigit 2 found first 322 Enddigit 3 found first 1203623 Enddigit 4 found first 204 Enddigit 5 found first 325 Enddigit 6 found first 206 Enddigit 7 found first 872897 Enddigit 8 found first 208 Enddigit 9 found first 212159
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*/ 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 j=@.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</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 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
<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
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
br>(arithmetic)