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.

• Leaky Nun: The fact that this terminates is closely related to the possibility of expressing a decimal in continued fraction.
• Leaky Nun: Are we expected to output floats? They cause some precision issue.
• Wheat Wizard: 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
• Leaky Nun: Can we take two integers as input to represent a rational number?
• izzyg: This is equal to the final element of the simple continued fraction of the input.

Answer 1

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

• Greg Martin: What happens without Rationalize?
• Anders Kaseorg: @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}.

Answer 2

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!

• cole: Also 18, but has some floating point imprecisions because of tolerances presumably: _2{(%@-<.) ::]^:a:.
• FrownyFrog: %@|~&1^:(~:<.)^:_

Answer 3

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.

• tsh: .replace(".","") -> .replace(*"._") save 1 byte

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

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 6

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=f1ドル/(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 7

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.

• Wheat Wizard: 34 bytes? I don't know why you are using such a cumbersome IO method
• Ørjan Johansen: @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.

Answer 8

Jelly, 8 bytes

®İ$%1$©¿

Try it online!

Floating-point inaccuracies.

• Leaky Nun: Good luck doing it for 0.7
• Erik the Outgolfer: @LeakyNun That luck means either infinite loops or infinite loops...
• hyperneutrino: Use M to fix floating-point inaccuracies :P. It's Jelly but with arbitrary precision mathematics. Doesn't fix the 0.7 loop though.
• Erik the Outgolfer: @HyperNeutrino M is way outdated version of Jelly.
• caird coinheringaahing: 5 bytes

Answer 9

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 10

JavaScript ES6, 25 bytes

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

Call f(a,b) for a/b

• l4m2: If gcd(a,b)=1 can remove /b

Answer 11

Haskell, (削除) 62 (削除ここまで) 61 bytes

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

Try it online!

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

• Wheat Wizard: @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.
• H.PWiz: posted

Answer 12

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.

• Shaggy: This won't work for numbers >= 10.
• tsh: @Shaggy Is supporting numbers > 1 needed?
• Solomon Ucko: Yes, it should work for any rational number (ignoring round-off error).

Answer 13

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 

• Uriel: ⍵-⌊⍵ → 1|⍵ for one byte
• user58988: @Uriel thank you... So the bytes are as the J solution

Answer 14

Smalltalk, 33 bytes

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

Answer 15

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.