Unprimeable numbers: Difference between revisions
m (added new link) |
|||
Line 47: | Line 47: | ||
;Also see: |
;Also see: |
||
:* the OEIS entry: [https://oeis.org/A118118 A118118 (unprimeable)] |
:* the OEIS entry: [https://oeis.org/A118118 A118118 (unprimeable)] |
||
:* with some useful counts to compare [http://www.numbersaplenty.com/set/unprimeable_number/ unprimeable number] |
|||
:* the Wiktionary entry (reference from below): [https://en.wiktionary.org/wiki/unprimeable (arithmetic definition) unprimeable] |
:* the Wiktionary entry (reference from below): [https://en.wiktionary.org/wiki/unprimeable (arithmetic definition) unprimeable] |
||
:* from the Adam Spencer book (page 200): ''Adam Spencer's World of Numbers'' (Xoum Publishing) |
:* from the Adam Spencer book (page 200): ''Adam Spencer's World of Numbers'' (Xoum Publishing) |
Revision as of 07:52, 5 December 2019
- 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)
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".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
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
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
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)