12
\$\begingroup\$

According to Wikipedia, a strongly Darboux function is

one for which the image of every (non-empty) open interval is the whole real line

In other words, a function \$f\$ is strongly Darboux if given 3 arbitrary real numbers \$a\$, \$b\$, and \$y\$, it is always possible to find an \$x\$ between (distinct) \$a\$ and \$b\$ such that \$f(x) = y\$.

For the purposes of this challenge, we will consider strongly Darboux functions over the rationals instead.

Your challenge is to write a program or function that:

  • gives a rational number as output for every rational number input,
  • always gives the same output for a given input, and
  • has the strongly Darboux property.

Input and output may be either of the following:

  • an arbitrary-precision number type, if your language has one (or has a library for one, e.g. GMP).
  • a string representation of the number, which you may assume will always contain a decimal point and at least one digit on either side. It may be in any base \$b \geq 2\$, but input and output must be in the same base. You may use any set of characters for the digits and decimal point (but again, they must be consistent between input and output).

The input will always have a terminating base \$b\$ expansion. As for the output, which may have a theoretically non-terminating base \$b\$ expansion depending on your choice of function, you may choose any of the following:

  • output digits forever.
  • take an additional integer as input and output at least that many digits.
  • output at least as many digits as are in the input (which may contain trailing zeroes).

Note that by the nature of this challenge, the convention that numbers may be assumed to be representable by standard number types does not apply, except for the second input described in option 2 above.

To avoid loopholes with functions that are only defined on non-terminating rationals, your submission must be able to produce output arbitrarily close to a desired value in practice. Formally, given rational numbers \$a\$, \$b\$, \$y\$, and \$\varepsilon\$, there must be a rational number \$x\$ that terminates in your chosen base such that \$a<x<b\$ and \$|f(x)-y|<\varepsilon\$.


To give you some ideas, here is a description of the Conway base 13 function:

  • Convert \$x\$ to base 13 and remove the decimal point.
  • If the result is of the form \$[x]A[y]C[z]_{13}\$, where \$[y]\$ and \$[z]\$ consist of only digits from 0 to 9, then \$f(x) = [y].[z]\$.
  • If the result is of the form \$[x]B[y]C[z]_{13}\$, where \$[y]\$ and \$[z]\$ consist of only digits from 0 to 9, then \$f(x) = -[y].[z]\$.
  • Otherwise, \$f(x) = 0\$.

This function is strongly Darboux. Say, for example, that we want to find some \$x\$ between \$123.456_{13}\$ and \$123.457_{13}\$ such that \$f(x) = 7.89\$. The base-13 value \$123.456A7C89_{13}\$ would satisfy this requirement.

Your submission may be an implementation of this function, although I suspect that there are other strongly Darboux functions that are a lot shorter to implement. :)

\$\endgroup\$
  • \$\begingroup\$ Are the numbers assumed to have a terminating base \$b\$ expansion? \$\endgroup\$ – Nitrodon Jun 27 at 20:31
  • \$\begingroup\$ math.stackexchange link and also the original question it's a dupe of for some examples \$\endgroup\$ – Giuseppe Jun 27 at 20:32
  • \$\begingroup\$ If we implement the Conway base 13 algorithm, we could take input in base 13 but would then have to output in base 13 also. Since the output of the function is usually in decimal, we will end up with a recurring tridecimal number. How should this be output? Do we output the first \$x\$ digits, where \$x\$ is specified in the question (not yet though)? Or do we need to indicate that it’s recurring? \$\endgroup\$ – Nick Kennedy Jun 27 at 20:34
  • \$\begingroup\$ @NickKennedy Thanks, I overlooked that - I've edited the question to clarify. \$\endgroup\$ – Doorknob Jun 27 at 20:41
  • 1
    \$\begingroup\$ Hmm, I'm quite sure I can define a strongly Darboux function that is constant or the identity on all terminating inputs... \$\endgroup\$ – Christian Sievers Jun 29 at 10:48
4
\$\begingroup\$

Retina 0.8.2, 43 50 bytes

^.*\.(..)*1(.)((..)+)1.((..)*)$
$2$*-$3.$5
0(.)
$1

Try it online! I/O is as a binary string. Encode a binary number y close to another binary number a as follows:

  1. If a does not contain a ., suffix one.
  2. If a contains an odd number of digits after the ., suffix a 0.
  3. If y is negative then suffix 11 otherwise suffix 10.
  4. For each digit in y, suffix 0 followed by that digit.
  5. If y contains a ., suffix 11 at that point, otherwise suffix it after all the digits in y.

Explanation:

^.*\.(..)*1(.)((..)+)1.((..)*)$
$2$*-$3.$5

Pair the digits starting at the binary point. If the number is a valid encoding, then decode the last 1x digit pair to a . and the second last to an optional - sign. Digits before that are ignored.

0(.)
$1

This should just leave pairs that begin with 0, so delete the 0s.

\$\endgroup\$
  • \$\begingroup\$ I sometimes get outputs such as -.. Do those imply zeroes or are they not supposed to be produced? \$\endgroup\$ – Erik the Outgolfer Jun 28 at 11:36
  • \$\begingroup\$ @EriktheOutgolfer I guess I could change the *s to +s, that would guarantee at least one digit before and after the .? \$\endgroup\$ – Neil Jun 28 at 11:54
  • \$\begingroup\$ Actually I can't guarantee digits after the .. I think I can still guarantee a digit before the . though. \$\endgroup\$ – Neil Jun 28 at 11:55
  • \$\begingroup\$ An additional terminal 0 in a number with . doesn't change its value, but such a change in the input of your function changes the output. Maybe you are allowed to fix this by assuming input has no such 0s. Also, if you group pairs from the right, how does this "theoretically work for any real input"? \$\endgroup\$ – Christian Sievers Jun 29 at 11:01
  • \$\begingroup\$ @ChristianSievers (Sorry I didn't notice my inbox earlier) I based my answer on the description of the base 13 function in the question, which seems also to require a terminating representation. Also you're right that I was assuming that there would be no trailing zeros. (So integers always have to have 11 appended in step 2.) \$\endgroup\$ – Neil Jun 29 at 23:22
1
\$\begingroup\$

Jelly, 71 bytes

L7*©ṛḅ7WµṪ×⁵d®µ⁴‘¤Ð¡ḊṖ
DF7,8ṣṪ¥ƒṣ9ḅ7×ɗÇƭ€j”,
DFf7r9¤ṫ-Ḍ⁼Ɱ“OY‘TịØ+³çƲ0Ẹ?

Try it online!

A full program that takes a base-10 number as input and output and implements the Conway base 13 function but using bases 7 and 10 rather than 10 and 13. Both input and output use comma as a decimal separator. Output will have a leading - for negative numbers.

\$\endgroup\$
  • \$\begingroup\$ The example at the TIO link has the digit 9 in the input and the output, so how are these base 7 numbers? \$\endgroup\$ – Christian Sievers Jun 29 at 10:51
  • \$\begingroup\$ @ChristianSievers sorry meant base 10 for input and output. Base 7 is used in the code, but is converted back to base 10. \$\endgroup\$ – Nick Kennedy Jun 29 at 12:02
  • \$\begingroup\$ Fine, now I can change the input and understand how that affects the output! \$\endgroup\$ – Christian Sievers Jun 29 at 13:24
1
\$\begingroup\$

Retina, 28 25 26 28 bytes

.*11|22
.
D^`\.
^3
-
4(.)
$1

Try it online!

Explanation

.*11|22     Delete up to the last 11 and prepend a dot. Also change 22 to a dot.
.
D^`\.       Keep only the last dot, if there is one.
^3          Change 3 at the beginning to a minus sign.
-
4(.)        4 is the escape character.
$1

It may output leading and trailing zeros, and numbers without a integer part.

It could be golfed 2 or 3 bytes more if I could use 4+. But I'm not sure how to define the theoretical result if the input has an endless stream of 4s.

\$\endgroup\$
  • 1
    \$\begingroup\$ I got cursed by a T-shaped thing by posting this answer. \$\endgroup\$ – jimmy23013 Jul 8 at 17:37

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.