Unprimeable numbers

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   600^th   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

Perl 6

Works with: Rakudo version 2019.11

<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.*/

1. = 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   ⁵/₆   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

Translation of: Sidef

Library: GMP

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