How to resolve the algorithm Unprimeable numbers step by step in the Go programming language

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm Unprimeable numbers step by step in the Go programming language

Table of Contents

Problem Statement

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.

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.

Show all output here, on this page.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Unprimeable numbers step by step in the Go programming language

The provided Go code finds and prints the first 35 unprimeable numbers and the 600th unprimeable number, as well as the first unprimeable number ending with each digit from 0 to 9. A number is considered unprimeable if it's composite (not prime) and cannot be transformed into a prime number by changing a single digit.

  • isPrime function: Checks whether a given number is prime. It uses various optimizations to efficiently determine primality.
  • commatize function: Converts a number to a comma-separated string representation for readability.
  • main function:
    • outer loop: Iterates through numbers starting from 100 and checks if they are unprimeable.
    • if the number is prime, the loop continues to the next number.
    • if the number is composite, it tries to change each digit to every other digit (except itself) and checks if the resulting number is prime. If any of the modified numbers are prime, the loop continues to the next number.
    • if none of the modified numbers are prime, the number is considered unprimeable, and its count is incremented.
    • firstNum array: Stores the first unprimeable number ending with each digit from 0 to 9.
    • printing: The program prints the first 35 unprimeable numbers, the 600th unprimeable number with commas for readability, and the first unprimeable number ending with each digit.

Source code in the go programming language

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


  

You may also check:How to resolve the algorithm Pentagram step by step in the REXX programming language
You may also check:How to resolve the algorithm Farey sequence step by step in the Yabasic programming language
You may also check:How to resolve the algorithm Pascal matrix generation step by step in the Stata programming language
You may also check:How to resolve the algorithm Arithmetic/Integer step by step in the Yabasic programming language
You may also check:How to resolve the algorithm Haversine formula step by step in the Julia programming language