# Check membership of an infinite list

• An integer $$\a\$$

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

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

• Does a theoretically infinite list fall within the rules? Apr 4, 2020 at 0:15
• @S.S.Anne I'm not sure what a theoretically infinite list is. Apr 4, 2020 at 0:25
• Meaning memory or memory model limits restrict the length of the list but given infinite memory and an unbounded memory model it would work. Apr 4, 2020 at 0:27
• Apr 4, 2020 at 0:35
• @l4m2 Then after finite time it should output false (or equivalent). Apr 20, 2020 at 15:58

# 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!

• This is good. How hard was it to come up with? Apr 4, 2020 at 1:22
• Thanks! I wouldn't call it hard, since it was the first and only method I came up with. Apr 4, 2020 at 1:25

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


Try it online!

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

• 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.
– xash
Dec 12, 2020 at 15:40
• @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. Dec 12, 2020 at 16:18
• … 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!
– xash
Dec 12, 2020 at 17:35

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

• \nN=next has cost a byte Apr 3, 2020 at 20:07
• @JonathanAllan thanks for pointing it out.
– ovs
Apr 3, 2020 at 20:48
• Python 3.8 is already released, by the way. Apr 4, 2020 at 6:40
• @user2357112 It's not manually typed out. That's just the way TIO has it on there. Apr 4, 2020 at 18:07
• a*(b:=a-l())>v*b for a byte saved Apr 7, 2020 at 7:17

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.

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

• 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 Apr 14, 2020 at 10:20 • @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.) Apr 14, 2020 at 16:55 • 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 Apr 15, 2020 at 5:42
• @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. Apr 16, 2020 at 2:13
• You should be able to remove the 1 in 1i$m Apr 16, 2020 at 5:11 # 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. • Is the 11th byte y or I? Apr 4, 2020 at 16:16 • @GregMartin Oops.. error curing copy-paste from the test suite. It's supposed to be I (push input). Thanks for noticing. Apr 4, 2020 at 16:49 • 0‹ can be d by switching the two branches. Apr 6, 2020 at 8:06 • Here's a 7 Apr 6, 2020 at 8:22 • @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. :) Apr 6, 2020 at 8:29 # Pyth, 201716 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  # 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 # 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. # 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. # Ruby, 39 bytes ->a,g{[]!=[a]&(0..a*a+g[0]**2).map(&g)}  Try it online! # APL (Dyalog Unicode), 15 bytesSBCS {⍵∊⍺⍺⍳1+|⍵-⍺⍺1}  { } ⍝ 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.  • You need to include {} in a dfn, because by itself it isn't a valid function Apr 4, 2020 at 16:50 • @user41805 Are you sure? :'( – RGS Apr 4, 2020 at 17:07 • @RGS Yes. – Adám Apr 5, 2020 at 10:09 • @Adám damn it, went from "winning by 1 byte" to "2nd place by 1 byte" :) – RGS Apr 5, 2020 at 10:18 • @RGS Don't worry about it; you're still winning big in the "production languages" category! – Adám Apr 5, 2020 at 10:20 # 05AB1E, 7 6 bytes α¬>£0å  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  # 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 # 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! • You don't need $$k^2>(g(0)-n)^2$$, $$k$$ being some larger is not a problem – l4m2 Apr 20, 2020 at 13:52 # 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! • Nice, but did you forget to remove that ‘n’ at the beginning, because I don’t really see the point of it. Apr 4, 2020 at 6:59 • That was from the old way, with the generator function. I'll get rid of it when I have access to my computer. Apr 4, 2020 at 17:41 • How would it stop in case of the second case? (6 in -1,-2,...) Apr 6, 2020 at 20:52 • @VaradMahashabde That's what the abs is for in the initialization of the counter variable. Apr 6, 2020 at 20:55 # 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. # 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)  # 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. # 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.

• I don't think this works for decreasing input sequences: Try it online! Apr 3, 2020 at 22:41

# 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!

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

# 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

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


Try it online!

# 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