# UVa 10916

Jump to navigation Jump to search

## Summary

Given a year, find out what the Amtel processor word size will be in that year, and then figure out the largest ${\displaystyle N}$ for which ${\displaystyle N!}$ will fit in an unsigned integer of that word size.

## Explanation

In 1960, the word size was a measly four bits, with the word size doubling every ten years. That means that given the year Y, the number of bits can be calculated as ${\displaystyle 2^{2+\lfloor (Y-1960)/10\rfloor }}$.

The largest unsigned integer that will no longer fit in K bits is ${\displaystyle 2^{K}}$. For ${\displaystyle N!}$ to fit, then it must clearly be less than that. Now, consider ${\displaystyle \log _{2}N!=\log _{2}N+\log _{2}(N-1)+\ldots +\log _{2}1}$. If this quantity is less than ${\displaystyle \log _{2}2^{K}=K}$, then ${\displaystyle N!}$ will fit. This suggests a fairly simple algorithm: given the number of bits K, keep adding ${\displaystyle \log _{2}i}$ terms (incrementing i each time) until this number exceeds K. The largest number that still fit is the required Factstone rating.

## Notes

Strictly speaking, the running sum must actually be less than or equal to ${\displaystyle \log _{2}(2^{K}-1)}$, but the difference between that quantity and K is so miniscule that it makes no difference to solving this problem.

```1960
1981
2160
0
```

```3
8
254016
```