17
\$\begingroup\$

Your task is to make a program that decides if a real number between 0 and 1 is irrational or not. As stated, this is obviously impossible, so instead we will use the following definition:

p is your program, which takes in a decimal expansion of a number (list of integers), and returns 0 (≈Rational) or 1 (≈Irrational). If x is an irrational number, then \$\limsup\limits_{n\rightarrow\infty}p(x[:n])=1\$, and if x is rational the limit superior has to be 0. \$x[:n]\$ means the truncated decimal expansion, which is just the first n digits after the decimal point.

Or in other words, iff x is rational, there should be some n such that all prefixes longer than n return Rational.

This is , so shortest code wins. Also, standard rules apply, so instead of outputting 0 or 1, you can output true,false, "Irrational", "Rational", etc. As we know, \$0.999...=1\$, so you can assume that the decimal expansion doesn't contain a trail of repeating 9s. Instead of decimal, you can use binary. The input list is non-empty.

Explanation

Your program will receive a list/string of decimal digits corresponding to a truncated decimal expansion of that real number. For example, if we had the real number 0.31415926..., the program could receive [3,1,4] or [3] or [3,1,4,1,5,9,2] etc. as input. The program then has to guess whether the real number is irrational or not.

Of course, it's impossible to always guess correctly. What matters is what happens when the input length increases (the limiting behavior). Let's use the rational number 8/13=0.6153846153846153846153846... as example. If we gave the program the first three digits [6,1,5], it might (incorrectly) guess that the number is irrational. But if we gave the program at least 30 digits, it might correctly guess (every time) that the number is rational.

In other words, if your program is given the decimal expansion of a rational number \$q\$, there must be some \$n\$ so that if at least \$n\$ digits are given to your program, it will always return Rational.

For irrational numbers the opposite is true. For every irrational number \$r\$ there must be infinitely many \$n\$ so that if you give the first \$n\$ digits of \$r\$ as input, the program returns Irrational.

Implementation hints

Every rational number has a repeating decimal expansion and all irrational numbers have non-repeating decimal expansions.

Possible program execution ("test cases")

# 41/333 = 0.123123123123...
[1] -> Rational
[1,2] -> Rational
[1,2,3] -> Irrational
[1,2,3,1] -> Irrational
[1,2,3,1,2] -> Irrational
[1,2,3,1,2,3] -> Rational
[1,2,3,1,2,3,1] -> Rational
[1,2,3,1,2,3,1,2] -> Rational
[1,2,3,1,2,3,1,2,3] -> Rational
[1,2,3,1,2,3,1,2,3,1] -> Rational
[1,2,3,1,2,3,1,2,3,1,2] -> Rational
[1,2,3,1,2,3,1,2,3,1,2,3] -> Rational
[1,2,3,1,2,3,1,2,3,1,2,3,1] -> Rational
# pi/10 = 0.31415926...
[3] -> Rational
[3,1] -> Rational
[3,1,4] -> Irrational
[3,1,4,1] -> Irrational
[3,1,4,1,5] -> Irrational
[3,1,4,1,5,9] -> Irrational
[3,1,4,1,5,9,2] -> Irrational
[3,1,4,1,5,9,2,6] -> Irrational
# 7/24 = 0.291666666...
[2] -> Rational
[2,9] -> Rational
[2,9,1] -> Irrational
[2,9,1,6] -> Irrational
[2,9,1,6,6] -> Irrational
[2,9,1,6,6,6] -> Rational
[2,9,1,6,6,6,6] -> Rational
[2,9,1,6,6,6,6,6] -> Rational
[2,9,1,6,6,6,6,6,6] -> Rational
[2,9,1,6,6,6,6,6,6,6] -> Rational
[2,9,1,6,6,6,6,6,6,6,6] -> Rational
# 0.10110000111111110...
[1] -> Rational
[1,0] -> Rational
[1,0,1] -> Irrational
[1,0,1,1] -> Rational
[1,0,1,1,0] -> Irrational
[1,0,1,1,0,0] -> Irrational
[1,0,1,1,0,0,0] -> Irrational
[1,0,1,1,0,0,0,0] -> Rational
[1,0,1,1,0,0,0,0,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1,1,1,1] -> Irrational
[1,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1] -> Rational
[1,0,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0] -> Irrational
# 333/500 = 0.66600000000...
[6] -> Rational
[6,6] -> Rational
[6,6,6] -> Rational
[6,6,6,0] -> Irrational
[6,6,6,0,0] -> Irrational
[6,6,6,0,0,0] -> Rational
[6,6,6,0,0,0,0] -> Rational
[6,6,6,0,0,0,0,0] -> Rational
Improve this question
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Suggestion to change the 0 and 1 in the second paragraph to False and True, to be clearer that you're talking about the code there; I first read the lim sup ... = 1 part as some math result you were stating (especially since I was unfamiliar with the notation) and was really confused. \$\endgroup\$
    – Sundar R
    Commented Mar 8, 2022 at 16:44
  • 1
    \$\begingroup\$ @SundarR Maybe "x is irrational iff \$\sum_{i=1}^{\infty}p(x[:i])=\infty\$ is easier parsed \$\endgroup\$
    – l4m2
    Commented Mar 8, 2022 at 17:01
  • 2
    \$\begingroup\$ @l4m2 That seems way harder to parse. Really I think the whole thing could better be stated as "Iff x is rational, there should be some n such that all prefixes longer than n return Rational". The notation just gets in the way of a pretty straight forward claim. \$\endgroup\$
    – Wheat Wizard ♦
    Commented Mar 9, 2022 at 0:37
  • \$\begingroup\$ @WheatWizard mine is easier parsed but harder understood \$\endgroup\$
    – l4m2
    Commented Mar 9, 2022 at 13:09

9 Answers 9

Reset to default
5
\$\begingroup\$

Jelly, 5 bytes

ŒHṪẇṖ

A monadic Link that accepts a list and yields 1 (≈rational) or 0 (≈irrational).

Try it online! Or see the test-suite (results being the application to each prefix of each input).

How?

Identify a list, L, as rational if the last half is a sublist of L without its final element (i.e. appears anywhere earlier).

ŒHṪẇṖ - Link: list, L
ŒH    - split L into two halves (first half longer when odd in length)
  Ṫ   - tail -> X = last half of L
    Ṗ - pop L -> Y = L without its final element
   ẇ  - is Y a sublist of X?
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Define a sequence of strings \$a_0=0\$ and \$a_n=a_{n-1}1a_{n-1}1\$. \$\lim_{n\to\infty}0.a_n\$ is well defined and not rational, but this method yields 1 for all \$0.a_n\$. Try it online! \$\endgroup\$
    – att
    Commented Mar 9, 2022 at 5:26
  • \$\begingroup\$ Proof of irrationality: the longest string of consecutive \$1\$s in \$a_n\$ has length \$n\$. \$\endgroup\$
    – att
    Commented Mar 9, 2022 at 5:31
  • 1
    \$\begingroup\$ @att But it seems like the code handles prefixes of a_n just fine. The try-it-online you linked contains both zeroes and ones. It doesn't matter if a sub-sequence of the prefixes of an irrational number always yields rational, as long as the full sequence yields irrational an infinite number of times. In fact, I don't think this challenge is possible if there would be such strict requirements. \$\endgroup\$
    – AnttiP
    Commented Mar 9, 2022 at 8:18
  • 1
    \$\begingroup\$ @AnttiP Ah, I see my mistake. Got confused somewhere in the middle... \$\endgroup\$
    – att
    Commented Mar 9, 2022 at 9:00
4
\$\begingroup\$

Retina 0.8.2, 33 bytes

((.)+)$(?<=^(?<-2>.)+\1(?<-2>.)+)

Try it online! Link includes test cases. Explanation: Requires that at least the last half of the input is repeated somewhere between it and the start (exclusive). The middle + could be changed to * to allow matching at the start but I thought it looked prettier this way and it doesn't matter in the long run.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 45 bytes

x=>x.match(`^.{0,${x.length>>1}}(.+)\\1{9}$`)

Try it online!

Requiring any length have a *10 loop allowing some left before, so rational number works; not well confirmed on irrational though

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ If a loop is detected after digits n and n+1, then by shifting left by the period detected at n+1, we see that digit n+1 must continue the repeating pattern detected at position n. With more care, this can be extended to a proof that the number is rational if the output is eventually 1. \$\endgroup\$
    – Nitrodon
    Commented Mar 8, 2022 at 16:15
3
\$\begingroup\$

PARI/GP, 41 bytes

a->prod(i=1,#a,#Pol(Ser(a)*(1-x^i))>#a/2)

Attempt This Online!

a->prod(i=1,#a,#Pol(Ser(a)*(1-x^i))>#a/2)

a ->                                         Define a function with argument `a`
   prod(i=1,#a,                         )    Take product, where `i` runs from `1` to the length of `a`
                    Ser(a)                   Convert `a` to (truncated) power series
                          *(1-x^i)           Multiply `1 - x^i`
                Pol(              )          Convert to a polynomial
               #                             Take the length of the polynomial, i.e., degree + 1
                                   >#a/2     Check if the result is larger than half of the length of a

Take a = [2,1,6,1,6] as an example:

  • Ser(a) is 2 + x + 6*x^2 + x^3 + 6*x^4 + O(x^5).
  • When i = 2, Ser(a)*(1-x^i) is 2 + x + 4*x^2 + O(x^5).
  • #Pol(Ser(a)*(1-x^2)) is 3, which is equal to the half of the length of a.
  • So the result is 0.
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

R, 69 73 bytes

(or 59 bytes in R≥4.1 by changing two function keywords each to \)

Edit: changed approach to give correct output for A003842.

function(x,l=sum(x|1)/2,s=1:l)all(Map(function(i)any(x[l+s]-x[s+i]),s-1))

Try it online!

Returns FALSE for suspected rational numbers, and TRUE for suspected irrational numbers.
Based on approach of Neil's answer: checks whether the second half of the input sequence is identical to any subsequence except itself.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Husk, 6 bytes

§€ho→½

Try it online!

Or try it online with a rational test-case with a non-repeating prefix, or try it online with the first few digits of pi, or try it online with the first few digits of A003842.

Ports Neil's answer: checks whether the second half of the input sequence is present within the input without its last digit.

Unfortunately my initial attempt (ṁoV=½ṫ, which checked whether the input digits end in a repeated sequence, fails for the non-repeating sequence A003842 [credit to Bubbler for finding this]).

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Hi, not saying the answer is wrong, but do you have proof that this works for irrational numbers? I would suspect so, but can't formulate a proof. \$\endgroup\$
    – AnttiP
    Commented Mar 10, 2022 at 5:45
  • \$\begingroup\$ @AnttiP - I don't have a proof; it just seemed intuitive... but I'll try to think about a proof, though... \$\endgroup\$
    – Dominic van Essen
    Commented Mar 10, 2022 at 7:34
  • \$\begingroup\$ Don't think too hard, because Bubbler found a counterexample \$\endgroup\$
    – AnttiP
    Commented Mar 10, 2022 at 7:35
  • \$\begingroup\$ @AnttiP - Rats! Updated now to a port of Neil's answer. \$\endgroup\$
    – Dominic van Essen
    Commented Mar 10, 2022 at 13:51
1
\$\begingroup\$

Charcoal, 12 bytes

›÷Ｌθ²⌕θ✂θ⊘Ｌθ

Try it online! Link is to verbose version of code. Takes input as a string and outputs a Charcoal boolean, i.e. - for probably rational, nothing for probably irrational. Explanation:

   θ            Input string
  Ｌ             Length
 ÷              Integer divided by
    ²           Literal integer `2`
›               Is greater than
      θ         Input string
     ⌕          Find index of
        θ       Input string
       ✂        Sliced from
           θ    Input string
          Ｌ     Length
         ⊘      Halved

(Slice truncates its parameters so I don't have to use integer division.)

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 57 bytes Invalid solution

import Data.List
(==[[]]).intersect<*>map(\a->a++a).tails

True for irrational number, False for rational number

I used a different algorithm for this program. This program returns true if the sequence ends with two identical sequence next to each other. For example, this program returns true for [1,2,3,4,3,4] because it ends with [3,4,3,4], which is [3,4] repeated twice.

For rational number, it's obvious that this will return false for large enough string, because rational number always ends with repeating string of digits. However, I don't know if this program still works for irrational number. Turns out it doesn't work for irrational numbers.

Haskell, 60 bytes

import Data.List
isInfixOf<$>(drop=<<(`div`2).length)<*>init

Turns out that the fixed solution is not that worse. This uses the more standard solution: whether the last half of the string still appears anywhere else in the string.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ This doesn't work. Conterexample: start from "001001" and then randomly add either "001" or "01001" (example: "001001010010010010100101001..."). The resulting string will be non-repeating (irrational) but your algorithm will return Rational for every prefix longer than 5 characters. \$\endgroup\$
    – AnttiP
    Commented Mar 10, 2022 at 12:43
  • \$\begingroup\$ @AnttiP Thanks for letting me know. But I think I can only start fixing it tomorrow. \$\endgroup\$
    – Xwtek
    Commented Mar 10, 2022 at 15:51
  • \$\begingroup\$ @AnttiP fixed now \$\endgroup\$
    – Xwtek
    Commented Mar 11, 2022 at 13:15
1
\$\begingroup\$

BQN, 24 bytes

(↓⊑˜2⌊∘÷˜≠)⋈⊸∊{∾↑¨↓¯1↓𝕩}

Try it at BQN online REPL

Ungolfed: for input 𝕩, checks whether (SecondHalfOf 𝕩) IsOneOf SublistsOf HeadOf 𝕩.
Try the ungolfed code here

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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