/
A025282.java
69 lines (65 loc) · 1.93 KB
/
A025282.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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package irvine.oeis.a025;
import irvine.factor.factor.Jaguar;
import irvine.math.z.Z;
import irvine.oeis.Sequence1;
import irvine.util.array.LongDynamicByteArray;
import irvine.util.string.StringUtils;
/**
* A025282 Smallest number requiring n Fibonacci numbers to build using + and *.
* @author Sean A. Irvine
*/
public class A025282 extends Sequence1 {
private final boolean mVerbose = "true".equals(System.getProperty("oeis.verbose"));
private final LongDynamicByteArray mComplexity = new LongDynamicByteArray();
private byte mN = 0;
private long mM = 0;
private long mA = 1;
private long mB = 1;
@Override
public Z next() {
++mN;
while (true) {
++mM;
long min = mM - 1; // add 1 together mM times
if (mM == mB) {
// Matches the next Fibonacci number, hence requires only 1 number
min = 1;
final long t = mA + mB;
mA = mB;
mB = t;
assert mB > mM;
} else {
// Deal with addition
for (long a = 1, b = 1, t; b < mM; t = a + b, a = b, b = t) {
final long c = 1 + mComplexity.get(mM - b);
if (c < min) {
min = c;
}
}
// Deal with multiplication
for (final Z dd : Jaguar.factor(mM).divisors()) {
final long d = dd.longValue();
if (d != 1 && d <= mM / d) {
final long c = mComplexity.get(d) + mComplexity.get(mM / d);
if (c < min) {
min = c;
}
}
}
}
if (min > 127) {
throw new UnsupportedOperationException();
}
mComplexity.set(mM, (byte) min);
if (mVerbose && (mM & 0xFFFFF) == 0) {
StringUtils.message("m=" + mM + " -> " + min);
}
if (min >= mN) {
if (min > mN) {
StringUtils.message("Warning " + mM + " actually required more than " + mN + " numbers, please report this");
}
return Z.valueOf(mM);
}
}
}
}