11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The fact that this terminates is closely related to the possibility of expressing a decimal in continued fraction. \$\endgroup\$ – Leaky Nun Jul 2 '17 at 14:45
  • 4
    \$\begingroup\$ Are we expected to output floats? They cause some precision issue. \$\endgroup\$ – Leaky Nun Jul 2 '17 at 14:45
  • 7
    \$\begingroup\$ 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 \$\endgroup\$ – Sriotchilism O'Zaic Jul 2 '17 at 14:51
  • 4
    \$\begingroup\$ Can we take two integers as input to represent a rational number? \$\endgroup\$ – Leaky Nun Jul 2 '17 at 14:58
  • 1
    \$\begingroup\$ This is equal to the final element of the simple continued fraction of the input. \$\endgroup\$ – isaacg Jul 2 '17 at 16:08

15 Answers 15

5
\$\begingroup\$

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!

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

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.

\$\endgroup\$
  • \$\begingroup\$ .replace(".","") -> .replace(*"._") save 1 byte \$\endgroup\$ – tsh Jul 5 '17 at 3:27
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ What happens without Rationalize? \$\endgroup\$ – Greg Martin Jul 3 '17 at 5:08
  • 1
    \$\begingroup\$ @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}. \$\endgroup\$ – Anders Kaseorg Jul 3 '17 at 6:12
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 8 bytes

®İ$%1$©¿

Try it online!

Floating-point inaccuracies.

\$\endgroup\$
2
\$\begingroup\$

JavaScript ES6, 25 bytes

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

Call f(a,b) for a/b

\$\endgroup\$
  • \$\begingroup\$ If gcd(a,b)=1 can remove /b \$\endgroup\$ – l4m2 Jan 1 '18 at 12:58
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – Sriotchilism O'Zaic Jan 3 '18 at 0:50
  • \$\begingroup\$ posted \$\endgroup\$ – H.PWiz Jan 3 '18 at 1:00
1
\$\begingroup\$

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 
\$\endgroup\$
  • \$\begingroup\$ ⍵-⌊⍵1|⍵ for one byte \$\endgroup\$ – Uriel Jan 1 '18 at 12:17
  • \$\begingroup\$ @Uriel thank you... So the bytes are as the J solution \$\endgroup\$ – RosLuP Jan 1 '18 at 17:51
1
\$\begingroup\$

Smalltalk, 33 bytes

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

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.

\$\endgroup\$
0
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.