Bijection of positive rational numbers with the natural numbers

941 Views Asked by At

In what position does the number $\frac{14}{15}$ appear in the bijection of the positive rational numbers with the natural numbers?

The first few terms of the bijection are:

$\frac 11$, $\frac12$, $\frac21$, $\frac13$, $\frac31$, $\frac14$, $\frac23$, $\frac32$, $\frac41$, $\frac51$, $\frac16$, $\frac25$, $\frac34$, $\frac43$, $\frac52$, $\frac61$, $\frac17$, $\frac35$,...

1

There are 1 best solutions below

2
On

Option 1

Writing them out gives:$${1, \frac{1}{2}, 2, \frac{1}{3}, 3, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, 4, \frac{1}{5}, 5, \frac{1}{6}, \frac{2}{5}, \frac{3}{4}, \frac{4}{3}, \frac{5}{2}, 6, \frac{1}{7}, \frac{3}{5}, \frac{5}{3}, 7, \frac{1}{8}, \frac{2}{7}, \frac{4}{5}, \frac{5}{4}, \frac{7}{2}, 8, \frac{1}{9}, \frac{3}{7}, \frac{7}{3}, 9, \frac{1}{10}, \frac{2}{9}, \frac{3}{8}, \frac{4}{7}, \frac{5}{6}, \frac{6}{5}, \frac{7}{4}, \frac{8}{3}, \frac{9}{2}, 10, \frac{1}{11}, \frac{5}{7}, \frac{7}{5}, 11, \frac{1}{12}, \frac{2}{11}, \frac{3}{10}, \frac{4}{9}, \frac{5}{8}, \frac{6}{7}, \frac{7}{6}, \frac{8}{5}, \frac{9}{4}, \frac{10}{3}, \frac{11}{2}, 12, \frac{1}{13}, \frac{3}{11}, \frac{5}{9}, \frac{9}{5}, \frac{11}{3}, 13, \frac{1}{14}, \frac{2}{13}, \frac{4}{11}, \frac{7}{8}, \frac{8}{7}, \frac{11}{4}, \frac{13}{2}, 14, \frac{1}{15}, \frac{3}{13}, \frac{5}{11}, \frac{7}{9}, \frac{9}{7}, \frac{11}{5}, \frac{13}{3}, 15, \frac{1}{16}, \frac{2}{15}, \frac{3}{14}, \frac{4}{13}, \frac{5}{12}, \frac{6}{11}, \frac{7}{10}, \frac{8}{9}, \frac{9}{8}, \frac{10}{7}, \frac{11}{6}, \frac{12}{5}, \frac{13}{4}, \frac{14}{3}, \frac{15}{2}, 16, \frac{1}{17}, \frac{5}{13}, \frac{7}{11}, \frac{11}{7}, \frac{13}{5}, 17, \frac{1}{18}, \frac{2}{17}, \frac{3}{16}, \frac{4}{15}, \frac{5}{14}, \frac{6}{13}, \frac{7}{12}, \frac{8}{11}, \frac{9}{10}, \frac{10}{9}, \frac{11}{8}, \frac{12}{7}, \frac{13}{6}, \frac{14}{5}, \frac{15}{4}, \frac{16}{3}, \frac{17}{2}, 18, \frac{1}{19}, \frac{3}{17}, \frac{7}{13}, \frac{9}{11}, \frac{11}{9}, \frac{13}{7}, \frac{17}{3}, 19, \frac{1}{20}, \frac{2}{19}, \frac{4}{17}, \frac{5}{16}, \frac{8}{13}, \frac{10}{11}, \frac{11}{10}, \frac{13}{8}, \frac{16}{5}, \frac{17}{4}, \frac{19}{2}, 20, \frac{1}{21}, \frac{3}{19}, \frac{5}{17}, \frac{7}{15}, \frac{9}{13}, \frac{13}{9}, \frac{15}{7}, \frac{17}{5}, \frac{19}{3}, 21, \frac{1}{22}, \frac{2}{21}, \frac{3}{20}, \frac{4}{19}, \frac{5}{18}, \frac{6}{17}, \frac{7}{16}, \frac{8}{15}, \frac{9}{14}, \frac{10}{13}, \frac{11}{12}, \frac{12}{11}, \frac{13}{10}, \frac{14}{9}, \frac{15}{8}, \frac{16}{7}, \frac{17}{6}, \frac{18}{5}, \frac{19}{4}, \frac{20}{3}, \frac{21}{2}, 22, \frac{1}{23}, \frac{5}{19}, \frac{7}{17}, \frac{11}{13}, \frac{13}{11}, \frac{17}{7}, \frac{19}{5}, 23, \frac{1}{24}, \frac{2}{23}, \frac{3}{22}, \frac{4}{21}, \frac{6}{19}, \frac{7}{18}, \frac{8}{17}, \frac{9}{16}, \frac{11}{14}, \frac{12}{13}, \frac{13}{12}, \frac{14}{11}, \frac{16}{9}, \frac{17}{8}, \frac{18}{7}, \frac{19}{6}, \frac{21}{4}, \frac{22}{3}, \frac{23}{2}, 24, \frac{1}{25}, \frac{3}{23}, \frac{5}{21}, \frac{7}{19}, \frac{9}{17}, \frac{11}{15}, \frac{15}{11}, \frac{17}{9}, \frac{19}{7}, \frac{21}{5}, \frac{23}{3}, 25, \frac{1}{26}, \frac{2}{25}, \frac{4}{23}, \frac{5}{22}, \frac{7}{20}, \frac{8}{19}, \frac{10}{17}, \frac{11}{16}, \frac{13}{14}, \frac{14}{13}, \frac{16}{11}, \frac{17}{10}, \frac{19}{8}, \frac{20}{7}, \frac{22}{5}, \frac{23}{4}, \frac{25}{2}, 26, \frac{1}{27}, \frac{3}{25}, \frac{5}{23}, \frac{9}{19}, \frac{11}{17}, \frac{13}{15}, \frac{15}{13}, \frac{17}{11}, \frac{19}{9}, \frac{23}{5}, \frac{25}{3}, 27, \frac{1}{28}, \frac{2}{27}, \frac{3}{26}, \frac{4}{25}, \frac{5}{24}, \frac{6}{23}, \frac{7}{22}, \frac{8}{21}, \frac{9}{20}, \frac{10}{19}, \frac{11}{18}, \frac{12}{17}, \frac{13}{16}, \frac{14}{15}, \frac{15}{14}, \frac{16}{13}, \frac{17}{12}, \frac{18}{11}, \frac{19}{10}, \frac{20}{9}, \frac{21}{8}, \frac{22}{7}, \frac{23}{6}, \frac{24}{5}, \frac{25}{4}, \frac{26}{3}, \frac{27}{2}, 28}$$

Counting then gives it in position 255.

Option 2

Alternatively you can add up terms in Euler Totient function until the 28th then do the case for 29 by hand. The first 28 add up to 241. The 29th term is 28 so we know that no terms with numerator plus denominator equals 29 cancel out. So adding 14 to 241 gives 255.