0

This is a programming question on my homework for one of my courses. I haven't programmed in a couple years and I wasn't that great to begin with. I'm currently going through tutorials to get back up to speed, but it will take some time. If you guys can help me out with this problem, I would really appreciate it.

Constraints:

Each term of this sequence is a positive integer of the form 2^i*3^j*5^k, for all non-negative integers i, j, and k with i + j + k >= 1.

Can't use arrays. The algorithm to solving this problem must involve the repeated creation and merger of lists. Specifically 5 lists; a final list, temp list, and three term lists.

"The final list grows by being merged with the current temp list. The temp list, in turn, is replaced by the merger of the three term lists. New term lists are generated by multiplying the new temp list by 2, 3, and 5 respectively"

The desired sequence would go as follows: 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, . . .

David Robinson
  • 77,383
  • 16
  • 167
  • 187
JessieM
  • 11
  • 3
  • 12
    What you have done so far? Show us your effort. – kosa Sep 04 '12 at 15:40
  • See: http://stackoverflow.com/questions/7215315/find-the-kth-least-number-for-expression-2x3y5z – hammar Sep 04 '12 at 15:49
  • @Nambari Well so far I have only the basic concept down. I haven't actually written started writing a program because I'm re familiarizing myself with all of the java syntax. What I believe i have to do is created a temporary list of integers 1-n. Then I would take that list and multiply it by 2, and store the results in another list, lets call it L2. I would the the same except multiply the temp list by three and call it L3. And finally would do it with 5 and call the list L5. Then I think i would use a merge sort algorithm and store the results into Lfinal and just have it print it out. – JessieM Sep 04 '12 at 15:50
  • 1
    **the correct answer is** stackoverflow.com/a/7215642/849891 . It has linear complexity. – Will Ness Sep 17 '12 at 20:39
  • A good solution is at http://stackoverflow.com/questions/14493373/generating-a-sequence-using-prime-numbers-2-3-and-5-only-and-then-displaying – Ramin Halavati Dec 03 '13 at 09:42

1 Answers1

2

As you've explained in your question, you might do your algorithm recursively.

At step n:

The final list will represent the set F(n) = {m | m = 2^i*3^j*5^k, 1<=i+j+k<=n}

The temp list will represent the set T(n) = {m | m = 2^i*3^j*5^k, i+j+k=n}

Then, the "L2" term list will be L2(n) = 2*T(n-1)

the "L3" term list will be L3(n) = 3*T(n-1)

the "L5" term list will be L5(n) = 5*T(n-1)

To get T, T(n) = merge(L2(n), L3(n), L5(n))

To get F, F(n) = merge(F(n-1), T(n))

Once you've got this, you have to implement a function to merge 2 lists. In the main function, you just have to translate these in Java.

You can also make the lists always sorted so that merge is easy and efficient! In java, I think you can use LinkedList or ArrayList, both work fine.

After all, it's your homework.

Sisi
  • 263
  • 1
  • 2
  • 9
  • I have a nagging suspicion that your algorithm should be (very?) inefficient, but I'm certain it's incorrect: the `F(n)` will have holes in it towards the end. For instance, `F(1)` includes 5 but lacks 4. But where exactly the holes start is hard to say. – Will Ness Sep 17 '12 at 20:48
  • the classic Haskell version `hh=1:union(map(2*)hh)(union(map(3*)hh)(map(5*)hh))` gets me 100,000th Hamming number in 0.14 secs on my computer. Your version, in about 2.5 secs and I have no way to know which `n` to use so that `F(n)[100000]` is correct (140 works, but 120 doesn't). the code for your version: ``ttNext xs = map(2*)xs`union`map(3*)xs`union`map(5*)xs ; tt1 = [1] ; tt = iterate ttNext tt1 ; ff = scanl union [] tt `` (I'm using a special `union` function, linear for merging ordered lists, removing duplicates). – Will Ness Sep 17 '12 at 21:22