That's all I'm given?

Computer Science Level 4

Let $S(n)$ denote the sum of digits in decimal representation of $n$ . Find the smallest positive integer value of $n$ such that $S(n!)$ does not divide $n!$ .

Adapted from another forum.

The answer is 432.

4 solutions

Bill Bell
Jun 30, 2015

Computing factorial is expensive. Therefore, better to compute it as you go.

Brock Brown
Jun 28, 2015

Python 3.3:

from math import factorial
def s(n):
    return sum((int(digit) for digit in str(n)))
n = 1
while factorial(n) % s(factorial(n)) == 0:
    n += 1
print("Answer:", n)

Daniel Liu
Jun 28, 2015

I used BigInteger in Java. Outputs $432$ . Terminates in around 130 ms.

import java.math.BigInteger;

public class Brilliant {
    public static void main(String[] args){
        int counter = 1;
        while(true){
            BigInteger factorial = new BigInteger("1");
            for(int i = 1; i <= counter; i++){
                BigInteger prod = new BigInteger(Integer.toString(i));
                factorial = factorial.multiply(prod);
            }
            if(!factorial.mod(digSum(factorial)).equals(BigInteger.ZERO)){
                System.out.println(counter);
                System.exit(0);
            }
            counter++;
        }
    }
    public static BigInteger digSum(BigInteger x){
        String str = x.toString();
        BigInteger sum = BigInteger.ZERO;
        for(int i = 0; i < str.length(); i++){
            BigInteger character = new BigInteger(Character.toString(str.charAt(i)));
            sum = sum.add(character);
        }
        return sum;
    }
}

@Pi Han Goh I'm really surprised that the smallest value is as large as $432$ . Wow.

Daniel Liu - 5 years, 11 months ago

Yeah I know! Shocking right? And I initially thought that no such value exist.

Relevant .

Pi Han Goh - 5 years, 11 months ago

Arulx Z
Jul 1, 2015

I basically did the same thing as Brock Brown -

from math import factorial
num = 1
while factorial(num) % sum(int(x) for x in str(factorial(num))) == 0:
    num += 1
print num

Moderator note:

Good, standard solution.

@Calvin Lin , I have a suggestion regarding the rating method of programming questions. Most time I see that many purely computational problems get rated high and so the points system is a bit flawed. Is there any way to avoid this?

Arulx Z - 5 years, 11 months ago

That's all I'm given?

Adapted from another forum.

The answer is 432.

4 solutions

Moderator note:

0 pending reports