Repeated reciprocal

Question

What you need to do is create a function/program that takes a decimal as input, and outputs the result of repeatedly taking the reciprocal of the fractional part of the number, until the number becomes an integer.

More specifically, the process is as follows:

1. Let x be the input

2. If x is an integer, output it.

3. Otherwise: \$x \leftarrow \frac{1}{\mathrm{frac}(x)}\$. Go back to 2.

\$\mathrm{frac}(x)\$ is the fractional component of \$x\$, and equals \$x - \left\lfloor x \right\rfloor\$. \$\left\lfloor x \right\rfloor\$ is the floor of x, which is the greatest integer less than \$x\$.

Test cases:

0 = 0
0.1 = 1/10 -> 10
0.2 = 1/5 -> 5
0.3 = 3/10 -> 10/3 -> 1/3 -> 3
0.4 = 2/5 -> 5/2 -> 1/2 -> 2
0.5 = 1/2 -> 2
0.6 = 3/5 -> 5/3 -> 2/3 -> 3/2 -> 1/2 -> 2
0.7 = 7/10 -> 10/7 -> 3/7 -> 7/3 -> 1/3 -> 3
0.8 = 4/5 -> 5/4 -> 1/4 -> 4
0.9 = 9/10 -> 10/9 -> 1/9 -> 9
1 = 1
3.14 = 157/50 -> 7/50 -> 50/7 -> 1/7 -> 7
6.28 = 157/25 -> 7/25 -> 25/7 -> 4/7 -> 7/4 -> 3/4 -> 4/3 -> 1/3 -> 3

Summary for 0 to 1 at increments of 0.1: 0, 10, 5, 3, 2, 2, 2, 3, 4, 9, 1

This is code-golf, so fewest bytes wins.

Clarifications:

• "Bonus points" for no round-off error
• Should work for any non-negative rational number (ignoring round-off error)
• You can, but don't have to output the steps taken
• You can take input as a decimal, fraction, or pair of numbers, which can be in a string.

Sorry for all the issues, this is my first question on this website.

Answer 1

J, 18 bytes

%@(-<.)^:(~:<.)^:_

In J, the idiom u ^: v ^:_ means "Keep applying the verb u while condition v returns true.

In our case, the ending condition is defined by the hook ~:<., which means "the floor of the number <. is not equal ~: to the number itself" -- so we'll stop when the main verb u returns an int.

u in this case is another hook -<. -- the number minus its floor -- whose return value is fed into @ the reciprocal verb %.

Try it online!

Answer 2

Python 3, 101 bytes

lambda s:g(int(s.replace(".","")),10**s[::-1].index("."))
g=lambda a,b:a and(b%a and g(b%a,a)or b//a)

Try it online!

Format: the string must contain a decimal point.

Answer 3

Mathematica, 36 bytes

Last@*ContinuedFraction@*Rationalize

Demo

In[1]:= f = Last@*ContinuedFraction@*Rationalize

Out[1]= Last @* ContinuedFraction @* Rationalize

In[2]:= f[0]

Out[2]= 0

In[3]:= f[0.1]

Out[3]= 10

In[4]:= f[0.2]

Out[4]= 5

In[5]:= f[0.3]

Out[5]= 3

In[6]:= f[0.4]

Out[6]= 2

In[7]:= f[0.5]

Out[7]= 2

In[8]:= f[0.6]

Out[8]= 2

In[9]:= f[0.7]

Out[9]= 3

In[10]:= f[0.8]

Out[10]= 4

In[11]:= f[0.9]

Out[11]= 9

In[12]:= f[1]

Out[12]= 1

Answer 4

Perl 6, 42 bytes

{($_,{1/($_-.floor)}...*.nude[1]==1)[*-1]}

Try it online!

The nude method returns the numerator and denominator of a rational number as a two-element list. It's shorter to get the denominator this way than to call the denominator method directly.

Answer 5

Haskell, 47 bytes

This beats Wheat Wizard's answer because GHC.Real allows us to pattern match on rationals using :%, aswell as having a shorter name

import GHC.Real
f(x:%1)=x
f x=f$1/(x-floor x%1)

Try it online!

f takes a Rational number as input, although ghc allows them to be written in a decimal format, within a certain precision.

Answer 6

Haskell, 40 34 bytes

Edit:

• -6 bytes: @WheatWizard pointed out the fraction can probably be given as two separate arguments.

(Couldn't resist posting this after seeing Haskell answers with verbose imports – now I see some other language answers are also essentially using this method.)

! takes two integer arguments (numerator and denominator of the fraction; they don't need to be in smallest terms but the denominator must be positive) and returns an integer. Call as 314!100.

n!d|m<-mod n d,m>0=d!m|0<1=div n d

Try it online!

• Ignoring type mismatch, the fractional part of n/d (assuming d positive) is mod n d/d, so unless mod n d==0, ! recurses with a representation of d/mod n d.

Answer 7

Python 3 + sympy, 67 bytes

from sympy import*
k=Rational(input())
while k%1:k=1/(k%1)
print(k)

Try it online!

Sympy is a symbolic mathematics package for Python. Because it is symbolic and not binary, there are no floating point inaccuracies.

Answer 8

PHP, 69 bytes

for(;round(1e9*$a=&$argn)/1e9!=$o=round($a);)$a=1/($a-($a^0));echo$o;

Try it online!

PHP, 146 bytes

for($f=.1;(0^$a=$argn*$f*=10)!=$a;);for(;1<$f;)($x=($m=max($a,$f))%$n=min($a,$f))?[$f=$n,$a=$x]:$f=!!$a=$m/$n;echo($o=max($a,$f))>1?$o:min($a,$f);

Try it online!

Answer 9

Jelly, 8 bytes

®İ$%1$©¿

Try it online!

Floating-point inaccuracies.

Answer 10

JavaScript ES6, 25 bytes

f=(a,b)=>a%b?f(b,a%b):a/b

Call f(a,b) for a/b

Answer 11

Haskell, 62 61 bytes

import Data.Ratio
f x|denominator x==1=x|u<-x-floor x%1=f$1/u

Try it online!

Uses Haskell's Data.Ratio library for arbitrary precision rationals. If only the builtin names were not so long.

Answer 12

APL (Dyalog Classic), 18 bytes

{1e¯9>t←1|⍵:⍵⋄∇÷t}

Try it online!

APL NARS, 18 chars

-1 byte thanks to Uriel test

f←{1e¯9>t←1|⍵:⍵⋄∇÷t}
v←0 .1 .2 .3 .4 .5 .6 .7 .8 .9 1 3.14
⎕←v,¨f¨v
  0 0  0.1 10  0.2 5  0.3 3  0.4 2  0.5 2  0.6 2  0.7 3  0.8 4  0.9 9  1 1  3.14 7 

Answer 13

Smalltalk, 33 bytes

[(y:=x\\1)>0]whileTrue:[x:=1/y].x

Answer 14

Stax, 8 bytes

ç▄é⌠á◙àù

Run and debug it

"Bonus points" for no precision errors. No floating point arithmetic used. This (finally) makes use of stax's built-in rational type.

Answer 15

JavaScript, 70 bytes

x=>(y=(x+'').slice(2),p=(a,b)=>b?a%b?p(b,a%b):a/b:0,p(10**y.length,y))

If we can change input type to a string, then it may save 5 bytes.