I got this question from a math contest on expii:
You are playing the biggest game of musical chairs ever, with 6,469,693,230 chairs. The rules are a little different: an integer D is uniformly and randomly selected from 1 to 6,469,693,230 (inclusive) and when the music starts, everyone moves D chairs to their left, then another D chairs, then another, on and on, forever. What is the expected number of unique chairs that you will sit in during this game? Note that for some values of D you will not be able to reach every chair. For example, if D=2, you can only sit in half the chairs.
I was able to get the correct answer using Mathematica to sum up: Sum[D=1,to D=6,469,693,230] {1/GCD{6,469,693,230 , D}} and I simplified a general version of the problem to (with n chairs): Sum[D=1,to D=n] {1/GCD{n , D}} but for larger values of n one needs a computer. I feel like using Mathematica is equivalent to cheating and I'm nearly certain there is a much easier way to do the problem without a computer but I wasn't able to find it. My hunch says a solution to the problem could rely on Pillai's Arithmetical Function but I'm not sure. Can someone help me? Thanks in advance!
Also Helpful: 6,469,693,230= 2*3*5*7...*23*29 Edit: Pillai's Arithmetical Function:https://en.wikipedia.org/wiki/Pillai%27s_arithmetical_function
Given $d=\gcd(N,D)$, you get $\phi(N/d)$ different values of $D$ that least to $d$.
So the above can be written as:
$$f(N)=\sum_{d\mid N} \frac{1}{d}\phi(N/d)=\frac{1}{N}\sum_{d\mid N} d\phi(d)$$
Since $\phi(n)$ is multiplicative, so is $f$, and therefore, we only need to determine the values of $f$ when $N=p^a$, for $p$ prime.
$$\begin{align}f(p^a)&=\frac{1}{p^a}\sum_{k=0}^{a} p^k\phi(p^k)\\ &=\frac{1}{p^a}\left(1 + \sum_{k=1}^a (p^{2k}-p^{2k-1})\right)\\ &=\frac{1}{p^a}\left(\sum_{j=0}^{2a} (-p)^k\right)\\ &=\frac{1}{p^a}\frac{p^{2a+1}+1}{p+1} \end{align}$$
So if you have a prime factorization of $N=p_1^{a_1}p_2^{a_2}\dots p_{m}^{a_m}$ then:
$$f(N)=\frac{1}{N} \prod_{i=1}^m \frac{p_i^{2a_i+1}+1}{p_i+1}$$
That still requires you to come up with a prime factorization of $N$.
You should get:
$$f(6,469,693,230)=\frac{1}{6,469,693,230} \frac{2^3+1}{2+1}\frac{3^3+1}{3+1}\cdots \frac{29^3+1}{29+1}$$