Practical number algorithm

Question

I am trying to write a program to find the practical numbers, from an input from \1ドル\$ to \$n\$.

Practical numbers

My code is running correctly but it is extremely slow when calculating numbers around 50 - it gets stuck at 44.

import Foundation
func getInteger() -> Int {
 var firstNum:Int = 0
 while true {
 // get value from user. Using optional input since readLine returns an optional string.
 let input = readLine()
 // ensure string is not nil
 if let unwrappedInput = input {
 if let unwrappedInt = Int(unwrappedInput) {
 firstNum = unwrappedInt
 break
 }
 else { // the input doesn't convert into an int
 print("`\(unwrappedInput)` is not an integer. Please enter an integer")
 }
 }
 else { // did not enter anything
 print("Please enter an integer")
 }
 }
 return firstNum
}
func addOne(signArray: [Int]) -> [Int] { // finds the combinations
 var signArray2 = [Int]()
 for i in 0...signArray.count-1 {
 signArray2.append (signArray[i])
 }
 for i in 0...signArray2.count-1 {
 if signArray2[i] == 1 {
 signArray2[i] = 0
 }
 else {
 signArray2[i] = 1
 break
 }
 }
 return signArray2
}
func signEval (signArray: [Int], divArray: [Int], inNum: Int) -> Bool {// changes 2nd
 var counts = 0
 for i in 0...divArray.count-1 {
 if signArray[i] == 0 {
counts = divArray[i] + counts }
 if counts == inNum {
 return true
 }
 }
 return false
}
print("Please enter a number to find the summable numbers up to that number:")
var input2 = getInteger()// if num = 1 print 1 if num = 2 print 1 and 2 else print >2 1, 2
var inNum = 0
var numHalf = 0.0
var numRound = 0.0
var numCheck = false
var numCheck2 = false
var numQuarter = 0.0
var numSixth = 0.0
var divArray:[Int] = []
var theirArray = [Int]()
var signArray = [Int]()// array of 0s and 1s
var summableArray:[Int] = [1,2] // need to check if num is bigger than 2!
for input in 1...input2 {
 numHalf = Double (input) / 2.0
 numRound = round(numHalf)
 if numRound == numHalf {
 numCheck = true }
 if input > 2 && numCheck == false { // odd numbers greater than one are not summable
 }
 else { // these are possible summable nums
 numQuarter = Double (input) / 4.0
 numRound = round(numQuarter)
 if numRound == numQuarter {
 numCheck = true
 }
 else {
 numCheck = false
 }
 numSixth = Double(input) / 6.0
 numRound = round(numSixth)
 if numRound == numSixth {
 numCheck2 = true }
 else { numCheck2 = false}
 if numCheck == true || numCheck2 == true {
 theirArray = []
 divArray = []
 signArray = []
 summableArray = []
for i in 1...input {
 theirArray.append (i)
 }
for i in 1...input { // creates an array of all the diviors of inputted number
 if input%i == 0 {
 divArray.append (i)
 }
}
 for j in 1...divArray.count {//
 signArray.append(0)
 }
for i in 1...input{
let x: Int = Int(pow(Double(2),Double(input-1)))// int 2 to the power of input -1
 var Boolcheck = false
 for q in 1...x-1 { // i to 2^n -1 (sequence to check)
 Boolcheck = (signEval(signArray: signArray, divArray: divArray, inNum: i))// checks
 signArray = addOne(signArray: signArray)// adding the ones to the array
 if Boolcheck == true {
 summableArray.append(i)// creates array of mini summable numbers
 break
 }
 }
 if summableArray.count == input {
 print ("\(input)")
 }
}
 }
}
}

Answer 1

Some points in addition to what Roland already said:

You are correct that the readLine() returns an optional and you need to ensure that it is not nil. However, nil is only returned on an end-of-file condition, which means that it makes no sense to call readLine() again. You can only terminate the program in that situation. That is a typical use-case for guard:

func readInteger() -> Int {
 while true {
 guard let line = readLine() else {
 fatalError("Unexpected end-of-file")
 }
 if let n = Int(line) {
 return n
 }
 print("Please enter an integer")
 }
}

---

Now let's have a look at

var signArray2 = [Int]()
for i in 0...signArray.count-1 {
 signArray2.append (signArray[i])
}

First, this will crash if signArray is empty. Better use a half-open range instead:

for i in 0..<signArray.count { ... }

or iterate over the indices

for i in signArray.indices {
 signArray2.append (signArray[i])
}

or just iterate over the elements:

for e in signArray {
 signArray2.append(e)
}

But actually, you are just copying the array:

var signArray2 = signArray

---

Determination of the divisors should be done in a separate function. Your code

divArray = []
for i in 1...input {
 if input % i == 0 {
 divArray.append (i)
 }
}

can be simplified to

divArray = (1...input).filter { input % 0ドル == 0 }

There are various ways to make this faster. For example the observation that with each divisor \$ i \$ of a number \$ n \,ドル \$ n/i \$ is another divisor (see for example Find all divisors of a natural number). That allows to reduce the number of loop iterations to the square-root of the given number, and could look like this:

func divisors(n: Int) -> [Int] {
 var divs = [Int]()
 for i in 1...Int(sqrt(Double(n))) {
 if n % i == 0 {
 divs.append(i)
 if n/i != i {
 divs.append(n/i)
 }
 }
 }
 return divs // or divs.sorted(), if necessary
}

---

Your code

signArray = []
for j in 1...divArray.count {//
 signArray.append(0)
}

creates an array with the same size as divArray, but filled with zeros. That can be simplified to

signArray = Array(repeating: 0, count: divArray.count)

---

There is no need to use string interpolation when printing an integer (or any single value),

 print ("\(input)")

can be simplified to

 print(input)

---

Why is your code slow?

There is a logical error in

 let x: Int = Int(pow(Double(2),Double(input-1)))// int 2 to the power of input -1

because the number of possible combinations of divisors is just \$ 2 ^ {\text{number of divisors}} \,ドル which can be computed as

 let x = 1 << divArray.count

With that change, your program computes all practical numbers up to 200 in 0.2 seconds, and up to 1,000 in 25 seconds (on a MacBook, compiled in Release mode, with optimization).

---

A faster algorithm

In order to determine if \$ n \$ is a practical number, you test all numbers \$ 1 \le i \le n \$ if they are a sum of distinct divisors of \$ n \,ドル and for each \$ i \$ that is done by building all possible sums of divisors, until \$ i \$ is found.

It is more efficient to work the other way around. From the list of divisors of \$ n \,ドル build a list of all sums of distinct divisors. This can be done iteratively: Starting with \$ 0 \,ドル the first, second, ... divisor is added to the numbers obtained previously. Then check if all numbers from \$ 1 ... n-1 \$ are in that list.

The following implementation uses a boolean array to mark all numbers which are confirmed as sums of divisors. In addition, it uses that powers of two are always practical numbers (using the method from Determining if an integer is a power of 2).

func divisors(_ n: Int) -> [Int] {
 var divs = [Int]()
 for i in 1...Int(sqrt(Double(n))) {
 if n % i == 0 {
 divs.append(i)
 if n/i != i {
 divs.append(n/i)
 }
 }
 }
 return divs.sorted()
}
func isPractical(n: Int) -> Bool {
 // 1 and 2 are practical numbers:
 if n == 1 || n == 2 {
 return true
 }
 // Every other practical number must be divisible by 4 or 6:
 if n % 4 != 0 && n % 6 != 0 {
 return false
 }
 // Every power of 2 is a practical number:
 if n & (n-1) == 0 {
 return true
 }
 var isSumOfDivisors = Array(repeating: false, count: n)
 isSumOfDivisors[0] = true
 var last = 0 // Index of last `true` element.
 // For all divisors d of n (except n):
 for d in divisors(n).dropLast() {
 // For all i which are a sum of smaller divisors (in reverse order, so that
 // we can simply update the array):
 for i in stride(from: min(last, n-1-d), through: 0, by: -1) where isSumOfDivisors[i] {
 // Mark i + d:
 isSumOfDivisors[i + d] = true
 if i + d > last {
 last = i + d
 }
 }
 }
 // n is "practical" if isSumOfDivisors[i] == true for all i = 0...n-1:
 return !isSumOfDivisors.contains(false)
}

Test code:

let startDate = Date()
let practicalNumbers = (1...10_000).filter(isPractical)
let endDate = Date()
print(endDate.timeIntervalSince(startDate))
print(practicalNumbers)

On my MacBook, this computes the practical numbers up to 1,000 in 0.003 seconds, and up to 10,000 in 0.1 seconds.

• Without Haste: That logic for summing permutations of the divisors is magic! It dropped my time to generate 1-to-1000 from 10 minutes to the under-one-second time you said. github.com/WithoutHaste/RecreationalMath/blob/master/…

Answer 2

The indentation of your code looks messy in some places. Let your IDE format the code for you. At least the counts = divArray line needs to be further to the right, and the closing brace at the end of that line needs to be on a line of its own.

The code should have a function called isPractical(x). That function should look approximately like the following, for a very naive approach, but maybe that works already.

func isPractical(num:Int) -> Bool {
 var factors = getFactors(num)
 for i in 1...num {
 if (!isSumPossible(i, factors)) {
 return false
 }
 }
 return true
}

I don't understand your variable names. Imagine you would explain this program to a human. Which words would you use to describe the purpose of each of these variables? These words are the basis for good names.

• getInteger should be called readInt
• firstNum is unnecessary, since you can just return unwrappedInt
• input should be called line
• addOne should be called nextCombination
• signArray should not have the word sign in its name, since a 0 in that array means take this number

Instead of if condition { numCheck = true } else { numCheck = false }, you can simply write numCheck = condition.

Swift has the remainder operator %, which can be used like this:

if number % 4 == 0 {
 print("Divisible by 4")
}

Instead of using pow(2, n), you can write 1 << n, which has the same result for Int, but is simpler and faster.

All the above will not help you with the time-limit-exceeded, but it will make your program readable enough so that others may want to have a look at it. So when you have fixed all the above issues, feel free to post another new question.