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.}

• S.S. Anne: Does a theoretically infinite list fall within the rules?
• Wheat Wizard: @S.S.Anne I'm not sure what a theoretically infinite list is.
• S.S. Anne: Meaning memory or memory model limits restrict the length of the list but given infinite memory and an unbounded memory model it would work.
• Wheat Wizard: @S.S.Anne Let's continue this discussion in chat.
• Wheat Wizard: @l4m2 Then after finite time it should output false (or equivalent).

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!

• S.S. Anne: This is good. How hard was it to come up with?
• dingledooper: Thanks! I wouldn't call it hard, since it was the first and only method I came up with.

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!

Gif

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.

Explanation 0

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.

Explanation 1 (Ascending)

Explanation 1 (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.

Explanation 2

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.

Explanation 3

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.

• xash: Congratulations, you are the first other convey user! I'm really happy that it's apparently usable for someone else, thanks! :-) If there is a fixed number of elements, you can often use ? instead of @, e.g. at the top instead of 01@v...>(, ?v...>(. Or at the bottom ? to just have one element: this should be equivalent. And there seems to be a bug that & omits every second item in this configuration, will try to fix that now.
• Wheat Wizard: @xash Thank you convey is a lot of fun! I figured how to use ? a bit on my second try (which is a lot shorter). On the topic of bugs is # supposed to act like a queue? It has been a bit of a source of frustration for me and I don't see it in the docs.
• xash: ... finally fixed # and & passing all my tests and both your solutions. They shouldn't queue, but I guess the paths shouldn't block each other. Nice second solution!

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.

• Jonathan Allan: \nN=next has cost a byte
• ovs: @JonathanAllan thanks for pointing it out.
• user2357112: Python 3.8 is already released, by the way.
• S.S. Anne: @user2357112 It's not manually typed out. That's just the way TIO has it on there.
• Olivier Grégoire: a*(b:=a-l())>v*b for a byte saved

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).

• user41805: You should be able to convert (echo $m;head -$[(m-(1ドル))**2]) into a single sed 'call', and so remove the need for the parens
• Mitchell Spector: @user41805 Thanks -- I hadn't thought of using sed to replace both the echo and the head. (I had tried replacing head with sed early on but just doing that didn't shorten things.)
• user41805: Nice including the 1 in front of the number, I missed that, this now allows you to bring 1i$m after the q statement, saving on the newline and the quotes. Additionally, the 1 can be dropped as well. Hm I wonder if awk would be shorter
• Mitchell Spector: @user41805 Thanks again -- reversing the order of the sed commands saved a byte. It got rid of the quotes, but the newline had to be replaced with the 2 characters \;. I haven't looked into using awk.
• user41805: You should be able to remove the 1 in 1i$m

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.

• Greg Martin: Is the 11th byte y or I?
• Kevin Cruijssen: @GregMartin Oops.. error curing copy-paste from the test suite. It's supposed to be I (push input). Thanks for noticing.
• Grimmy: 0‹ can be d by switching the two branches.
• Grimmy: Here's a 7
• Kevin Cruijssen: @Grimmy Nice approach! I think it might be better if you post it as a separated answer, since it's completely different from my approach with .i. :)

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

NθNηNζW›Π−⟦θη⟧ζ0NζNo⟦ηζ⟧θ

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:

Nθ

Input a.

NηNζ

Input the first two terms of the list.

W›Π−⟦θη⟧ζ0

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

Nζ

Read another term from the list.

No⟦ηζ⟧θ

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!

• vrintle: Unfortunately, it gives me error on 4th test case: The request exceeded 60 second time limit and was terminated.

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.

• user41805: You need to include {} in a dfn, because by itself it isn't a valid function
• RGS: @user41805 Are you sure? :'(
• Adám: @RGS Yes.
• RGS: @Adám damn it, went from "winning by 1 byte" to "2nd place by 1 byte" :)
• Adám: @RGS Don't worry about it; you're still winning big in the "production languages" category!

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!

• l4m2: You don't need $$k^2>(g(0)-n)^2$,ドル $$k$$ being some larger is not a problem

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!

• dingledooper: Nice, but did you forget to remove that ‘n’ at the beginning, because I don’t really see the point of it.
• S.S. Anne: That was from the old way, with the generator function. I'll get rid of it when I have access to my computer.
• Varad Mahashabde: How would it stop in case of the second case? (6 in -1,-2,...)
• S.S. Anne: @VaradMahashabde That's what the abs is for in the initialization of the counter variable.

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.

• math junkie: I don't think this works for decreasing input sequences: Try it online!

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