Counting Fractions

Problem Statement

Consider the fraction, $\dfrac n d$, where $n$ and $d$ are positive integers. If $n \lt d$ and $\operatorname{HCF}(n,d)=1$, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for $d \le 8$ in ascending order of size, we get: $$\frac 1 8, \frac 1 7, \frac 1 6, \frac 1 5, \frac 1 4, \frac 2 7, \frac 1 3, \frac 3 8, \frac 2 5, \frac 3 7, \frac 1 2, \frac 4 7, \frac 3 5, \frac 5 8, \frac 2 3, \frac 5 7, \frac 3 4, \frac 4 5, \frac 5 6, \frac 6 7, \frac 7 8$$

It can be seen that there are $21$ elements in this set.

How many elements would be contained in the set of reduced proper fractions for $d \le 2^N$?

Submit Answers

You need to submit in the format: "N:problem(N)", possibly with multiple values at once, separated by commas, with $N$ between $1$ and $100$.

Top Users

🥇 icy
59.00 (66)
🥈 shs10978
59.00 (59)
🥉 rrzmt
54.00 (54)
4 hacatu
50.00 (50)
5 disturbed_
44.00 (44)
6 pacome
35.00 (35)
7 Nondegon
31.00 (31)
8 jonnytang
21.00 (21)
9 CandynightJ
16.00 (16)
10 mmtg
15.00 (15)

Data

Stats

Your submissions will appear here

Recent Submissions

1
icy
$g(66)$, $40$ digits 4 days, 15 hours ago
2
icy
$g(64)$, $39$ digits 6 days, 4 hours ago
3
icy
$g(65)$, $39$ digits 6 days, 17 hours ago
4
icy
$g(64)$, $39$ digits 2 weeks, 2 days ago
5
shs10978
$g(50)$, $30$ digits 2 weeks, 2 days ago