-3

Let L be an ordered set of positive integers (for example, the set of all primes).

Here, #L = infinity, and N is a positive number serving as an upper limit. Goal is to list the following set M:

M = {all multiplicative non-linear combinations of L | each multiplicative combination < N}

For example, if L = {a,b,c, ..., inf}, a snippet of combination could be

{a*b   ,a*c    ,...,   a*inf}
{a^2 *b, a^2 *c,..., a^2*inf}
...
{a*b*c , a*c*d ,..., y*z*inf}
...

Assuming L would be finite, with #L = n, then the program would require n levels of looping,but in my problem n is unknown, instead there is the condition about N. I don't know how to loop such an unknown number of nested levels. It's this but which I'm struggling with - how to model an unknown number of loops, rather than an unknown threshold.

Specific problem details

List: list of primes P that is expanding.

Constraints: non-primes (none linear multiplicative combination of primes) under N.

closed as unclear what you're asking by Philip Kendall, amon, Samuel, gnat, Bart van Ingen Schenau Nov 7 '17 at 12:25

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    What will you do with the resulting sets? Any model must first have a purpose. – amon Nov 5 '17 at 21:38
  • 1
    "looping unknown looping can't be modeled programmatically, is there other way around?" Isn't that what a while loop is for? Looping until a specific condition is met? – user1118321 Nov 5 '17 at 23:29
  • 3
    Voting to close as unclear. What approach/methodology do you have in mind when talking about "programmatic modeling", and why do you think this problem cannot be modeled with that approach? And what does "looping unknown looping" mean? I suggest you tell us your favorite programming language, and I am pretty sure someone here can tell you how to model the problem in this language. – Doc Brown Nov 6 '17 at 13:54
  • 1
    Your statement of the problem is inherently impossible to solve. No program can list all combinations of an infinite list. Unless you have a constraint on elements of the list, such as "monotonically increasing", to allow setting an upper bound, it can't be done. – BobDalgleish Nov 6 '17 at 18:41
  • 2
    I'm honestly having a very hard time trying to understand your question. – T. Sar Nov 6 '17 at 19:42
2

Not really sure that I understood what you are after, but what you asked for looks to me like it could be solved it this way (which requires 3 nested loops, not more):

  1. start with L1={a}, generate all "multiplicative non-linear combinations" containing a (so a^2, a^3, ...) below N. Lets call these products P1, it is a finite set.
  2. continue with with L2={a,b}, generate all of these combinations where b is a factor (a^2*b, a^3*b, a^4*b, ...), (a^2*b^2, a^3*b^2, ...), where no number exceeds N. You can utilize the results from step 1 and implement it like this:

     P0={1}
     Q=union of P0,P1
     for(i=1; b^i < N; ++i):
        for each p in Q:
           if b^i*p > N: break;
           P2.insert(b^i*p);
    
  3. now you see how this continues: lets say L3={a,b,c}, generate all combinations where c is a factor. Do this by utilizing the resultset P2:

     Q=union of P0,P1,P2
     for(i=1; c^i < N; ++i):
        for each p in Q:
           if c^i*p > N: break;
           P3.insert(c^i*p);
    

Repeat this until the last element in step k, the last element of L_k exceeds N (actually N/2 should be enough).

Finally, merge the results P1, P2, ..., P_k into a single resultset.

  • the element {a, b, c, ...} are of unknown limit, bounded by condition, which requires unknown # of for loops! – Error Nov 6 '17 at 21:13
  • @Error: you said one knows N, and L is the set of all primes. So one only needs to loop over all elements of L from 2 to the maximum prime below N/2. This looks like a known limit to me. But independently from this, the solution in my answer requires simply 3 nested loops, not more. If that is not what you are after, please invest more time into your problem description to make it clearer (start with writing in full sentences, using punctuation and correct lower/upper case letters). – Doc Brown Nov 6 '17 at 21:36
  • 4
    @Error: sorry, but from your mumble I have a hard time to understand what you mean. Either I did not understand your problem description, or you did not understand my solution. So try to give a better description, or tell me exactly why you think this is not a solution. – Doc Brown Nov 7 '17 at 6:22
  • 1
    while ignoring loop of expansion(prime list), first loop for primes iteration, second for prime power iteration, third for multiplicative combination with the old generated array in your case Pi, that would work, but in your code , first loop for prime iteration, second for prime power iteration, and the third for multiplicative combination with only the first generated array P1, it should be P2, and so on, and no merging at the end. – Error Nov 7 '17 at 23:23
  • 1
    @Error: ok, that is a comment I understood, and you are right, I missed that. But it is easy to fix, see my edit. – Doc Brown Nov 8 '17 at 6:28
3

Many languages support infinite series with lazy evaluated streams. You can operate on streams without actually evaluating any elements in the stream. Here is a Scala example for the Fibonacci sequence.

Here's a Scala example that yields combinations

val L = "abcdefghijklmnopqrstuvwxyz".toCharArray.toList.map(_.toString).toStream
def combinations(stream: Stream[String], i: Int): Stream[Stream[String]] =
    stream.combinations(i).toStream.map(comb => 
        comb.reduceLeft((a, b) => s"$a*$b")) #:: combinations(stream, i + 1)
val N = 4
val result = combinations(L.take(N), 1).take(N)
result.toList.foreach(s => println(s.toList))

Yields

List(a, b, c, d)
List(a*b, a*c, a*d, b*c, b*d, c*d)
List(a*b*c, a*b*d, a*c*d, b*c*d)
List(a*b*c*d)
  • no not that either, question edited. – Error Nov 6 '17 at 17:59
  • 1
    see my edit for a scala program that yields combinations – Samuel Nov 6 '17 at 21:26
  • i didn't wrote in the question explicitly that the combination required is repetitive, but i showed that is the case in the examples, your output is the possible non-repetitive combination, in repetitive case the output is infinite list of size infinity, but there is a constraint "multiplicative repetitive combination < N" which makes it finite. – Error Nov 6 '17 at 21:29
  • is it clear now? – Error Nov 6 '17 at 21:30
  • 2
    my program creates a stream. it supports infinite recursion. as you can see I defined N=4 so the program would exit. otherwise the program would never terminate. – Samuel Nov 6 '17 at 21:37

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