You are given a number D, for which 0 < D < 1,000,000

Your task : is to find the number of irreducible fractions for a fraction of the
sequence, (D-1)/D , (D-2)/D ... 1/D.

For example, let D = 12; Then listing all fraction increments of 1/D we get :
1/12 , 2/12 , 3/12 , 4/12 , 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12.

From the list of fractions above, the only fraction not reducible are: 1/12, 3/12, 5/12,
7/12, 9/12, 11/12. While the rest are reducible, for example 2/12 reduces to 1/12, and
10/12 reduces to 5/6.

Problem: Given a denominator D, for which, 0 < D < 1,000,000. Find the number
of irreducible fractions starting from the fraction 1/D to (D-1)/D, while incrementing
the series by 1/D.

2
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by firstPerson

Doesn't 3/12 reduce to 1/4 and 9/12 to 3/4.

Also 2/12 reduces to 1/6 not 1/12 (typo I think).

Doesn't 3/12 reduce to 1/4 and 9/12 to 3/4.

Also 2/12 reduces to 1/6 not 1/12 (typo I think).

Oops, your completely right. Thanks. Was thinking that, but typed something else.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.