Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
1  
"no floating point numbers or fraction types" - does that mean, anywhere in the program? –  CompuChip Apr 10 at 7:49
    
@CompuChip Yes. Other non-number types are allowed –  qwr Apr 10 at 18:55

11 Answers 11

up vote 4 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Wow, that was fast. Are you sure "Rational" uses only integers? Nothing else is allowed –  qwr Apr 9 at 21:00
    
@qwr Rational stores the numbers as a numerator and a denominator, not as a floating point. –  Doorknob Apr 9 at 21:00
    
@qwr If you're interested, I've also added a new version that doesn't use Rational. –  Doorknob Apr 9 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.

share|improve this answer
    
Doesn't bc -l give a floating point answer? The question states that only integer types are allowed. –  user80551 Apr 10 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. –  DigitalTrauma Apr 10 at 4:10
1  
Nice, but why escape the *. –  devnull Apr 10 at 11:26
1  
@devnull: Not escaping the asterisk will cause problems if there's a file with name ./10^91/1;. –  Dennis Apr 10 at 14:06
    
@Dennis Ah! Ugly globbing. –  devnull Apr 10 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.

share|improve this answer
1  
You can save 3 with c[n/d]=c[n/d]||++o –  Peter Taylor Apr 9 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 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
share|improve this answer
    
"You must actually count in some way. " –  ace Apr 9 at 21:28
2  
@ace This is counting. I just redirect half of it to the built-in function. –  swish Apr 9 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 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
share|improve this answer

Haskell 47

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

Run this from the interpreter.

share|improve this answer

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

share|improve this answer
    
Oh wait, only integers are allowed. Oops... Disregard this! :D –  kukac67 Apr 10 at 1:23

C++ - 64

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

It counts in some way!

share|improve this answer
    
    
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 at 16:12

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

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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.