Skip to main content

Probability and Cumulative Dice Sums

Post a Comment

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\).

Comments

Post a Comment

Popular posts from this blog

Simplified Multinomial Kelly

Here's a simplified version for optimal Kelly bets when you have multiple outcomes (e.g. horse races). The Smoczynski & Tomkins algorithm, which is explained here (or in the original paper): https://en.wikipedia.org/wiki/Kelly_criterion#Multiple_horses Let's say there's a wager that, for every $1 you bet, will return a profit of $b if you win. Let the probability of winning be \(p\), and losing be \(q=1-p\). The original Kelly criterion says to wager only if \(b\cdot p-q > 0\) (the expected value is positive), and in this case to wager a fraction \( \frac{b\cdot p-q}{b} \) of your bankroll. But in a horse race, how do you decide which set of outcomes are favorable to bet on? It's tricky, because these wagers are mutually exclusive i.e. you can win at most one. It turns out there's a simple and intuitive method to find which bets are favorable: 1) Look at \( b\cdot p-q\) for every horse. 2) Pick any horse for which \( b\cdot p-q > 0\) and mar...
Post a Comment
Read more

Probability and Cumulative Dice Sums

Let a die be labeled with increasing positive integers \(a_1,\ldots , a_n\), and let the probability of getting \(a_i\) be \(p_i>0\). We start at 0 and roll the die, adding whatever number we get to the current total. If \({\rm Pr}(N)\) is the probability that at some point we achieve the sum \(N\), then \(\lim_{N \to \infty} {\rm Pr}(N)\) exists and equals \(1/\rm{E}(X)\) iff \((a_1, \ldots, a_n) = 1\). The direction \(\implies\) is obvious. Now, if the limit exists it must equal \(1/{\rm E}(X)\) by Chebyshev's inequality, so we only need to show that the limit exists assuming that \((a_1, \ldots, a_n) = 1\). We have the recursive relationship \[{\rm Pr}(N) = p_1 {\rm Pr}(N-a_1) + \ldots + p_n {\rm Pr}(N-a_n);\] the characteristic polynomial is therefore \[f(x) = x^{a_n} - \left(p_1 x^{(a_n-a_1)} + \ldots + p_n\right).\] This clearly has the root \(x=1\). Next note \[ f'(1) = a_n - \sum_{i=1}^{n} p_i a_n + \sum_{i=1}^{n} p_i a_i = \rm{E}(X) > 0 ,\] hence this root is als...
Post a Comment
Read more

Mixed Models in R - Bigger, Faster, Stronger

When you start doing more advanced sports analytics you'll eventually starting working with what are known as hierarchical, nested or mixed effects models . These are models that contain both fixed and random effects . There are multiple ways of defining fixed vs random random effects , but one way I find particularly useful is that random effects are being "predicted" rather than "estimated", and this in turn involves some "shrinkage" towards the mean. Here's some R code for NCAA ice hockey power rankings using a nested Poisson model (which can be found in my hockey GitHub repository ): model The fixed effects are year , field (home/away/neutral), d_div (NCAA division of the defense), o_div (NCAA division of the offense) and game_length (number of overtime periods); offense (strength of offense), defense (strength of defense) and game_id are all random effects. The reason for modeling team offenses and defenses as random vs fixed effec...
3 comments
Read more