Converting $68^8$ microseconds to years without calculator

Question

The following problem is easy to solve with the help of a calculator. However, when doing it manually, we are faced with a very large exponentiation ($68^8$) and which, at first glance, does not seem possible to be manipulated together with the remaining data of the problem to find a simplified final result. The problem follows:

Suppose a password for a computer system must be exactly $8$ characters long, where each character in the password is either a lowercase letter, an uppercase letter, a decimal digit, or one of six special characters (*><!+=). If it takes a microsecond ($10^{-6}$ seconds) for a hacker to check if a password is correct, how many years would it take for the hacker to try every possible password?

What I've tried: Using a calculator, I first calculate the number of possible passwords, which is $68^8$. Then I multiply it by the time it takes for the hacker to test each one, so it becomes $68^8\times10^{-6}$. To convert the result into years, I first convert it into minutes by dividing by $60$, then into hours by dividing by $60$ again, then I convert it into days by dividing by $24$, and finally into years by dividing by $365$. It gives a little more than $14$ years.

I have tried to simplify the expression $$\frac{68^8}{10^6\cdot 60^2\cdot 24\cdot 365}$$ that gives the answer of the question, but even finding some common factors between numerator and denominator, this doesn't help too much, because $17$ is a prime factor of $68$, and I don't think it appears as a factor of anything in the denominator.

Also, I would like to do that in a efficient way, in a short time, without spending too much paper.

Edit.: We have noticed that a aproximated answer is the better option here. I think it is suficient to get the integer part of the aumont of years.

Answer 1

I woul do it this way:

Seconds in a hour $=60*60=36*10^2$

hours in a day $=24\approx 25$

days in a year $=365\approx36*10$

and then approximate $36*36\approx 36*3*10\approx 100*10=10^3$

so we get $36*10^2*36*10*25\approx10^3*10^3*25=2.5*10^7$ seconds in a year, i.e. $2.5*10^{13}$ microseconds in a year.

$$\frac{68^8}{2.5*10^{13}}\approx \frac{7^8*10^8}{2.5*10^{13}}=\dots$$ and since $7^2=49\approx50$ i would do $$\dots=\frac{50^4}{2.5*10^{5}}=\frac{5^4*10^4}{2.5*10^{5}}=\frac{5^4}{2.5*10}=\frac{5^3}{2.5*2}=\frac{50}{4}=12.5$$

Answer 2

Musical Logarithms

This method requires memorizing how several common musical intervals are represented in both just intonation (JI) and 12-note equal temperament (12-ET).

In both tuning systems, an octave is an exact double of frequency. The 12-ET system divides the octave logarithmically into 12 equal semitones. For convenience, let $s := \sqrt[12]{2} \approx 1.059463$ represent the frequency ratio of a semitone. By definition,

$$\log_s 2 = 12$$

A perfect fifth has a frequency ratio of $\frac{3}{2}$ in JI, and is represented by 7 semitones ($s^7 \approx 1.498307$, error of 1.955 cents) in 12-ET. IOW,

$$\log_s \frac{3}{2} \approx 7$$ $$\log_s 3 \approx \log_s{2} + 7 = 12 + 7 = 19$$

Alternatively, a perfect fourth has a frequency ratio of $\frac{4}{3}$, and is 5 semitones in 12-ET, so $\log_s \frac{4}{3} \approx 5$. This gives us the same $\log_s 3 \approx 19$ approximation as the perfect fifth.

The major third has a frequency ratio of $\frac{5}{4}$ in JI, and is represented by 4 semitones ($s^4 \approx 1.259921$, an error of 13.69 cents). IOW:

$$\log_s \frac{5}{4} \approx 4$$ $$\log_s 5 \approx 2\log_s2 + 4 = 24 + 4 =28$$

This gives us approximate logs for the primes 2, 3, and 5. The prime 7 is not always used with JI, but if we want to include it, $\log_s 7 \approx 34$. Equivalently, $\log_s \frac{7}{4} \approx 10$, approximating a minor seventh. But this has an error of 31.17 cents, so not as good.

To recap,

$$\log_s 2 = 12$$ $$\log_s 3 \approx 19$$ $$\log_s 5 \approx 28$$ $$\log_s 7 \approx 34$$

Of course, we can use the usual power and product laws to estimate the logs of composite numbers. For example,

$$\log_s 4 = 2\log_s 2 = 2\cdot12 = 24$$ $$\log_s 6 = \log_s 2 + \log_s 3 \approx 12 + 19 = 31$$ $$\log_s 8 = 3\log_s 2 = 3\cdot12 = 36$$ $$\log_s 9 = 2\log_s 3 \approx 2 \cdot 19 = 38$$ $$\log_s 10 = \log_s 2 + \log_s 5 \approx 12 + 28 = 40$$

Now, let's consider your expression

$$x := \frac{68^8}{10^6\cdot 60^2\cdot 24\cdot 365}$$

After factoring into primes, and reducing the fraction, this becomes:

$$x := \frac{2^3 \cdot 17^8}{3^3 \cdot 5^9 \cdot 73}$$

The 2's, 3's, and 5's are easy enough to deal with, but we don't know the musical logarithm of 17 or 73.

But $\log_s 17$ must be between $\log_s 16 = 4\log_s2 = 48$ and $\log_s 18 = \log_s2 + \log_s9 \approx 12 + 38 = 50$. So let's interpolate to get $\log_s 17 \approx 49$.

Similarly, $\log_s 73$ must be between $\log_s 72 = \log_s 8 + \log_s 9 \approx 36 + 38 = 74$ and $\log_s 75 = \log_s3 + 2\log_s 5 \approx 19 + 2\cdot28 = 75$. Linear interpolation between $(72, 74)$ and $(75, 75)$ gives $\log_s 73 \approx 74 + \frac{1}{3}$.

Putting all this together:

$$\log_s x = 3\log_s 2 + 8\log_s 17 - (3\log_s3 + 9\log_s5 + \log_s 73)$$ $$\approx 3(12) + 8(49) - (3(19) + 9(28) + 74.333...)$$ $$= 36 + 392 - (57 + 252 + 74.333...)$$ $$= 428 - 383.333...$$ $$= 44.666...$$

This value falls between $\log_s 12 \approx 43$ and $\log_s 15 \approx 47$. Linear interpolation between $(43, 12)$ and $(47, 15)$ gives $s^{44.666...} \approx \boxed{13.75}$.

But the actual value of $x$ (to double precision) is $\boxed{14.496551232032472}$. So our approximation has a 5.15% error. This may or may not be good enough.

Answer 3

Here's my way of approximation: Note that $68^4 = (68^2)^2$ can be calculated by pen and paper in $5$ minutes tops. We won't approximate smaller powers (if we approximate before exponentiation, the error gets too large), as one may usually be willing to spend a couple of minutes extra to get a closer answer. Now, $68^4 = 21381376$. We need $$\frac{21381376 \cdot21381376}{2^7\cdot3^3\cdot5^3\cdot73}\cdot 10^{-6}$$ Now, the most obstinate factor is undoubtedly $73$. Note that $73\cdot 3 = 219$, so we can replace one $21381376$ by $21900000$. Since we have increased $21381376$ by a number greater $500000$, we'll decrease the other $21381376$ by a number close to this so that it takes care of as many 2's, 3's and 5's as possible. One such number is $20880000$. Now, our approximation becomes $$\frac{21900000 \cdot20880000}{2^7\cdot3^3\cdot5^3\cdot73}\cdot10^{-6} = \frac{100000 \cdot2320000 }{2^7\cdot5^3}\cdot10^{-6}$$ $$= \frac{232}{2^4} = 29/2$$whcih is very close to the required answer.

[In case anyone is wondering how did I get 20880000: Subtract $500000$ from $21300000$. Now, to make it a multiple of $9$, we need an $8$ after $208$ so as to preserve maximum zeroes]

Answer 4

Another answer based on estimating logarithms.

Let $f(x \in [1, 10])$ be an approximation of $\log_{10} x$. We want $f$ to have the following properties:

• Symmetry: $\forall x \in [1, 10] : f(x) + f(\frac{10}{x}) = 1$
• Exactness at the endpoints: $f(1) = 0$ and $f(10) = 1$.
• $f(2) \approx 0.3$, and $f(5) \approx 0.7$. Because these are reasonably accurate and easy to remember.

A relatively simple function that meets all of these requirements is the Laurent polynomial:

$$f(x) = \frac{(1 - x)(x^3 - 30 x^2 - 210 x + 100)}{360 x^2}$$

which has a maximum absolute error of $0.004741$.

So, after prime-factorizing and reducing the fraction from your question:

$$x := \frac{2^3 \cdot 17^8}{3^3 \cdot 5^9 \cdot 73}$$

we can approximate (with all $f$ values rounded to 2 decimal places)

$$\log_{10} x$$ $$= 3\log_{10}2 + 8\log_{10}17 - 3\log_{10}3 - 9\log_{10}5 - \log_{10}73$$ $$\approx 3f(2) + 8(1 + f(1.7)) - 3f(3) - 9f(5) - (1 + f(7.3))$$ $$\approx 3(0.30) + 8(1.23) - 3(0.48) - 9(0.70) - 1.87$$ $$= 1.13$$

So $x \approx 10^{1.13} = 10 \times 10^{0.13}$, but how do we find the antilog of $0.13$? Well, we have:

$$\log_{10} 1.3 \approx 0.11$$ $$\log_{10} 1.4 \approx 0.14$$

So if we interpolate between those, we get $x \approx 13.67$, about 6% less than the actual value.

Answer 5

It helps if you know that there are roughly $31.5×10^6$ seconds per year, but that's easy enough to estimate. Given 52 weeks per year, we get $$\begin{array}\\ 7×52×24×60×60\\ \approx 7×100/2×100/4×3600\\ \approx 7×36/4×1/2×100^3\\ \approx 7×9/2×10^6\\ \approx 31.5×10^6\\ \end{array}$$

Note that the relative errors in $52\approx 100/2$ and $24\approx 100/4$ are equal in magnitude with opposite sign, so they cancel: $$(50+2)(25-1)=50×25-50+50-2$$

For the numerator, note that
$$68^2=(70-2)^2=4900-4×70+4=4624$$ which is just under $(4+5/8)×10^3$

Squaring again, $$\begin{array}\\ (4+5/8)^2×10^6\\ =(16+5+25/64)×10^6\\ \approx (21+3/8)×10^6\\ \end{array}$$

Squaring again gets us the estimate of $68^8$:

$$\begin{array}\\ (21+3/8)^2×10^{12}\\ \approx (441+21×3/4)×10^{12}\\ \approx 457×10^{12}\\ \end{array}$$

So the time in years is approximately $$\begin{array}\\ \frac{457×10^{12}}{31.5×10^{12}}\\ =\frac{914}{63}\\ \approx 14.5\\ \end{array}$$