Lazy Sequence: Collatz
Problem
Starting from n, the next number is n/2 when n is even and 3n+1 when n is odd. Print the sequence from n until it reaches 1 (1 is printed too), separated by spaces. Build it as a lazy sequence: describe how to get the next number, and take values only until 1 appears (Stream.iterate with takeWhile in Java, a generator in JavaScript, TypeScript and Python).
Constraints
- 1 <= n <= 10000
Examples
Input
6
Output
6 3 10 5 16 8 4 2 1
Solutions
A lazy sequence stores the rule, not the values. This is why it can describe an endless sequence and we still take only what we need. It is believed (but not proven) that every start reaches 1.
/*
* Problem : Collatz sequence.
* Input : One integer n.
* Output : The sequence.
* Approach: Lazy generator.
* Time : O(length)
* Space : O(length)
* Java : 9 or newer.
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.*;
import java.util.stream.*;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static int[] solve(long n) {
// Step 1: Stream.iterate describes an endless sequence. Nothing is computed until we ask for values.
// Step 2: takeWhile stops the stream before the first 1. We add the final 1 ourselves.
java.util.List<Integer> values = new java.util.ArrayList<>(
java.util.stream.Stream.iterate((int) n, value -> value % 2 == 0 ? value / 2 : 3 * value + 1)
.takeWhile(value -> value != 1)
.collect(java.util.stream.Collectors.toList()));
values.add(1);
int[] result = new int[values.size()];
for (int i = 0; i < result.length; i++) {
result[i] = values.get(i);
}
return result;
}
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
System.out.println(Arrays.stream(solve(n)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
}
}
Hints (1)
- Why can an endless stream be used safely here?