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

-
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