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\$ – Wheat Wizard 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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\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.
| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Jelly, 8 bytes

®İ$%1$©¿

Try it online!

Floating-point inaccuracies.

| improve this answer | |
\$\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

| improve this answer | |
\$\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.

| improve this answer | |
\$\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\$ – Wheat Wizard 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 
| improve this answer | |
\$\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\$ – user58988 Jan 1 '18 at 17:51
1
\$\begingroup\$

Smalltalk, 33 bytes

[(y:=x\\1)>0]whileTrue:[x:=1/y].x
| improve this answer | |
\$\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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\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.