### Highest Powers of 3 and $$\left(1+\sqrt{2}\right)^n$$

Let $$\left(1+\sqrt{2}\right)^{2012}=a+b\sqrt{2}$$, where $$a$$ and $$b$$ are integers. What is the greatest common divisor of $$b$$ and $$81$$?
Source: 2011-2012 SDML High School 2a, problem 15.

Let $$(1+\sqrt{2})^n = a_n + b_n \sqrt{2}$$. I've thought about this some more, and there's a nice way to describe the highest power of $$3$$ that divides $$b_n$$. This is probably outside of the scope of the intended solution, however.

First note that $$(1-\sqrt{2})^n = a_n - b_n \sqrt{2}$$, and so from $$(1+\sqrt{2})(1-\sqrt{2})=-1$$ we get $$(1+\sqrt{2})^n (1-\sqrt{2})^n = {(-1)}^n$$. This gives ${a_n}^2 - 2 {b_n}^2 = {(-1)}^n.$ Now define the highest power of a prime $$p$$ that divides $$n$$ to be $$\operatorname{\nu}_p(n)$$.
From cubing and using the above result it's straightforward to prove that if $$\operatorname{\nu}_3(b_n) = k > 0$$ then $$\operatorname{\nu}_3(b_{3n}) = k+1$$.
Note $$(1+\sqrt{2})^4 = 17 + 12\sqrt{2} \equiv -1+3\sqrt{2} \pmod{3^2}$$. Cubing and using the first formula as before, we can in fact show that $(1+\sqrt{2})^{4\cdot 3^n} \equiv -1 + 3^{n+1}\sqrt{2} \pmod{3^{n+2}},$ and squaring we also have $(1+\sqrt{2})^{8\cdot 3^n} \equiv 1 + 3^{n+1}\sqrt{2} \pmod{3^{n+2}}.$ Now assume $$\operatorname{\nu}_3(b_m) = k, \operatorname{\nu}_3(b_n) = l$$ and $$k\neq l$$. From the top formula if $$3 | b_i$$ then $$3 \not{|} a_i$$, and it follows that $\operatorname{\nu}_3(b_{m+n}) = \min(k,l).$Putting this all together, write $$n = 4\cdot m +k$$, where $$0\leq k <4$$. If $$k\neq 0$$, then $$\operatorname{\nu}_3(b_{n}) = 0$$. If $$k=0$$, let the base-3 expansion of $$m$$ be $$a_i \cdot 3^i + \ldots + a_0$$. Then $\operatorname{\nu}_3(b_{n}) = \min_{a_j \neq 0} j+1 .$
For $$n=2012$$, we have $$2012 = 4\cdot 503 = 4\cdot(2\cdot 3^5 + 3^2 + 2\cdot 3 + 2)$$ and so $$\operatorname{\nu}_3(b_{2012})=1$$. We don't actually need to compute the entire base-3 expansion for 503, of course; we only need to observe that it's not divisible by 3.

For $$n=2016$$, we have $$2016 = 4\cdot 504 = 4\cdot(2\cdot 3^5 + 2\cdot 3^2)$$ and so $$\operatorname{\nu}_3(b_{2016})=3$$.

### A Bayes' Solution to Monty Hall

For any problem involving conditional probabilities one of your greatest allies is Bayes' Theorem. Bayes' Theorem says that for two events A and B, the probability of A given B is related to the probability of B given A in a specific way.

Standard notation:

probability of A given B is written $$\Pr(A \mid B)$$
probability of B is written $$\Pr(B)$$

Bayes' Theorem:

Using the notation above, Bayes' Theorem can be written: $\Pr(A \mid B) = \frac{\Pr(B \mid A)\times \Pr(A)}{\Pr(B)}$Let's apply Bayes' Theorem to the Monty Hall problem. If you recall, we're told that behind three doors there are two goats and one car, all randomly placed. We initially choose a door, and then Monty, who knows what's behind the doors, always shows us a goat behind one of the remaining doors. He can always do this as there are two goats; if we chose the car initially, Monty picks one of the two doors with a goat behind it at random.

Assume we pick Door 1 and then Monty sho…

### Notes on Setting up a Titan V under Ubuntu 17.04

I recently purchased a Titan V GPU to use for machine and deep learning, and in the process of installing the latest Nvidia driver's hosed my Ubuntu 16.04 install. I was overdue for a fresh install of Linux, anyway, so I decided to upgrade some of my drives at the same time. Here are some of my notes for the process I went through to get the Titan V working perfectly with TensorFlow 1.5 under Ubuntu 17.04.

Old install:
Ubuntu 16.04
EVGA GeForce GTX Titan SuperClocked 6GB
2TB Seagate NAS HDD

New install:
Ubuntu 17.04
Titan V 12GB
/ partition on a 250GB Samsung 840 Pro SSD (had an extra around)
/home partition on a new 1TB Crucial MX500 SSD
New WD Blue 4TB HDD