9
\$\begingroup\$

Quote notation[1] is a way of expressing rational integers in a precise, finite manner, based on the concept of \$p\$-adic numbers. The notation is in the form of a string of digits (\$0123456789\$) containing exactly one "quote" (a \$\newcommand{'}[2]{#1\text{'}#2} \text{'}\:\$) and one "radix point" (a \$.\:\$). Like with standard decimal notation, if the radix point is at the right end of the string, it is omitted. Some examples of quote notation:

$$\begin{array} & \' {123} {456} & \' {123} {} & \' {} {456} \\ \' {12.3} {456} & \' {12.3} {} & \' {} {4.56} \\ \end{array}$$

Interpreting quote notation

The first thing to handle is the radix point. This point has the same function as regular decimal notation: it divides the integer form of the number by the base (\$10\$) equal to the number of places it is from the end. Therefore, we can rewrite our 3 examples with a radix point as

$$\begin{array} & \' {123} {456} \div 10^4 & \' {123} {} \div 10 & \' {} {456} \div 10^2 & \end{array}$$

Now, we can interpret the quote. The quote indicates that the digits to its left should be repeated infinitely to the left, then have the digits to the right appended to the right end. If there are no digits to the left of the quote, a zero is taken instead:

$$ \' {123} {456} = \dots 123123456 \\ \' {123} {} = \dots 123123 \\ \' {} {456} = \dots 000 456 $$

We then consider the following converging series:

$$\cdots + 10^{3k} + 10^{2k} + 10^{k} + 10^{0} = \frac 1 {1 - 10^k}$$

where \$k\$ is equal to the number of digits to the left of the quote (\$k = 1\$ from the implicit \$0\$ if there are no digits). We can then approach the infinite number in the following way:

$$\begin{align} \' {123} {456} & = \dots 123123456 \\ & = 456 + \dots 123123000 \\ & = 456 + 1000 \times \dots 123123 \\ & = 456 + 1000 \times \dots \' {123} {} \\ & = 456 + 1000 \times (\cdots 123 \times 10^9 + 123 \times 10^6 + 123 \times 10^3 + 123 \times 10^0) \\ & = 456 + 1000 \times 123 \times (\cdots + 10^9 + 10^6 + 10^3 + 10^0) \\ & = 456 + 123000 \times \left( \frac 1 {1 - 10^3} \right) \\ & = 456 - \frac {123000} {999} \\ & = \frac {110848} {333} \end{align}$$

If the original number had a radix point in (say, \$\' {12.3} {456}\$), then we just "bring back" the division we performed earlier: \$\' {12.3} {456} = \' {123} {456} \div 10^4 = \frac {110848} {333} \div 10^4 = \frac {6928} {208125}\$

With this notation, we can express any rational number in a finite string of digits with a quote and potentially a radix point.

Additionally, the 4 basic operations - addition, subtraction, multiplication and division - are fully defined for quote notated values, and produce exact values with no roundoff errors.

Rational numbers to quote notation

Unfortunately, while there is a clearly defined algorithm for mapping a quote notated value to a rational number, doing the inverse can be far more taxing. The simplest method is to combine the fact that negation and division are clearly and fully defined for quote notated values, then using these to calculate the quote notation form of a rational number.

Natural numbers are easily expressed in quote notation, as are positive finite terminating decimals. \$\' {} z\$ is the quote notation form of a natural number \$z\$, or a finite terminating decimal \$z\$. For example, \$\' {} 2 = 2\$ and \$\' {} {3.2} = 3.2\$. Negative integers and negative finite terminating decimals are also fairly trivial to derive, through negation of their positive equivalents. From these two points, we can then divide any two integers or finite terminating decimals to construct any arbitrary rational number, expressed in quote notation form.

Negating quote notated values

The easiest way to negate any quote notated value is to subtract it from \$\' 0 {}\$. This is almost exactly like digit-wise subtraction for regular decimal numbers, but rather than "borrowing" a digit from the left if the minuend digit is less than the subtrahend, we "carry" a digit. For example, to negate \$\' {429} {}\$:

$$\begin{array} \dots & 0 & 0 & 0 & 0 & 0 & 0 \\ \dots & 4_1 & 2_1 & 9_1 & 4_1 & 2_1 & 9 \\ \hline \\ \dots & 5 & 7 & 0 & 5 & 7 & 1 & = \' {057} 1 \end{array}$$

We start by subtracting the \$9\$ from \$0\$ on the right end. As \$0 < 9\$, we carry a digit along (notated by \$2_1\$ etc.) and subtract \$9\$ from \$10\$, yielding \$1\$. We then repeat this for each digit to the left, adding the carry to the subtrahend (\$10 - (2 + 1) = 7\$, carry a \$1\$ as \$0< (2+1)\$, etc.). Eventually, we'll end up with a section repeating infinitely to the left, so we can put our quote in.

Dividing quote notated values

Division can be calculated through examining the last digit of both the divisor and the dividend, and is built up from the right end of the result. This is best demonstrated with an example, \$\' {} {143} \div \' {} {333}\$:

We examine the last digit to determine what we multiply the divisor by. We then subtract this multiple from the dividend until we reach a repeated difference. In the example below, the quotes have been fully expanded, and subtraction carries have been omitted:

$$\begin{array}{rrccccccccl} & \dots & 0 & 0 & 0 & 0 & 0 & 1 & 4 & 3 & = \' {} {143} \\ - & \dots & 0 & 0 & 0 & 0 & 0 & 3 & 3 & 3 & = \' {} {333} \times 1 \\ \hline \\ & \dots & 9 & 9 & 9 & 9 & 9 & 8 & 1 & & \' {} {} \\ - & \dots & 0 & 0 & 0 & 2 & 3 & 3 & 1 & & = \' {} {333} \times 7 \\ \hline \\ & \dots & 9 & 9 & 9 & 7 & 6 & 5 & & & \\ - & \dots & 0 & 0 & 1 & 6 & 6 & 5 & & & = \' {} {333} \times 5 \\ \hline \\ & \dots & 9 & 9 & 8 & 1 & 0 & & & & \\ - & \dots & 0 & 0 & 0 & 0 & 0 & & & & = \' {} {333} \times 0 \\ \hline \\ - & \dots & 9 & 9 & 8 & 1 & & & & & \text{Repeated value} \\ \end{array}$$

Each step, we leave the last digit that was cancelled from the subtraction blank. Note that this is only the last digit, not all trailing zeros, as these can have an impact on the final result.

In this case, we have the digits of our division, we just need to know where to place the quote. We always place the quote immediately after the first occurrence of the repeated value (marked with a quote in the example above). For our example, \$\' {} {143} \div \' {} {333} = \' {057} {1}\$

However, this only works in cases where the divisor (\$\' {} {333}\$ in the example) is co-prime with \$10\$. If the denominator in the fraction \$\frac a b\$ is not co-prime with \$10\$, we need to manipulate the fraction to the form \$\frac x {10\times y}\$ where \$y\$ is co-prime to \$10\$, then extract the \$\div 10\$ to modify the position of the radix point in the result \$x \div y\$. For example, \$8 \div 15\$:

$$\begin{align} 8 \div 15 & = 16 \div 30 \\ & = 16 \div 3 \div 10 \\ 16 \div 3 & = \' 6 {72} \\ \therefore 16 \div 3 \div 10 & = \' 6 {72} \div 10 \\ & = \' 6 {7.2} \\ \therefore 8 \div 15 & = \' 6 {7.2} \end{align}$$

This way, we are fully able to divide any natural number by another, allowing us to express all positive rational numbers. Through negation, we can then express all rational numbers.

Normalisation of quote notation

As the left hand side of the quote is infinite, it is possible to "roll" it into the right hand side, to obtain an alternate form of the value. For example \$\' {057} 1 = \' {705} {71}\$ (try writing them both out if you can't see it). Therefore, it is usually possible to normalise a quote notated value by potentially rolling any leading digits from the right side of the quote into the left side.

The normalised form of quote notation is always the shortest possible representation of that number.


You are to take a rational number as input, and output the normalised quote notation form of this rational number.

You may choose to take input as either a fraction \$\frac a b\$, or as two integers \$a, b\$. If the input is negative and you take 2 integers as input, you may choose which integer has the negative sign, so long as it's consistent. In either case, the fraction will be fully simplified, and \$b\$ will never be equal to 0. If \$b\$ is equal to \$1\$, you may choose to omit it.

You may output the quote notated value in any reasonable manner. For example, outputting as a string with 2 distinct, non-digit characters representing the quote and radix point, or outputting 2 lists of digits and a power of 10 to represent the radix point.

Note that there may not be digits after the quote, and that leading zeros matter for both strings of digits, so the format you choose must be able to represent significant leading zeros, as well as distinguish between an empty output and a zero output.

This is so the shortest code in bytes wins.

Test cases

2/1    = '2
-85/7  = 571428'45
58/3   = 6'86
-11/8  = 9'8.625
32/21  = 047619'2
-85/56 = 714285'5.625
677/86 = 162790697674418604651'9.5
-332/9 = 8'52
71/51  = 1960784313725490'21
1/17   = 2941176470588235'3
-1/900 = .11'
389/198 = 35'5.5
-876/83 = 38554216867469879518072289156626506024096'28
-38/2475 = 3.5'2
-1081/2475 = 67'.24
\$\endgroup\$
6
  • \$\begingroup\$ Sandbox \$\endgroup\$ Apr 24 at 0:07
  • \$\begingroup\$ If outputting as a string, what is the proper normalized form for something like -1/900=. 1'/.11', where the number of repeating digits is less than the distance between the quote and the decimal point? \$\endgroup\$
    – att
    Apr 24 at 1:12
  • \$\begingroup\$ @att The normalised form of -1/900 is.11', as the power of 10 to divide by with .1' is too low, and "places" should only be filled with digits \$\endgroup\$ Apr 24 at 1:24
  • \$\begingroup\$ A couple of the test cases are incorrect - -11/8 should be 9'8.625, and 389/198 should be 3.5'55 \$\endgroup\$
    – att
    Apr 24 at 4:21
  • \$\begingroup\$ @att Corrected -11/8. 389/198 should be 35'5.5, and I've corrected the 3.5'2 input \$\endgroup\$ Apr 24 at 14:53
5
\$\begingroup\$

Wolfram Language (Mathematica), 142 128 125 bytes

{Clear@r;_r:=e<(e=10#2~GCD~e);e=10;l=1//.o_?r:>10o,n=l#;{}//.g_/;!r@n:>(For[j=0;r@n=l--,!e∣n,n-=#2,j++];n/=10;j<>g),r@n-l}&

Try it online!

Input [n, d]. Implements the division algorithm. Returns {r, QD, q} | r, where QD is a StringJoin of digits and r is a power of ten, representing \$\text{Q}_1\cdots\text{Q}_q\text{'D}\times\frac{1}{r}\$.


For a nicer output format, 141 138 bytes:

{Clear@r;_r:=e<(e=10#2~GCD~e);e=10;l=1//.o_?r:>10o,n=l#;TakeDrop[{}//.{g___}/;!r@n:>{For[j=0;r@n=l--,!e∣n,n-=#2,j++];n/=10;j,g},r@n-l]}&

Try it online!

Input [n, d]. Returns {r, {Q, D}}, where Q and D are lists of digits and r is a power of ten, representing \$\text{Q'D}\times\frac{1}{r}\$.


Another approach, 154 159 153 bytes

q±#|l@#-#2&@@r[FromDigits[a___~g~b_List:{9}:={q=If[#<0,b,9-b]~RotateRight~l@!a};g@@@r@#]10^l@q+#]&
{a_,b___}±{a_,c___}={b,a}±{c}
l=Length
r=RealDigits

Try it online!

Input [n/d]. Computes the quoted number from the input's (possibly repeating) decimal representation. Returns Q ± D | r, where Q and D are lists of digits and r is a nonnegative integer, representing \$\text{Q'D}\times10^{-r}\$. Normalization costs 39 bytes.

Uses \$0=b_1b_2...b_n\text'\overline{b_1b_2...b_n}\$, i.e. any infinitely repeating sequence (in both directions).

\$\endgroup\$
1
+100
\$\begingroup\$

Charcoal, 202 bytes

NθNη≔⁰ζF⟦χ⁵¦²⟧W¬﹪ηι«≦⊕ζ≧÷ιη≧×÷χιθ»¿⊖η«≔χεW﹪⊖εη≧×χε≧×÷⊖εηθ≔θδ≔¹ηW÷⁻×⊖ε﹪θηδ×εη«≧×χη≔×±δ↨E↨⊖ηε¹εθ»≔ΦI⁺ε÷⁻×⊖ε﹪θηδηκδ»«≔¹ηW÷⁺θη⊗η≧×χη≔…9‹θ⁰δ»≔ΦI⁺η﹪θηκη≦⁻L⁺δηζW⮌…∨⮌δ0±ζ«≔⁺ιηη≔…⁺ιδLδδ≔⁰ζ»⭆δ⁺….⁼κζι'⭆η⁺….⁼⁺Lδκζι

Try it online! Link is to verbose version of code. Takes numerator and denominator on separate lines. Explanation:

NθNη

Input the numerator and denominator.

≔⁰ζF⟦χ⁵¦²⟧W¬﹪ηι«≦⊕ζ≧÷ιη≧×÷χιθ»

Calculate the position of the decimal point, and adjust the fraction by the appropriate power of 10, so the denominator's GCD with 10 is now 1.

¿⊖η«

If the denominator is still greater than 1, then:

≔χεW﹪⊖εη≧×χε

Calculate the smallest string of 9s that is divisible by the denominator.

≧×÷⊖εηθ≔θδ

Calculate the numerator for that string of 9s as a denominator.

≔¹ηW÷⁻×⊖ε﹪θηδ×εη

See whether we can create quote notation for that fraction.

«≧×χη≔×±δ↨E↨⊖ηε¹εθ»

If not, add another digit after the quote and try again. Note that this involves calculating the multiplicative inverse of the denominator modulo the power of 10 given by the number of digits after the quote.

≔ΦI⁺ε÷⁻×⊖ε﹪θηδηκδ

Calculate the digits before the quote.

»«

If the denominator was 1, meaning that we had a terminating decimal, then:

≔¹ηW÷⁺θη⊗η≧×χη

Calculate the number of digits after the quote. This is particularly significant for negative numbers, but it also means that I can share the code that generates digits after the quote.

≔…9‹θ⁰δ»

Place a 9 before the quote if the value is negative.

≔ΦI⁺η﹪θηκη

Calculate the digits after the quote.

≦⁻L⁺δηζW⮌…∨⮌δ0±ζ

If there are not enough digits for the decimal point, then...

«≔⁺ιηη≔…⁺ιδLδδ≔⁰ζ»

... add digits after the quote as necessary, using digits from before the quote or 0s if there are none, rotating the digits before the quote.

⭆δ⁺….⁼κζι'⭆η⁺….⁼⁺Lδκζι

Output the digits before and after the quote, inserting the decimal point appropriately (unless it goes at the end, in which case it isn't output).

\$\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.