# Repeated reciprocal

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

• The fact that this terminates is closely related to the possibility of expressing a decimal in continued fraction. Commented Jul 2, 2017 at 14:45
• Are we expected to output floats? They cause some precision issue. Commented Jul 2, 2017 at 14:45
• Could you detail the process a little bit more? I'm unsure as to what "reciprocal of the fractional part of the number" entails, and the test cases don't help much either Commented Jul 2, 2017 at 14:51
• Can we take two integers as input to represent a rational number? Commented Jul 2, 2017 at 14:58
• This is equal to the final element of the simple continued fraction of the input. Commented Jul 2, 2017 at 16:08

# 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

• What happens without Rationalize? Commented Jul 3, 2017 at 5:08
• @GregMartin Without Rationalize, Mathematica thinks there isn’t sufficient precision to generate all terms of the continued fraction. For example, ContinuedFraction[0.1] is just {0}. Commented Jul 3, 2017 at 6:12

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

• Also 18, but has some floating point imprecisions because of tolerances presumably: _2{(%@-<.) ::]^:a:.
– cole
Commented Jan 1, 2018 at 18:09
• %@|~&1^:(~:<.)^:_ Commented Jan 1, 2018 at 19:06

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

• .replace(".","") -> .replace(*"._") save 1 byte
– tsh
Commented Jul 5, 2017 at 3:27

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

# PHP, 69 bytes

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


Try it online!

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

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.
• 34 bytes? I don't know why you are using such a cumbersome IO method Commented Jan 3, 2018 at 1:32
• @WheatWizard Hm well, I interpreted "pair" as having to be a pair rather than two distinct arguments. I suppose that's an overly Haskell-centric interpretation. Commented Jan 3, 2018 at 1:49

# Jelly, 8 bytes

®İ$%1$©¿


Try it online!

Floating-point inaccuracies.

• Good luck doing it for 0.7 Commented Jul 2, 2017 at 15:00
• @LeakyNun That luck means either infinite loops or infinite loops... Commented Jul 2, 2017 at 15:04
• Use M to fix floating-point inaccuracies :P. It's Jelly but with arbitrary precision mathematics. Doesn't fix the 0.7 loop though. Commented Jul 2, 2017 at 20:42
• @HyperNeutrino M is way outdated version of Jelly. Commented Jul 3, 2017 at 8:17
• 5 bytes Commented Jan 2, 2018 at 4:56

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

# JavaScript ES6, 25 bytes

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


Call f(a,b) for a/b

• If gcd(a,b)=1 can remove /b
– l4m2
Commented Jan 1, 2018 at 12:58

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.

• @H.PWiz Nice! I had been trying to pattern match with Data.Ratio. I've never heard of GHC.Real. Feel free to post that as your own answer. Commented Jan 3, 2018 at 0:50
• posted Commented Jan 3, 2018 at 1:00

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

• This won't work for numbers >= 10. Commented Jul 3, 2017 at 8:14
• @Shaggy Is supporting numbers > 1 needed?
– tsh
Commented Jul 5, 2017 at 3:22
• Yes, it should work for any rational number (ignoring round-off error). Commented Oct 27, 2017 at 23:47

# 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

• ⍵-⌊⍵1|⍵ for one byte Commented Jan 1, 2018 at 12:17
• @Uriel thank you... So the bytes are as the J solution
– user58988
Commented Jan 1, 2018 at 17:51

# Smalltalk, 33 bytes

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


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