Check membership of an infinite list

Question

As input you will receive

• An integer \$a\$

• A list of integers that is infinite and strictly-monotonic¹.

Your program should check in finite time if \$a\$ appears the list.

You should output one of two distinct values. One if \$a\$ appears in the list and the other if \$a\$ does not.

This is code-golf so answers will be scored by their length in bytes with fewer bytes being better.

---

You may take an infinite lists in any of the following formats:

• A list, stream, iterator or generator if your language allows them to be infinite.

• A function or pointer to a function that outputs the next value when queried with no input.

• A function or pointer to a function that outputs the \$n\$th value when passed \$n\$ as an input.

Additionally you may repeatedly query STDIN with the assumption that each query will provide the next term in the sequence.

---

Test cases

Since I cannot put infinite lists in the body of a challenge I will provide the first couple terms along with a description of the list and a definition in Haskell.

6
1 2 3 4 5 6 7 8 9 10 ... (positive integers) l=[1..]
 =>
True

---

6
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ... (negative integers) l=[-1,-2..]
 =>
False

---

109
0 2 4 6 8 10 12 14 16 18 20 ... (non-negative even integers) l=[0,2..]
 =>
False

---

-5
200 199 198 197 196 195 194 193 192 ... (integers smaller than 201) l=[200,199..]
 =>
True

---

256
1 2 3 5 8 13 21 34 55 89 144 ... (unique Fibonacci numbers) l=1:2:zipWith(+)l(tail l)
 =>
False

---

1
1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 ... (integers less than 2) l=[1,0..]
 =>
True

^{1: A strictly monotonic sequence is either entirely increasing or entirely decreasing. This means if you take the differences between consecutive elements they will all have the same sign.}

Answer 1

Python 2, 43 bytes

Takes as input the target integer \$a\$, and a lambda function \$g\$. Since the list is always either strictly increasing or decreasing, we only need to check if \$a\$ appears in the next \$ |a-g(0)|+1 \$ numbers.

lambda a,g:a in map(g,range(abs(a-g(0))+1))

Try it online!

Answer 2

Haskell, 33 bytes

t#l@(a:r)=t==a||(a<t)==(l<r)&&t#r

Try it online!

Answer 3

convey, 144 92 bytes

 v<<<<<<<<<<<
>;  >">>??>=@]
"">>,<1[v)>#,
v}^>)?:`(#>#^
v{^"9>v]^",^
>;@">>@`"#^
1>0   >>>^

Try it online!

Input is given as a list of integers with the first integer being the goal and the remaining being the list. Since there is no way to accept infinite input, this program instead only consumes a prefix of the input. You can see this in that there is a very long relay line to stop additional input.

Explanation

To start we need to split the first element off the input, to be used. To do this I use a simple switch, and because we want to use the input a bunch I feed it into a sort of generating vortex to continuously pump out new copies.

Now we split the main stream in two, and calculate the differences on one of the parts. This will tell us if the list is ascending or descending.

Now we use the difference stream to redirect the main stream, to the two different comparison sites. If the list is ascending we want to go until the element is greater than or equal to n if it is descending we want to go until it is less than or equal to n.

So that stream coming out now will give us some ones and then at some point switch to zeros. What we are concerned about is the first number that gives a zero. We want to know if it is equal to n. So we create another stream and get whether that is equal to n.

At this point I'm going to stop with the gifs, since they really look like the end product mostly. We redirect the streams with each other, discarding all the elements before the comparison starts giving zero. Then we use a lock to grab just the first equality. We output this and send a signal to stop taking input. With no input the machine slowly winds down and halts.

Answer 4

Python 3.8 (pre-release), 61 bytes

def f(l,v):
 a=l()
 while(a-v)*(b:=a-l())>0:a-=b
 return a==v

Try it online!

Input is a function that returns the next value on every call and an integer.

---

Python 3.8 (pre-release), 70 69 bytes

1 byte shorter thanks to @JonathanAllan.

def g(l,v):
 a=next(l)
 while(a-v)*(b:=a-next(l))>0:a-=b
 return a==v

Try it online!

Input is a generator and an integer, can probably be shorter with one of other input formats.

Answer 5

Haskell, 43 bytes

a#k@(b:c)|k>c=(-a)#map(0-)k|b<a=a#c|1>0=b>a

Try it online!

This outputs False if the integer is present and True if it is not although I have added a not to the handler because that sort of output is confusing to me.

---

Explanation

The first check we do is k>c, that is whether the input is greater than its own tail. Since this list is strictly monotonic the heads of these lists cannot be equal so k>c is a short way of comparing their heads. This check thus tells us whether the first element is larger than the second and by extension whether the input is decreasing. If the input is decreasing we negate everything to make it increasing

(-a)#map(0-)k

The next check is whether b<a, that is the head of the list is less than the thing we are looking for. If it is then we should find a later in the list so we discard b and go again

a#c

If that fails then a<=b meaning that either b is a or b should come before a. Since b is the first element we know that the only way for a to be present is for it to be b. Thus we halt returning

b>a

Which is a shorter way of writing b/=a since we know already that b>=a.

Answer 6

Bash + GNU utilities, ^{47 44 43} 42 bytes

read m
sed 1$[(m-($1))**2]q\;i$m|grep ^$1$

Try the test suite online!

3 bytes off thanks to user41805's pointing out that a single sed could be used to replace both the echo and the head.

1 more byte thanks to user41805 again.

And now 1 more from user41805.

The target integer (the integer \$a\$ in the challenge description) is passed as an argument, and the infinite list is read from stdin. (The challenge says: "Additionally you may repeatedly query STDIN with the assumption that each query will provide the next term in the sequence.")

The output is the program's exit code (0 for truthy, 1 for falsey).

---

Explanation:

The program reads the first number in the infinite list into \$m\$.

Let \$a\$ be the target integer that we're looking for (it's $1 in the program). In principle we need to check, after \$m\$, at most \$\left| m-a \right|\$ additional values in the infinite list, because we're starting at \$m\$ and either going up by at least 1 for each number in the list or going down by at least 1 for each number in the list.

However, the program actually checks (more than) \$(m-a)^2\$ additional values. That's OK, because \$(m-a)^2\ge\left|m-a\right|\$. We may be checking additional (unnecessary) values, but that's harmless.

The original version checked exactly \$(m-a)^2\$ additional numbers (using head). Unfortunately, replacing head -${n} with sed -${n}q doesn't work if the value of n is 0, so we need to enlarge the number of items checked. To do this, I simply prepend a 1 to the number (which takes one fewer byte than adding 1 to it).

The golfing benefit in doing all this is that, in bash, squaring a number requires fewer bytes than taking the absolute value of a number (as far as I can see).

Answer 7

05AB1E, 14 13 bytes

D¥нdiIë(I(}.i

-1 byte thanks to @Grimmy.

05AB1E has infinite lists, but no functions. So it assumes the infinite list is already at the top of the stack. Assuming this is allowed for stack-based languages according to the meta, but it explicitly mentions functions, so not sure how to handle it here.

Alternatively, the infinite list can be put in a pre-defined variable (i.e. X), in which case this would be 15 bytes with that X as additional leading byte.

Try it online or verify all test cases. The second line of the header contains the infinite list(s). In the output the first 10 values are printed as example sublist, so you know which infinite list was used in the program.

Explanation:

05AB1E has a builtin to check if an integer is in an infinite list that is guaranteed to be non-decreasing, which is .i. Using that builtin, we have the following program:

D         # Duplicate the infinite list at the top of the stack
 ¥        # Take it's deltas / forward-differences
  н       # Pop and push the first difference of this list
   di     # If it's non-negative:
     I    #  Simply push the input-integer
    ë     # Else (it's negative):
     (    #  Negate all values in the infinite list
      I(  #  Push the input-integer, and negate it as well
    }     # After the if-else, where we now have a non-decreasing infinite list
     .i   # Check if the (possibly negative) input we pushed is inside this infinite list
          # (after which the result is output implicitly)

Note that this approach only works because the infinite list is guaranteed to be either only increasing or only decreasing. With an infinite list that is both (i.e. \$a(n) = \left\lfloor10\tan(n)\right\rfloor\$ → [0, 15, -22, -2, 11, -34, -3, 8, -68, -5, ...]), this approach of course wouldn't work.

Answer 8

Pyth, 20 17 16 9 bytes

Takes a on STDIN, then a list of values on STDIN.

Edit: Wow, under 10 bytes now! Really shows how powerful Pyth is :P

}Q+JEmEaJ

Try it online!

Port of @dingledooper's Python answer.

}Q+JEmEaJ
 Q              # Initialize Q to be the first input from STDIN
   JE           # Initialize J to be the next input from STDIN
}Q              # Return true if Q is in:
  +             #   The union of 
   JE           #      - the first element of the sequence
     mEaJ(Q)    #      - abs(J-Q) more inputs from STDIN (Q appended implicitly)

---

8 bytes, if we can return the index of a in the list

x+JEmEaJ

Try it online!

x+JEmEaJ
x          (Q)  # Find index of Q in:
 +              #   The union of:
  JEmEaJ(Q)     # J and the next abs(J-Q) elements

Answer 9

K (ngn/k), 21 bytes

{|/x=y'!1+|/-:\x-y.0}

Try it online!

Explanation

x is number, y is function representing infinite list.

• 1+|/-:\x-y.0 equivalent to 1 + abs(x - y(0))
• ! range
• y' apply y to each element
• |/x= find x

Answer 10

GolfScript, 33 bytes

(@:k\-abs:r;0:g;{(k=g+:g;}r*;r!g+

Try it online!

This is a very, very quick and dirty way of doing this problem.

TL;DR

Check if the first number is the number we're looking for. If not, then find the difference between our number (finite) and the first number (finite) to get the maximum number of elements we need to search (finite). This is a clusterfuck, clumsy, and messy, but it does the job adequately. There's probably a builtin I'm missing, but I'll come back to this later to refine it and to make code short enough worthy of an explanation.

Answer 11

Charcoal, 24 bytes

ＮθＮηＮζＷ›Π⁻⟦θη⟧ζ⁰Ｎζ№⟦ηζ⟧θ

Try it online! Link is to verbose version of code. Reads each value as a separate line on STDIN and outputs - only if a appears in the monotonic list. Explanation:

Ｎθ

Input a.

ＮηＮζ

Input the first two terms of the list.

Ｗ›Π⁻⟦θη⟧ζ⁰

Repeat while the last term of the list so far lies between a and the first term.

Ｎζ

Read another term from the list.

№⟦ηζ⟧θ

Output - if a is the first term or the term just read.

Answer 12

Ruby, 39 bytes

->a,g{[]!=[a]&(0..a*a+g[0]**2).map(&g)}

Try it online!

Answer 13

APL (Dyalog Unicode), 15 bytes^SBCS

{⍵∊⍺⍺⍳1+|⍵-⍺⍺1}

Try it online! Uses dingledooper's idea.

{             } ⍝ Operator accepting function on the left and integer on the right
   ⍺⍺           ⍝ Apply the input function to
     ⍳           ⍝ the range of integers from 1 to
      1+         ⍝ 1 plus
        |        ⍝ the absolute value of
         ⍵-      ⍝ the input number minus
           ⍺⍺1   ⍝ the first value of the input function.
 ⍵∊              ⍝ Finally check if the input number is in that list.

Answer 14

05AB1E, 7 6 bytes

α¬>£0å

Try it online! or verify all test cases.

Takes the infinite list input via the stack, like Kevin's 05AB1E answer.

α              # absolute difference of the number with each element of the infinite list
               # this list contains 0 iff the original list contains the number
 ¬             # get the first element
  >            # increment
   £           # get the first n elements, where n = first element + 1
    0å         # check if 0 is in those elements

Answer 15

Wolfram Language (Mathematica), 31 bytes

#2@Range@Abs[#-#2@0]~MemberQ~#&

Port of dingledooper's python 2 solution.

Try it online!

Other similar attempts:

⌊#⌋==#&&#>=1&@InverseFunction[#2]@#&

and:

Tr[1^Solve[#2@x==#,x,PositiveIntegers]]==1&

9 bytes

Mathematica doesn't have iterators or generators in the same way python does, but Regions and Domains take their place. If you allow Regions as an equivalent,

{#}∈#2&

just tests if the 1d point of the first argument is in the Region. RAW (Rules as written) don't allow Regions, so I'm going to leave the port as the main answer.

Try it online!

The best solution is just Mathematica's built-in Element over a domain, but Domains do not seem to be able to be defined by the users, only the premade handful exist.

Answer 16

Desmos, 41 bytes

f(k)=∑_{n=0}^{(k-g(0))^2}0^{(g(n)-k)^2}

Because Desmos does not support infinite lists and does not support functions as arguments, the input list should be represented as a function named g.

Pretty much a port of dingledooper's Python answer, except I replaced absolute value with square because that is golfier.

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 17

JavaScript (ES7), 49 bytes

Using @dingledooper's method

Takes input as (integer)(generating_function). Returns \$0\$ or \$1\$.

n=>g=>(F=k=>k*k>(g(0)-n)**2?0:g(k)-n?F(k+1):1)(0)

Try it online!

---

JavaScript (ES6), 54 bytes

Takes input as (integer)(generating_function). Returns a Boolean value.

n=>g=>(F=k=>(v=g(k),g(1)>g(0)?v<n:v>n)?F(k+1):v)(0)==n

Try it online!

Answer 18

C (gcc), 59 bytes

t;f(a,p)int*p;{for(t=abs(a-*p)+2;t-->0;)t=*p++-a?t:-1;++t;}

Takes a pointer to an "infinite" array. The way I implement this is to only calculate the numbers that are used (and then a "safe buffer" at the end to make sure I don't have any off-by-one errors, but this won't skew the result).

Es un puerto de la solución de dingledooper.

-1 byte thanks to ceilingcat!

Try it online!

Answer 19

Pip -x, 24 bytes

W(Y(bi))CMa=yCM(bUi)_a=y

Uses the third format of infinite list: "A function... that outputs the nth value when passed n as an input." Takes a number and a function as command-line arguments. Attempt This Online!

Explanation

W(Y(bi))CMa=yCM(bUi)_a=y
                          a is the number, b is the function, i is 0 (implicit)
W                         While...
   (bi)                     Call b with argument i
  Y                         Yank the result into y
 (     )CMa                 Compare that value with a (returns -1, 0, or 1)
           =                Equals
            yCM             Compare y with
               (b  )        Call b with argument
                 Ui         Increment i
                          ... loop:
                    _       No-op
                          When the loop exits, we've either reached or passed a
                     a=y  1 if the most recent sequence value equals a, 0 otherwise
                          Autoprint (implicit)

Answer 20

Perl 5, 55 bytes

sub f{$f=pop;@L=($F=&$f,map&$f,0..abs$_[0]-$F);pop~~@L}

Try it online!

More or less a translation of @dingledooper's Python2 answer.

Answer 21

perl -lE, 34 bytes

$t=<>;{$_=<>;$_<$t?redo:say$_==$t}

Try it online!

Prints 1 followed by a newline if the first element of the list appears elsewhere; otherwise, it just prints a newline. The program terminates after reading the first number which is equal or larger than the first number.

Answer 22

Java (JDK), 67 bytes

a->s->{int p=s.get(),n;for(;p*(n=p-s.get())>a*n;)p-=n;return p==a;}

Try it online!

Credits

• -2 bytes thanks to ceilingcat

Answer 23

C++ (gcc), 114 bytes 106 bytes

#include<iostream>
int f(int a){int p,t;std::cin>>t;if(t-=a)for(;p=t,std::cin>>t,t-=a,p*t>t*t;);return!t;}

Try it online!

---

Explanation :

Our only hope of finding \$\alpha\$ in the future terms of the list \$t\$ is if :

• We don't skip over \$\alpha \implies\$ The difference of \$\alpha\$ and \$t_n\$ doesn't change signs \$\implies \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0 \space \forall \space n\in N, n > 1\$.(If it is zero, one of the terms is our target)
• The series approaches our target \$\implies {\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|}\$

We can then combine these two conditions :
$$ {\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|} $$ $$ \implies {\left| \alpha - t_n\right|} \cdot {\left| \alpha - t_{n-1}\right|} < {\left( \alpha - t_{n-1}\right)}^2$$ $$ \text{Since we need that}\left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0, $$ $$ \text{Condition } P \equiv \left( {\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|} \right) \land \left( \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0 \right) $$ $$ P \equiv \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right) < {\left(\alpha - t_{n-1}\right)}^2 $$

Hence if \$P\$ is found to be false the either the target has been found or we have passed it (or never reach it).

Answer 24

Ruby, 56 bytes

f=->a,g,t=1{a==g[t]||(g[2]-g[1])*(g[t]-a)<0&&f[a,g,t+1]}

Recursively, checks if current term g[t] == a, then return true. Else, check if the product of difference g[2] - g[1] and a - g[t] are of opposite sign, if yes, then return false

Try it online!

---

Ruby, 40 bytes

Port of dingledooper's Python answer!

->a,g{(1..(a-g[0]).abs+1).map(&g).any?a}

Try it online!

Answer 25

Julia, 23 bytes

N\~=N∈.~(0:abs(N-~0))

Try it online!

takes a zero-indexed function as input

port of dingledooper's solution. The solution I found on my own was exactly double the length