# How find a closed form for the numbers which are relatively prime to $10$,

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.

• $\displaystyle\prod_kp_k^{a_k}$, with $p_k\not\in\{2,5\}$. – 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.

• Hello,How can find this Nice form?especially this $\dfrac{1379}{9999}$? – china math Jan 10 '15 at 17:17
• @chinamath: I know that $\frac1{9999}=0.000100010001...$, and 0.137913791379... is just a multiple of that. – 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$$