Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

This question already has an answer here:

Suppose I want to compute $f(1)\vee f(2) \vee \ldots \vee f(10^{10})$, but I know a priori that $f(n)$ is True for some $n \ll 10^{10}$ with high probability. For example, f = PrimeQ.

One way to do this is to write: Or[f/@Range[1,10^10]], but that would involve allocating memory for $10^{10}$ elements, as well as computing f unnecessarily. (I overcame the latter problem with using Hold, but the memory problem still stands).

Question: Is there a way to compute Or[f[1], ..., f[10^10]] without allocating memory for $10^{10}$ booleans?

I've done some research: it seems like Functional style using lazy lists? might work, but I'm wondering if there is a shorter solution -- one that does not involve defining streams?

share|improve this question

marked as duplicate by Mr.Wizard Jul 23 '13 at 3:39

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
Maybe I missing something but if you know that f[n] is True for n<<10^10 isn't then Or automatically True? Even if you do not know if it is so then one occurance is enough: Do[If[PrimeQ@i, Print[i]; Break[];], {i, 10^10}] –  Kuba Jul 22 '13 at 21:50
    
Ah, sorry I should have been more clear. I meant that there is a high probability that f[n] is True for some n << 10^10. But yes, a Do loop seems like what I need. I still wonder though, if there is a more functional way of approaching this problem. –  user12677 Jul 22 '13 at 22:11
    
I am closing this question as a duplicate. If you feel that your question is not addressed there please clarify for me how it is different and I shall reopen this. –  Mr.Wizard Jul 23 '13 at 3:39

2 Answers 2

up vote 5 down vote accepted

Streams and iterators

Using streams would certainly be one of the most elegant ways to do this. In any case, you will at least need an iterator for your sequence of numbers. The reason why an abstraction of an iterator is useful is because it separates the iteration over your sequence from the stuff you want to do with individual elements, so that you can implement them independently. It also inverses the control, since rather than doing an active iteration with your sequence, you get a next number on demand. This leads to a more modular code and better abstractions.

Iterator for a sequence of numbers

Here is one possibility. First, define an iterator for equidistant numbers:

ClearAll[makeIterator];
makeIterator[min_,max_,step_]:=
    Module[{current=min},            
        With[{curr=current},
            current=If[current+step<=max,current+step,Null];curr
        ]&
    ];

it can be used as

iter = makeIterator[1, 10, 1];
iter[]
iter[]
iter[]

(*
  1
  2
  3
*)

Implementation of Or

Now, here is a possible implementation of Or:

ClearAll[lazyOr];
lazyOr[iter_,f_]:=
    While[            
        True,
        (If[#1=!=Null,If[f[#1],Return[True]],Return[False]]&)[
            iter[]
        ]
    ]

and here is how we can use it:

lazyOr[makeIterator[1, 10, 1], # > 10 &]

(* False *)

lazyOr[makeIterator[1, 10, 1], # > 9 &]

(* True  *)

lazyOr[makeIterator[1, 10^10, 1], PrimeQ] // AbsoluteTiming

(*  {0.000977, True}  *)

Again, I want to stress that this is just a light-weight version of the lazy streams, where we had to make Or less trivial because it should do the iteration. The full lazy stream construction postpones iteration until we actually request an element, and is more elegant in that sense.

share|improve this answer
    
Is an analog possible when I am interested in the set of values {f(a) : a in A} for some arbitrary finite set A, not just when A = {1, ... ,n} for some n? EDIT: It seems all I need to do is to generalize the makeIterator function, so that it takes in a set (list) and returns an iterator for that list. Is this possible? –  user12677 Jul 22 '13 at 22:17
    
@user12677 It is possible in cases when you can enumerate your set in some way - provide a next operator that would, when applied to a current element, produce the next element, for some specific ordering of your set. It should be such that repeated application of next would exhaust your set. So, if such an ordering and an operator exist (if you can construct them), then this will work. Of course, if you already have a list of elements, it will induce a natural ordering by position, but this is a special case. –  Leonid Shifrin Jul 22 '13 at 22:21
    
@user12677 Well, if you have a list, then the generalization is rather trivial: makeIterator[lst_List] := With[{len = Length[lst]}, Module[{n = 1},Function[If[n <= len, lst[[n++]], Null]]]]. –  Leonid Shifrin Jul 22 '13 at 22:25
    
I see. Thank you very much for your code and explanations; I accepted your answer. –  user12677 Jul 22 '13 at 23:17
    
@user12677 Was glad to help. Thanks for the accept. –  Leonid Shifrin Jul 22 '13 at 23:55

It looks like you only need a looping construct that terminates when the first True is encountered with the Or operation. So how about this:

f = PrimeQ

(* ==> PrimeQ *)

notFound = False;
n = 0;
While[! notFound,
 n += 1;
 notFound = notFound || f[n]
 ]; n

(* ==> 2 *)
share|improve this answer

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