-
Notifications
You must be signed in to change notification settings - Fork 6
/
A054657.java
48 lines (40 loc) · 1.37 KB
/
A054657.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package irvine.oeis.a054;
import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;
import irvine.factor.factor.Jaguar;
import irvine.math.z.Z;
import irvine.oeis.Sequence1;
/**
* A054657 Number of leaves on the rooted tree of height n constructed by the following rule. Assign weight 1 to the single node at height 1. At each node of weight w at height k>0, branch to nodes at height k+1 as follows: one node of weight 1 and a node of weight d+1 if d divides w.
* @author Sean A. Irvine
*/
public class A054657 extends Sequence1 {
// It is only necessary to keep track of the number of nodes with a particular weight.
private Map<Z, Z> mTree = null;
private void add(final TreeMap<Z, Z> t, final Z key, final Z value) {
final Z v = t.get(key);
t.put(key, v == null ? value : v.add(value));
}
@Override
public Z next() {
if (mTree == null) {
mTree = Collections.singletonMap(Z.ONE, Z.ONE);
} else {
final TreeMap<Z, Z> t = new TreeMap<>();
for (final Map.Entry<Z, Z> e : mTree.entrySet()) {
final Z m = e.getValue();
add(t, Z.ONE, m);
for (final Z d : Jaguar.factor(e.getKey()).divisors()) {
add(t, d.add(1), m);
}
}
mTree = t;
}
Z res = Z.ZERO;
for (final Z multiplicity : mTree.values()) {
res = res.add(multiplicity);
}
return res;
}
}