# Challenge

Origami (folding paper) is a creative form of art. As far as I know, master of Origami prefers square paper. Let's start from beginning - convert a rectangular paper to a square one.

So the paper is divided into squares. We remove the biggest square which shares one shorter edge with the current shape, step by step (see the picture below). And if the remaining part after one step is less or equal than 0.001 * (area of the original paper), the paper cannot be divided any further. It is possible that nothing remains at last.

Your task is to calculate how many squares are made during the process. The square in the last step that makes the paper unable to be divided is counted into the output.

Example (a paper of 1.350 width/height), output is 10:

# Input and Output

Input: width / height ratio for the rectangular paper, one decimal (or an integer without the dot) from 1.002 to 1.999 with a minimal step of 0.001. You may also use any other reasonable format describing the ratio. Just mention it in your answer.

Output: square count, one integer.

# Example I/O

A mapping format is used to keep the page tidy, while your code doesn't need to support a list input nor to be a mapping function.

1.002 => 251
1.003 => 223
1.004 => 189
1.005 => 161
1.006 => 140
1.007 => 124
1.008 => 111
1.009 => 100


Thanks to @LuisMendo, here is the graph of answers.

# Remarks

• This is a code-golf so shortest code wins
• Pay attention to standard loopholes
• It's your freedom to decide how to deal with input and output but they should follow standard restrictions.

By the way...

• Comment if you have anything unclear about the challenge
• Personally I would suggest your answer contains a explanation if you are using a golfing language
• Thanks to @GregMartin, read his answer for a good mathematical explanation for the challenge.

# Example Code

Here is a ungolfed version of C++ code:

#include <iostream>
#include <utility>

int f (double m)
{
double n = 1, k = 0.001;
int cnt = 0;
k *= m;                       // the target minimum size
while(m*n >= k)
{
m -= n;                   // extract a square
if(n > m)
std::swap(n, m);      // keep m > n
++ cnt;
}
return cnt;
}

int main()
{
double p;
std::cin >> p;
std::cout << f(p);
return 0;
}


All calculations related in the example code need an accuracy of 6 decimal digits, which is covered in float.

• Can two numbers forming the ratio be used as inputs? Jan 9 '17 at 15:15
• @LuisMendo yes, as your wish. Jan 9 '17 at 15:15
• Neat challenge! Jan 9 '17 at 15:36
• The list of answers produces a nice graph Jan 9 '17 at 15:46
• @KeyuGan Of course, go ahead! Let me know if you need a version with some other format Jan 9 '17 at 15:52

# Haskell, 71 70 65 63 62 61 58 56 bytes

Thanks to @xnor for a some ingenious improvements!

(n#m)e|e>n*m*1e3=0|n<m=m#n$e|d<-n-m=(d#m)e+1 n!m=n#m$n*m


Try it online!

• It think the m==n at the end can be 1>0 because it's the only possibility remaining. Or, maybe the cases could be rearranged to allow a bind here.
– xnor
Jan 9 '17 at 15:57
• Actually, is the equality case needed? If n>m is expanded to n>=m and the first check is written e>m*n*1000, that should give 1 for equality.
– xnor
Jan 9 '17 at 16:01
• @xnor Good idea, thank you! Jan 9 '17 at 16:04
• Moving around guards for 56: (n#m)e|e>n*m*1e3=0|n<m=m#n$e|d<-n-m=(d#m)e+1;n!m=n#m$n*m
– xnor
Jan 10 '17 at 7:01
• Wow, using the d<-n-m as otherwise is really neat!!! Jan 10 '17 at 11:19

## JavaScript (ES6), 59 58 bytes

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)


### Test

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

console.log(f(1.002))
console.log(f(1.003))
console.log(f(1.004))
console.log(f(1.005))
console.log(f(1.006))
console.log(f(1.007))
console.log(f(1.008))
console.log(f(1.009))

## Mathematica, 64 53 bytes

({t=1,#}//.{a_,b_}/;1000a*b>#:>Sort@{++t;a,b-a};t-1)&


An imperative (C-style) solution is exactly the same length:

(For[t=a=1;b=#,1000a*b>#,If[a>b,a-=b,b-=a];++t];t-1)&


# MATL, 19 bytes

SZ}y-htG/p1e-3>}x@


The input is an array with the two numbers defining the original ratio, such as [1, 1.009]. (It is not necessary that the numbers be sorted or that one of them be 1.)

Try it online!

### Explanation

        % Do...while loop
S      %   Sort array. Takes 1×2 array as input (implicit) the first time
Z}     %   Split array into its 2 elements: first the minimum m, then the maximum M
y      %   Duplicate m onto the top of the stack. The stack now contains m, M, m
-      %   Subtract. The stack now contains m, M-m
h      %   Concatenate into [m, M-m]. This is the remaining piece of paper
t      %   Duplicate
G/     %   Divide by input, element-wise
p      %   Product of array. Gives ratio of current piece's area to initial area
1e-3>  %   True if this ratio exceeds 1e-3. In that case the loop continues
}        % Finally (execute after last iteration, but still within the loop)
x      %   Delete last piece of paper
@      %   Push current loop counter. This is the result
% End (implicit)
% Display (implicit)


# C (GCC/Clang), 61 59 bytes

c,k;f(m,n){for(k=m*n;m*n/k;m>n?(m-=n):(n-=m))++c;return c;}


Input is two integers (width & height) without dot, such as f(1999,1000).

I hope someone could save one byte pushing C into the 58-byte club. ;)

• Suggest removing the parentheses around m-=n Jul 31 '19 at 6:41

# C, 59 bytes

s,a,n=1e3;C(m){for(a=m;m*n>a;s++)m>n?m-=n:(n-=m);return s;}


Try It online

The input is an integer which is the width / height ratio in thousandths (eg. 1002 for 1.002:1).

### Ungolfed version

int C(int m)
{
int n = 1000;
int a = m;
int s = 0;

while (m * n > a)
{
if (m > n)
m -= n;
else
n -= m;

s++;
}

return s;
}