9
$\begingroup$

This question did never came out in any contest.

If $\sum_{d\mid n} d!=$ 5550293832739304789551054660550388117999982337982762871343070903773209740507907044212761943998894132603029642967578724274573160149321818341878907712327954361294013178117124257080649539302762988970409903639088284496919150497945884138370985131614381553, what is the value of $n$?

No calculators allowed.

As a bonus question, is it possible to find the value of $n$ by using the fact that the last $x$ digits remain the same when we hit $(5x)!$ without using logarithim?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ how many digits long is that number? $\endgroup$ Commented Nov 1 at 16:24
  • $\begingroup$ 250 digits. But it is possible to solve by “ruling out” numbers. $\endgroup$ Commented Nov 1 at 16:43

2 Answers 2

Reset to default
12
$\begingroup$

Answer:

n = 144

Explanation:

  • The only numbers with nonzero units digit in their factorial are 1 through 4, and the digits are 1, 2, 6, 4. Since the units digit is 3, both 1 and 2 are divisors, and either both 3 and 4 are divisors, or neither is.

  • The only numbers with nonzero tens digit in their factorial are 4 through 9, and the digits are 2, 2, 2, 4, 2, 8. All of them are even, but the tens digit is 5 (odd), so both 3 and 4 must be divisors. This means 6 and 12 are also divisors. So the tens digit is 5 = 1 (from carry over) + 2 (from 4) + 2 (from 6), which seems correct but allows for the possibility that 9 and 5, 7, or 8 are also divisors. If 5 or 7, and 9, are divisors, then n is a multiple of 22325 = 180 or 22327 = 252, both of which are too large using the argument below based on the number of digits. So 5 and 7 are not divisors.

  • Let's repeat this for the hundreds digit. The sum 1! + 2! + 3! + 4! + 6! + 12! contains 353 as the last three digits. In the given number, the hundreds digit is 5, but so far we have 3. The hundreds digit of the factorial is nonzero only for 5 through 14. Of these, 5, 7, 10, and 14 can't be divisors, and 6 and 12 are already taken care of, so let us focus on 8, 9, 11, 13. Their hundreds digits are 3, 8, 8, 8. But if 11 or 13 is a divisor, then n would be too large, so the only way to get the extra 2 in the hundreds digit is if 8 and 9 are the divisors (3+8 gives 1, but there's additional 1 carried over from 8 and 9's contribution to the tens digit). It follows that the number is divisible by 2332 = 72.

  • The number of digits of the sum is dominated by n! itself. And the number of digits in n! is between n log(n/3) and n log(n). Let's try n = 72. We have log(72) < 2, which means n log(n) < 144, so this doesn't work. What about n = 144? We have 1 < log(48) and log(144) < 3, and so the number of digits is between 144 and 432. This is the right ball park, so n = 144.

Update: Before someone points out in the comments...

  • You can rule out higher multiples of 72 as follows. Using the naive bound 1 < log(72), we only get that 216! has at least 216 digits. However, we know that √10 < 4, so 1.5 < log(40) < log(72), and so n log(n/3) > 324, so 216! has at least 324 digits.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ This shows that there is only one possible n, but does not prove that that n actually produces the large number given. $\endgroup$ Commented Nov 2 at 23:30
  • 7
    $\begingroup$ @fljx. I think it’s standard to assume that such an n exists in the first place for this kind of questions. So showing uniqueness is sufficient. $\endgroup$ Commented Nov 2 at 23:40
  • $\begingroup$ @fljx ... especially given the context of "no calculators allowed". $\endgroup$ Commented Nov 3 at 19:41
3
$\begingroup$

With no logarithms

After Pranay's terminal-digit arguments, we can get the answer without any use of logarithms.

Following the method of Pranay, we find that d has to be a multiple of 72.

Now comes the fun part, where we count digits without using logarithms.

The porridge is too cold

Suppose d=72. This has 12 divisors so the sum is less than 12×72!. But all whole numbers less than 32 multiplied by their successor are less than 1000 (31×32=992), so 72! is less 1 followed by 3×(72-32/2)=168 zeroes and thus the upper bound on the sum cannot fill 250 digits.

The porridge is too hot

Now try d=216. The 23 factors from 10 to 32 each contribute at least one power of 10. The pair of factors 33 and 34 now contribute more than a factor of 1000 (33×34=11×102=1122), and the same is true of 33 succeeding odd-even pairs up to 99×100. That's at least 102 powers of 10. The 116 factors from 101 to 216 each contribute at least two more individually, for a total of 232. So we end with 216! having at least 23+102+232=357 powers of 10 beneath it, too many for a 250-digit number. Note that 144!, with only 44 factors over 100, would have been to small to produce this contradiction.

The porridge is just right

So we conclude:

d is a multiple of 72, but must be greater than 72 and less than 216. Therefore d=144 is the sole survivor.

Improve this answer
$\endgroup$
1
  • $\begingroup$ To be fair, I didn’t actually compute any logarithm, but +1 $\endgroup$ Commented Nov 3 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.