// Return true if an integer is isPrime
boolean isPrime(int n) {
return IntStream
.range(2, n)
.noneMatch(x -> n % x == 0);
}
// Return a stream of integers of all the factors of an integer
IntStream factors(int x) {
return IntStream
.rangeClosed(2, x)
.filter(d -> x % d == 0);
}
// Return a stream of integers of all the prime factors of an integer
IntStream primeFactorsOf(int x) {
return factors(x)
.filter(d -> isPrime(d));
}
// Get the count of all the prime factors of each integer from 1 to n
LongStream omega(int n) {
return IntStream
.rangeClosed(1, n)
.mapToLong(x -> primeFactorsOf(x).count());
}
omega(10).toArray();
/exit
// Use BigInteger class to avoid overflow
// A pair to store 2 elements
class Pair<T, U> {
T first;
U second;
Pair(T first, U second) {
this.first = first;
this.second= second;
}
}
// 0 1
// 1 1
// 1 2
// 2 3
// 3 5
// 5 8
// 8 13
// ...
Stream<BigInteger> fibonacci(int n) {
return Stream.iterate(
new Pair<>(BigInteger.ZERO, BigInteger.ONE), pr -> new Pair<>(pr.second, pr.first.add(pr.second)))
.map(pr -> pr.second).limit(n);
}
fibonacci(5).toArray(BigInteger[]::new);
fibonacci(48).toArray(BigInteger[]::new);
/exit
/**
* n = 3
* k = 2
* 1 * 1 + 1 * 1 = 2
* fibs = 1, 1, 2
*
* n = 4, n = 5
* k = 3
* 1 * 1 + 2 * 1 = 3
* 1 * 1 * 2 * 2 = 5
* fibs = 1, 1, 2, 3, 5
*
* n = 6
* k = 5
* 3 * 1 + 5 * 1 = 8
* 3 * 1 + 5 * 2 = 13
* 3 * 2 + 5 * 3 = 21
* fibs = 1, 1, 2, 3, 5, 8, 13, 21
*
* f5 = f3 + f4 = 1 * f3 + 1 * f4 = f1 * f3 + f2 * f4
* f6 = f4 + f5 = 1 * f3 + 2 * f4 = f2 * f3 + f3 * f4
* f7 = f6 + f7 = 2 * f3 + 3 * f4 = f3 * f3 + f4 * f4
*/
import java.time.Instant;
import java.time.Duration;
List<BigInteger> generateFib(List<BigInteger> fibs) {
List<BigInteger> list = new ArrayList<>(fibs);
int k = list.size();
list.addAll(Stream.
iterate(0, i -> i < k - 1, i -> i + 1).
parallel().
map(i -> fibs.get(k - 2).
multiply(fibs.get(i)).
add(fibs.get(k - 1).
multiply(fibs.get(i+1))
)
).
collect(Collectors.toList()));
return list;
}
BigInteger findFibTerm(int n) {
List<BigInteger> fibList = new ArrayList<>();
fibList.add(BigInteger.ONE);
fibList.add(BigInteger.ONE);
Instant start = Instant.now();
while (fibList.size() < n) {
fibList = generateFib(fibList);
}
Instant stop = Instant.now();
System.out.println(Duration.between(start, stop).toMillis() + "ms");
return fibList.get(n - 1);
}
findFibTerm(50000);
/exit