Count the unique fractions with only integers

Question

Count the number of unique fractions with numerators and denominators from 1 to 100, and print the counted number. Example: 2/3 = 4/6 = ...

Rules:

You must actually count in some way. Only integers are allowed, no floating point numbers or fraction types.

Integers count as fractions. So 1/1, 2/1, etc is valid.

Answer 1

J - 21 17 char

+/1=,+./~1+i.100

Explained:

• 1+i.100 - The integers from 1 to 100.
• +./~ - Table of GCDs.
• 1=, - Run into a list, and then check for equality to 1.
• +/ - Add together the results (true is 1, false is 0).

Usage:

   +/1=,+./~1+i.100
6087

21 char version that actually constructs all the pairs of numbers:

#~.,/(,%+.)&>:/~i.100

&>: increments all the integers and also sets up another golfy thing, while ~. takes all the unique entries in the list of pairs we construct, and then # gives the length of that.

Answer 2

Ruby, 57 (67 without Rational) (-3 if run in IRB)

p((a=[*1..100]).product(a).map{|x|Rational *x}.uniq.size)

Output:

6087

Can be 3 less characters if run in IRB, because you can remove the p( and ).

Uses product for the numerator and denominator getting process, and then uses Rational for converting them to fractions. If you remove the .size at the end, it prints all of the fractions instead of how many there are.

It seems like it might take a long time to run, but it's actually almost instantaneous.

Here's an example IRB session to explain how the code works a bit better:

irb(main):027:0> (a=[*1..5]).product(a)
=> [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]]
irb(main):028:0> Rational 1, 2
=> (1/2)
irb(main):029:0> Rational 2, 4
=> (1/2)

Rational *x uses the "splat" operator to call the Rational function with arguments given in the array x. This "splat" is also used in [*1..100].

Here's an alternative that doesn't use Rational, weighing in at 66 characters:

p((a=[*1..100]).product(a).map{|x,y|z=x.gcd y;[x/z,y/z]}.uniq.size)

The fraction simplification method is replaced with this:

z=x.gcd y;[x/z,y/z]

which divides the numberator and the denominator by their GCD (greatest common denominator), and then sticks them back in an array so that uniq can work.

Answer 3

Bash + GNU tools, 47

$ echo 10^9\*{1..100}/{1..100}\;|bc|sort -u|wc -l
6087
$ 

Looks like a similar method to @Doorknob's answer.

Answer 4

Mathematica - 24

This is just a sequence A018805. EulerPhi[n] is the number of coprime to n integers m that are below n (gcd n m == 1)

2 Tr@EulerPhi@Range@100 - 1

J - 15

<:+:+/5&p:i.101

Answer 5

JavaScript, 64 characters

for(n=101,o=0,c={};--n;)for(d=101;--d;)!c[n/d]&&(c[n/d]=++o);o

Put into the JS console, returns 6087.

Answer 6

Sage, 62 or 42

Runs in the interactive prompt.

c=0
R=range(1,101)
for i in R:
 for j in R:
  c+=gcd(i,j)==1
c

Short and easy to understand.

If use of Euler's totient function is allowed, here's a 42-char one-liner:

2*sum(euler_phi(n)for n in range(1,101))-1

Answer 7

CJam - 18 22

100,:):X{dXf/}%:|,
Oops, I had missed the "no floating point" requirement. Here is an integer-based solution:

100,:):X_:*f*{Xf/}%:|,

CJam is a new language I am developing, similar to GolfScript - http://sf.net/p/cjam. Here is the explanation:

100, makes an array [0 1 ... 99]
:) increments all the elements of the array
:X assigns to variable X
_ duplicates the last value (the array)
:* multiplies the array elements together, thus calculating 100!
f* multiplies each array element with 100!
{...}% performs a "map" - applies the block to each element
Xf/ divides the current number by each element in X; since the numbers were already multiplied by 100!, it is an exact division
:| performs a fold with the | (set union) operator, on the array of arrays we obtained
, counts the number of elements

Answer 8

Haskell 47

sum$filter(<2)[gcd a b|a<-[1..100],b<-[1..100]]

Run this from the interpreter.

Answer 9

Mathematica, 77

Length@Select[Range[100]~Tuples~2,#[[1]]==Numerator@Simplify[#[[1]]/#[[2]]]&]

Wow, this is the longest one here. Guess I'm not too good at thinking outside the box...

Answer 10

C++ - 64

#include<iostream>
main(){int i=0;while(++i<6087);std::cout<<i;}

It counts in some way!

Answer 11

Python, 81 characters

I guess the following solution is more math golf than code golf: it prints all the fractions as well. The algorithm might be an inspiration for code golfers, though.

def f(i,j,k,l):
    m,n = i+k,j+l
    if m > 100 or n > 100:
        return 0
    print("%d/%d" % (m,n))
    return f(i,j,m,n)+f(m,n,k,l)+1

print(f(0,1,1,0))

So after proving that this does the right thing (it would not be producing all the right fractions if it didn't, would it?), we can write this as

f=lambda i,j,k,l:i+k<101>j+l and f(i,j,i+k,j+l)+f(i+k,j+l,k,l)+1;print f(0,1,1,0)

Which is 81 characters. At the interactive prompt, you can save the six characters "print " but that seems like a bit of cheating.

It's worth noting that putting 10001 instead of 101 and adding

import sys
sys.setrecursionlimit(100000)

in front allows to calculate the number of all fractions with nominator/denominator smaller than 10000 in less than a minute. Which is impressive since every single of the 60794971 fractions is actually generated as well as counted separately. And another thing worth noting is that discounting the break-off condition, all positive fractions in shortest terms are generated by this recursion, one per call.