Interesting Question

Let $a_n$ be the positive integers (in order) which are relatively prime to $10$.

Find a closed form for $a_n$.

I know $$a_{1}=1,a_{2}=3,a_{3}=7,a_{4}=9,a_{5}=11,a_{6}=13,a_{7}=17,a_{8}=19,a_{9}=21,\cdots$$

It is said the $$a_{n}=2\left\lfloor \dfrac{5}{3}\left(n-1-\left\lfloor\dfrac{n-1}{4}\right\rfloor\right)\right\rfloor-2\left\lfloor\dfrac{1}{2}\left(n-1-4\left\lfloor\dfrac{n-1}{4}\right\rfloor\right)\right\rfloor+1$$ But I can't find this proof.

Question 2:

Let $a_n$ be the positive integers relatively prime to $m$. Find a closed form for $a_{n}$.

Is this problem a research problem? I think it should be since this is in the OEIS, and although Euler's totient function is similar, these sequences are different.

  • $\begingroup$ $\displaystyle\prod_kp_k^{a_k}$, with $p_k\not\in\{2,5\}$. $\endgroup$ – Lucian Jan 10 '15 at 17:36

That solution to question 1 looks quite complex. One could also just say $$ a_n = 2n + 2\left\lfloor\frac{n+1}4\right\rfloor - 1 $$ which uses that the first differences 2,4,2,2,2,4,2,2,2,4,2,2,2,4,... have a particularly simple structure in this case.

As a more immediately generalizable solution one could say $$ a_n = 10\left\lfloor \frac {n-1}4 \right\rfloor + \left\lfloor 10^n \frac{1379}{9999} \right\rfloor \bmod 10 $$ since $\frac{1379}{9999}=0.137913791379...$. This same principle can be used to construct closed formulas for any other integer sequence whose first differences repeat.

  • $\begingroup$ Hello,How can find this Nice form?especially this $\dfrac{1379}{9999}$? $\endgroup$ – china math Jan 10 '15 at 17:17
  • $\begingroup$ @chinamath: I know that $\frac1{9999}=0.000100010001...$, and 0.137913791379... is just a multiple of that. $\endgroup$ – Henning Makholm Jan 10 '15 at 18:00

Looking at Henning's "generalizable solution", we can definitely make this into a general solution:

To generate $a_n$ relatively prime to $m$,

$$a_n = m \left\lfloor \frac{n-1}{\phi(m)} \right\rfloor +\left\lfloor m^n \frac{k}{m^{\phi(m)}-1} \right\rfloor \text{ mod } m$$

where ${\phi(m)}$ is Euler's totient and $k$ is formed from the totatives $\{t_i\}$ of $m$ as follows: $$k=\sum_1^{\phi(m)}m^{\phi(m)-i}t_i$$

(the totatives being those numbers that Euler's totient counts, those less than $m$ relatively prime to $m$)

For example, for $m=18$:

  • $\phi(m)=6$
  • $t_i = \{1,5,7,11,13,17\}$
  • $k = 2459087$ $$a_n = 18 \left\lfloor \frac{n-1}{6} \right\rfloor +\left\lfloor 18^n \frac{2459087}{34012223} \right\rfloor \text{ mod } 18$$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.