# Count the unique fractions with only integers

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.

• "no floating point numbers or fraction types" - does that mean, anywhere in the program? – CompuChip Apr 10 '14 at 7:49
• @CompuChip Yes. Other non-number types are allowed – qwr Apr 10 '14 at 18:55
• How on earth is this question voted negative? I like it. I just added a +1, bringing it back up to 0 from –1. – Todd Lehman Apr 15 '15 at 18:06

# 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.

# 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.

• Wow, that was fast. Are you sure "Rational" uses only integers? Nothing else is allowed – qwr Apr 9 '14 at 21:00
• @qwr Rational stores the numbers as a numerator and a denominator, not as a floating point. – Doorknob Apr 9 '14 at 21:00
• @qwr If you're interested, I've also added a new version that doesn't use Rational. – Doorknob Apr 9 '14 at 21:04

# 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.

• Doesn't bc -l give a floating point answer? The question states that only integer types are allowed. – user80551 Apr 10 '14 at 3:18
• @user80551 Yes, you're right, I missed that in the question. I've edited to use bc with no -l, and just premultiply everything so we still get the correct uniqueness. Adds 3 chars. – Digital Trauma Apr 10 '14 at 4:10
• Nice, but why escape the *. – devnull Apr 10 '14 at 11:26
• @devnull: Not escaping the asterisk will cause problems if there's a file with name ./10^91/1;. – Dennis Apr 10 '14 at 14:06
• @Dennis Ah! Ugly globbing. – devnull Apr 10 '14 at 14:08

# 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.

• You can save 3 with c[n/d]=c[n/d]||++o – Peter Taylor Apr 9 '14 at 23:12
• Also, if you change c to an array and assign it to o ([] casts to 0 with ++ operator) you can save 4 more bytes: (57 byte solution) for(n=101,o=c=[];--n;)for(d=101;--d;)c[n/d]=c[n/d]||++o;o – nderscore Apr 10 '14 at 4:44

## 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

• "You must actually count in some way. " – ace_HongKongIndependence Apr 9 '14 at 21:28
• @ace This is counting. I just redirect half of it to the built-in function. – swish Apr 9 '14 at 21:31
• @RossMillikan That's why we double it, so it will count both 3/2 and 2/3, 3/1 and 1/3. – swish Apr 9 '14 at 22:54

## 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


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


Run this from the interpreter.

# 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

• Hm... Is this some sort of emoticon language? – ace_HongKongIndependence Apr 9 '14 at 22:16
• @ace haha, not intentionally :) I used ":" followed by an operator as a shortcut for map/fold operations – aditsu Apr 9 '14 at 22:18
• It totally should be an emoticon based language. I'd goof around with it a little. – Kyle Kanos Apr 10 '14 at 2:44

# 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...

• Oh wait, only integers are allowed. Oops... Disregard this! :D – kukac67 Apr 10 '14 at 1:23

# C++ - 64

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


It counts in some way!

• meta.codegolf.stackexchange.com/a/1063/17249 – durron597 Apr 10 '14 at 13:55
• Quote from that link: "[if] the question doesn't require input and so a solution which just prints the answer would seem to meet the spec". – CompuChip Apr 10 '14 at 16:12

# 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.

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.