21
\$\begingroup\$

Your task is, given x, output 2*x. Easy right!? But there's a catch: x will be given as a (possibly infinite) continued fraction, and the output must be a continued fraction. The input is guaranteed to be a real algebraic number whose degree is at most 2.

Input: The continued fraction of x. This is split into 3 parts: the integer part, the prefix, and the repeating part. The integer part consists of a single integer. The prefix and repeating part are (possibly empty) arrays of positive integers which describe the prefix and repeating part of the continued fraction. For example, the input (3, [1], [2, 4]) represents the continued fraction [3; 1, 2, 4, 2, 4, ...].

If the repeating part is empty, that indicates a rational number. For example, (3, [1, 2], []) represents [3; 1, 2] = 11/3. You must accept both forms of a rational number (i.e. (3, [1, 1, 1], []), which is [3; 1, 1, 1] = 11/3 should also be valid input).

Output: Output the continued fraction of twice the input, in the same format as the input. If the output is rational, you may output either form of the continued fraction. As long as the answer is equivalent to the correct answer, it is fine; no "compression" is necessary, so the infinite part might be "unrolled" a little (e.g. [1; 4, 2, 3, 2, 3...] may be written (1, [4], [2, 3]) or (1, [4, 2, 3], [2, 3])). All answers must be exact.

Test cases: The exact form column is given for convenience.

Input               Exact Form       Output
(0, [] [])          0                (0, [] []) or (-1, [1], [])
(-5, [1, 1], [])    -4.5             (-9, [], []) or (-10, [1], [])
(3, [1, 2], [])     11/3             (7, [3], []) or (7, [2, 1], [])
(1, [], [2])        sqrt(2)          (2, [], [1, 4])
(-1, [2], [2, 1])   -1/sqrt(3)       (-2, [1, 5], [2, 6])

And finally a slightly larger test case to ensure precision: (0, [1], [6, 1, 3, 1, 42, 1, 3, 1, 6, 2]) --> (1, [], [1, 2, 1, 8, 1, 20, 1, 8, 1, 2, 1, 2]).

Shortest code wins!

Hint: You can perform arithmetic in a rather straightforward manner on continued fractions as described here. Doubling a continued fraction is just a special case of this algorithm (although the tricky part may be to find when the continued fraction repeats).

\$\endgroup\$
  • \$\begingroup\$ Would this work? tio.run/##y00syUjNTSzJTE78n2b73zk/ryQzrzQ1xa0oMbkkMz8v2kjLrSg/… \$\endgroup\$ – Pavel Jul 8 '18 at 23:47
  • \$\begingroup\$ @Pavel No, you must be able to specify the input solely based on the integer, prefix, and repeating parts rather than as Sqrt[2]. \$\endgroup\$ – soktinpk Jul 9 '18 at 0:27
  • \$\begingroup\$ Sorry, that was a mistake on my part. Here's the link with the actual continued fraction as input: tio.run/##y00syUjNTSzJTE78n2b73zk/ryQzrzQ1xa0oMbkkMz8v2kjLrSg/… \$\endgroup\$ – Pavel Jul 9 '18 at 0:56
  • 1
    \$\begingroup\$ [3; 1, 1, 1] would be (3, [1, 1, 1], []) in the input format we're using - so the question should probably mention it in that format (in the third paragraph), just to ensure clarity. \$\endgroup\$ – sundar - Reinstate Monica Jul 9 '18 at 6:26
  • 2
    \$\begingroup\$ What constraints are there on how minimised the output must be? E.g. would (-2, [1, 5, 2], [6, 2]) be acceptable output for input (-1, [2], [2, 1])? How about (-2, [1, 5, 2, 6, 2, 6], [2, 6])? \$\endgroup\$ – Peter Taylor Jul 9 '18 at 14:33
7
\$\begingroup\$

Wolfram Language (Mathematica), 44 bytes

ContinuedFraction[2FromContinuedFraction@#]&

Try it online!

Mathematica has a builtin! Yay! Mathematica's builtin is super long. Aww.

Mathematica's continued fractions look like {integer, ...prefix, {...repeating}}

-1 thanks to JungHwan Min

\$\endgroup\$
  • 4
    \$\begingroup\$ You could omit the * because Mathematica's default delimiter, if there isn't one, is Times. \$\endgroup\$ – JungHwan Min Jul 9 '18 at 5:24
  • 3
    \$\begingroup\$ When your language has builtins for everything from Scrabble scoring to Goat recognition, some of their names will have to be "super long" by necessity. :) \$\endgroup\$ – sundar - Reinstate Monica Jul 9 '18 at 6:56
  • 1
    \$\begingroup\$ @sundar No, Mathematica only has ~5000 builtins. It's possible to make each builtin 2 bytes at most (see Mthmtca) \$\endgroup\$ – user202729 Jul 9 '18 at 14:09
  • \$\begingroup\$ @user202729 But Mathematica wouldn't have been so popular if it did that :P \$\endgroup\$ – mbomb007 Jul 26 '18 at 18:33
3
\$\begingroup\$

JavaScript (ES6), 267 bytes

(n,f,r)=>eval(`f=[0,...f];e=i=[0,2,1,0];o=j=[];k=[];m={};while([a,b,c,d]=e,c|d&&o)i*m[s=i+m+(e=c*d&&(q=a/c|0)==(b/d|0)?(o.push(q),[c,d,a-c*q,b-d*q]):1/(++i,[p,...f]=f+f?f:(i=r[0],r),p)?[b,a+b*p,d,c+d*p]:[b,b,d,d])]?k+(o=k)?o=0:(m={})[s]=1:m[s]=1;[2*n+j.shift(),j,k]`)

Accepts 3 arguments (n = integer part, f = prefix, r = repeating part). Outputs the three parts in an array. Try it online!

Explanation

It's a fairly direct implementation of the algorithm for computing continued fraction arithmetic linked in the challenge here. Repeating terms are handled by storing intermediate matrices in a lookup table, waiting for a duplicate, and outputting the terms until the next appearance of that duplicate. It's inelegant and nearly doubles the bytes needed to handle continued fractions, but I could not think of a better alternative.

The leading term is computed separately to ensure that negative continued fractions retain positive values for all terms barring the first.

To prevent false positives when awaiting a repeated cycle, the lookup table stores the data as follows: <index of input repeating part><delimiter><matrix values>.

Note that the golfed version uses eval to save 1 byte.

(n, f, r) => {
    f = [0, ...f];                       // use a 0 to chop off the integer part
    e = i = [0,2,1,0];                   // e: matrix with starting values to handle doubling
                                         // 0 + 2x
                                         // ------
                                         // 1 + 0x
                                         // i: tracks index of repeating part; until the function loops through the
                                         // repeating part, i is equivalent to NaN
    o = j = [];                          // o: alias for group of terms currently being computed
                                         // j: output array of non-repeating terms
    k = [];                              // k: output array of repeating terms
    m = {};                              // lookup table
    while ([a,b,c,d] = e, c | d && o)    // destructure matrix
                                         // c | d stops loop if both a/c and b/d equal infinity
        i * m[s = i + m + (              // m also serves as the delimiter; JS will stringify it as "[object Object]"
                                         // if i equals a value that is coerced to NaN, this multiplication
                                         // will be falsy
            e = c * d && (q=a/c|0) == (b/d|0) // checks if either c or d is 0 to avoid converting an Infinity value to 0 using the bitwise or
                ? (o.push(q), [c, d, a - c*q, b - d*q]) // append the output term and compute the new matrix
                : 1/(++i, [p, ...f] = f+f ? f : (i=r[0], r), p) // 1/(... p) checks if p is a valid number
                                         // f+f is a short way to check length of f; if f is an empty
                                         // array, f+f = '' (which is falsy)
                                         // if f is empty, try to replace with r
                                         // if r is empty, the value of i will be set to undefined (e.g. NaN)
                    ? [b, a + b*p, d, c + d*p]
                    : [b,b,d,d]
            )
        ]                                // checks if matrix has been cached in lookup table
            ? k+(o=k)                    // if the repeating part of the output has a value...
                ? o=0                    // o serves as a flag to halt the loop
                : (m={})[s] = 1          // reset lookup table to only hold the first duplicate matrix
            : m[s] = 1;                  // otherwise flag a matrix as seen
    return [2*n + j.shift(), j, k]       // add the doubled integer part to the first term
}
\$\endgroup\$

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.