# Count the unique fractions with only integers [closed]

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
• This question is pretty old, and as a result I don't think it meets the standards of clarity that we have established since. Particularly what it means to "count in some way" and what "only integers" mean is pretty subjective. (the former is flouted here) I think the former could be sidestepped by having the "100" input rather than hardcoded, but its a little late to make that change. Feel free to re-ask this with new clear specs (there seems to be some recent intrest), and if you are wondering how to do that the sandbox may be able to help. – Wheat Wizard Dec 14 '20 at 0:01
• @WheatWizard yeah you're completely correct. I have some very bad early questions. – qwr Dec 14 '20 at 0: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. " – user12205 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

# Haskell, 32 bytes

sum[1|1<-gcd<$>r<*>r] r=[1..100]  Try it online! Tries to follow the spirit of actually computing the result by having a "100" that can be replaced with any number. • Wow, I completely forgot I even asked this question. Well now all the answers use the hardcoded 100 so I guess there could be a better challenge with arbitrary input (if one doesn't already exist). – qwr Dec 12 '20 at 9:07 # APL (Dyalog Extended), 12 bytes ≢⍸1=∘.∨⍨⍳100  Try it online! Original: (+/1=∘,⍳∘.∨⍳)100  Explanation:  (+/1=∘, ⍳∘.∨⍳ )100 ⍝ ^~~~~~v ^~~~v ^~~~v ⍝ | | 100 x 100 ⍝ | greatest common divisor table of dimensions ⍝ flatten, count all values equal to one in  ## 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  # Haskell 47 sum$filter(<2)[gcd a b|a<-[1..100],b<-[1..100]]


Run this from the interpreter.

• Save 3 bytes with s=[1..100];sum\$filter(<2)[gcd a b|a<-s,b<-s]. – Laikoni Jun 23 '20 at 8:00

# 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? – user12205 Apr 9 '14 at 22:16
• @ace haha, not intentionally :) I used ":" followed by an operator as a shortcut for map/fold operations – aditsu quit because SE is EVIL 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

# Husk, 11 bytes

LumF/π2ḣ100


Try it online!

# Mathematica, 77

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


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.

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.

# 05AB1E, 7 bytes

Port of isaacg's Haskell answer.

тLãʒ¿}g


Try it online!

## Explanation

т         Push 100
L        Length range: [1 .. 100]
ã       All possible pairs
ʒ      Filter where:
¿         The gcd of the pairs
}        is equal to 1
g   Find the length