How to resolve the algorithm Self numbers step by step in the Go programming language
How to resolve the algorithm Self numbers step by step in the Go programming language
Table of Contents
Problem Statement
A number n is a self number if there is no number g such that g + the sum of g's digits = n. So 18 is not a self number because 9+9=18, 43 is not a self number because 35+5+3=43.
The task is: 224036583-1 is a Mersenne prime, claimed to also be a self number. Extra credit to anyone proving it.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Self numbers step by step in the Go programming language
First approach:
This approach uses a brute-force algorithm to find self numbers. It starts from 1 and iterates through all numbers until it finds 100 million self numbers. For each number, it calculates the sum of its digits and checks if the sum is equal to the number itself. If it is, the number is a self number.
The time complexity of this approach is O(n^2), where n is the number of numbers to check. This is because for each number, it iterates through all smaller numbers to calculate the sum of its digits.
Second approach:
This approach uses a sieve algorithm to find self numbers. It starts with a list of all numbers from 0 to 2 billion. Then, it iterates through all numbers that are not already marked as self numbers. For each number, it calculates the sum of its digits and marks all numbers that are equal to its sum as self numbers.
The time complexity of this approach is O(n log n), where n is the number of numbers in the list. This is because the sieve algorithm only iterates through the list once and marks each number as a self number if its sum is equal to itself.
Third approach:
This approach uses a precomputed table of digit sums to find self numbers. It starts by initializing a table of digit sums for all numbers from 0 to 9999. Then, it iterates through all numbers that are not already marked as self numbers. For each number, it calculates the sum of its digits using the precomputed table and checks if the sum is equal to the number itself. If it is, the number is a self number.
The time complexity of this approach is O(n), where n is the number of numbers to check. This is because the precomputed table allows it to calculate the sum of digits in constant time.
Comparison of the three approaches:
The first approach is the simplest but also the slowest. The second approach is faster than the first approach but it is still relatively slow. The third approach is the fastest of the three approaches, and it is also the most efficient in terms of memory usage.
Conclusion:
The best approach for finding self numbers depends on the specific requirements of the application. If speed is the most important factor, the third approach is the best choice. If memory usage is the most important factor, the second approach is the best choice. If simplicity is the most important factor, the first approach is the best choice.
Source code in the go programming language
package main
import (
"fmt"
"time"
)
func sumDigits(n int) int {
sum := 0
for n > 0 {
sum += n % 10
n /= 10
}
return sum
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func main() {
st := time.Now()
count := 0
var selfs []int
i := 1
pow := 10
digits := 1
offset := 9
lastSelf := 0
for count < 1e8 {
isSelf := true
start := max(i-offset, 0)
sum := sumDigits(start)
for j := start; j < i; j++ {
if j+sum == i {
isSelf = false
break
}
if (j+1)%10 != 0 {
sum++
} else {
sum = sumDigits(j + 1)
}
}
if isSelf {
count++
lastSelf = i
if count <= 50 {
selfs = append(selfs, i)
if count == 50 {
fmt.Println("The first 50 self numbers are:")
fmt.Println(selfs)
}
}
}
i++
if i%pow == 0 {
pow *= 10
digits++
offset = digits * 9
}
}
fmt.Println("\nThe 100 millionth self number is", lastSelf)
fmt.Println("Took", time.Since(st))
}
package main
import (
"fmt"
"time"
)
func sieve() []bool {
sv := make([]bool, 2*1e9+9*9 + 1)
n := 0
var s [8]int
for a := 0; a < 2; a++ {
for b := 0; b < 10; b++ {
s[0] = a + b
for c := 0; c < 10; c++ {
s[1] = s[0] + c
for d := 0; d < 10; d++ {
s[2] = s[1] + d
for e := 0; e < 10; e++ {
s[3] = s[2] + e
for f := 0; f < 10; f++ {
s[4] = s[3] + f
for g := 0; g < 10; g++ {
s[5] = s[4] + g
for h := 0; h < 10; h++ {
s[6] = s[5] + h
for i := 0; i < 10; i++ {
s[7] = s[6] + i
for j := 0; j < 10; j++ {
sv[s[7]+j+n] = true
n++
}
}
}
}
}
}
}
}
}
}
return sv
}
func main() {
st := time.Now()
sv := sieve()
count := 0
fmt.Println("The first 50 self numbers are:")
for i := 0; i < len(sv); i++ {
if !sv[i] {
count++
if count <= 50 {
fmt.Printf("%d ", i)
}
if count == 1e8 {
fmt.Println("\n\nThe 100 millionth self number is", i)
break
}
}
}
fmt.Println("Took", time.Since(st))
}
package main
import (
"fmt"
"time"
)
const MAX_COUNT = 103*1e4*1e4 + 11*9 + 1
var sv = make([]bool, MAX_COUNT+1)
var digitSum = make([]int, 1e4)
func init() {
i := 9999
var s, t int
for a := 9; a >= 0; a-- {
for b := 9; b >= 0; b-- {
s = a + b
for c := 9; c >= 0; c-- {
t = s + c
for d := 9; d >= 0; d-- {
digitSum[i] = t + d
i--
}
}
}
}
}
func sieve() {
n := 0
for a := 0; a < 103; a++ {
for b := 0; b < 1e4; b++ {
s := digitSum[a] + digitSum[b] + n
for c := 0; c < 1e4; c++ {
sv[digitSum[c]+s] = true
s++
}
n += 1e4
}
}
}
func main() {
st := time.Now()
sieve()
fmt.Println("Sieving took", time.Since(st))
count := 0
fmt.Println("\nThe first 50 self numbers are:")
for i := 0; i < len(sv); i++ {
if !sv[i] {
count++
if count <= 50 {
fmt.Printf("%d ", i)
} else {
fmt.Println("\n\n Index Self number")
break
}
}
}
count = 0
limit := 1
for i := 0; i < len(sv); i++ {
if !sv[i] {
count++
if count == limit {
fmt.Printf("%10d %11d\n", count, i)
limit *= 10
if limit == 1e10 {
break
}
}
}
}
fmt.Println("\nOverall took", time.Since(st))
}
You may also check:How to resolve the algorithm Terminal control/Display an extended character step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Entropy step by step in the APL programming language
You may also check:How to resolve the algorithm Increment a numerical string step by step in the MIPS Assembly programming language
You may also check:How to resolve the algorithm Horner's rule for polynomial evaluation step by step in the Rascal programming language
You may also check:How to resolve the algorithm Bitwise operations step by step in the Neko programming language