2

So I have to implement a function avalanche :: [Integer] that returns a sorted, infinite list of the hamming sequence in Haskell.

  • This sequence is defined as: n = 3^i ∗ 5^j ∗ 7^k for i, j, k > 0

  • Or with pretty Latex: enter image description here

I'm still very new to Haskell and have tried multiple things with the iterate function, like:

avalanche = sort ((iterate (\x -> 3 ^ x) 1) ++ (iterate (\x -> 5 ^ x) 1) ++ (iterate (\x -> 7 ^ x) 1))

Which doesn't work, cause it only returns the numbers for (i = j = k) > 0.

How can I write a function which uses different permutations and starts at 0?

Some expected sample-output:

ghci> take 10 avalanche
[1,3,5,7,9,15,21,25,27,35]

EDIT:

I'm unable to find an algorithm that predicts the right in-/decrementation of i, j, and k, as they seem to grow and shrink in no concise pattern.

//       n                          i j k
//       01     3^0 * 5^0 * 7^0     0 0 0
//       03     3^1 * 5^0 * 7^0     1 0 0
//       05     3^0 * 5^1 * 7^0     0 1 0
//       07     3^0 * 5^0 * 7^1     0 0 1
//       09     3^2 * 5^0 * 7^0     2 0 0
//       15     3^1 * 5^1 * 7^0     1 1 0
//       21     3^1 * 5^0 * 7^1     1 0 1
//       25     3^0 * 5^2 * 7^0     0 2 0
//       27     3^3 * 5^0 * 7^0     3 0 0
//       35     3^0 * 5^1 * 7^1     0 1 1
//       45     3^0 * 5^1 * 7^1     0 1 1
//       49     3^0 * 5^0 * 7^2     0 0 2
  • Have you tried with a list comprehension? – jub0bs Dec 07 '21 at 12:04
  • No, I just had to google that. Never heard of it. Does it work like an Input Stream? –  Dec 07 '21 at 12:07
  • I think the first step is trying to figure out an algorithm to solve the problem and ignoring which specific language you are solving it in. How would you start calculating this sequence with pen and paper? How do you calculate the first avalanche number? And the second? How can you make sure there's no avalanche number between those? – Hjulle Dec 07 '21 at 12:30
  • 2
    More things to think about: How can you ensure the list is in order? You can't sort an infinite list, since that takes infinite time (even to get the first element). What constraints do you have on `i, j, k` for a specific `n`? – Hjulle Dec 07 '21 at 12:33
  • If I cant sort afterwards, I'd have to guess the order in which i, j and k change. I dont want to bruteforce this, but cannot see any pattern in this. –  Dec 07 '21 at 13:11
  • Dou you want filter numbers n from [1..] which comply n mod 3 == 0 and n mod 5 == 0 and n mod 7 == 0? – David Lukas Dec 07 '21 at 13:17
  • @DavidLukas, No I dont want that. I wrote down some examples for the first avalanche Numbers. Your formula doesnt apply to them. –  Dec 07 '21 at 13:23
  • @xtay2 Sorry. According your edit you filter n [1..]. Now I wonder the filter criteria. – David Lukas Dec 07 '21 at 13:37
  • Please don't tag questions with `[java]` unless they are **about** Java. – Stephen C Dec 07 '21 at 13:44
  • @DavidLukas that's one possible approach, but will be exponential in _n_ numbers produced. linear algorithms exist. – Will Ness Dec 07 '21 at 14:14
  • your "brute force" gives a whole new meaning to the words "brute force", reminds me of this primes finder `[ n | n <- [2..], not $ elem n [ j*k | j <- [2..n-1], k <- [2..n-1]]]` someone posted on SO in C once (IIRC). – Will Ness Dec 07 '21 at 14:22
  • @Will Ness. Thank you for your help and advice –  Dec 07 '21 at 14:31
  • I'm not done. :) – Will Ness Dec 07 '21 at 14:31
  • `> take 20 $ iterate (\x -> 3 ^ x) 1` produces `[1,3,27,7625597484987,` and here it freezes. so this is not the list of the first 20 powers of 3. can you make a _(very)_ small change to this piece of code so it does produce them correctly? – Will Ness Dec 07 '21 at 14:45
  • I'm trying to help you here. awaiting your response. – Will Ness Dec 07 '21 at 15:15
  • I'm done, thanks to the duplicate and an article on StackExchange: -https://cs.stackexchange.com/questions/39689/how-can-i-generate-first-n-elements-of-the-sequence-3i-5j-7k –  Dec 07 '21 at 15:17
  • I was trying to help but you weren't interested, I guess. – Will Ness Dec 07 '21 at 15:46
  • Bro, writing stuff like: "Just google something, youll figure it out eventually" or "I could help you, but that is no fun" is the exact way of saying: "I dont want to help you, but hey, I could, so that means I'm smarter." Sorry, but thats neither the answer not an explanation I was looking for. –  Dec 07 '21 at 15:53
  • I wrote nothing of the sorts. there's a comment of mine missing. I guess you've flagged it as unfriendly, which it was nothing of the kind. quite the opposite. ("no fun" was meant, "no fun for _you_") but if all you wanted was to get a code to copy, you're right, I did not want to do _that._ I consider _that_ rather unhelpful. – Will Ness Dec 07 '21 at 16:05
  • BTW your Java code has a problem. in particular it won't produce `3^10`, which should be included in the output if you change `generate(40)` to e.g. `generate(6000)`. – Will Ness Dec 07 '21 at 16:25

0 Answers0