Rev 14 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
32 | daniel-mar | 1 | package de.viathinksoft.immortal.gen2; |
5 | daniel-mar | 2 | |
3 | import java.math.BigInteger; |
||
4 | |||
32 | daniel-mar | 5 | import de.viathinksoft.immortal.gen2.math.CoPrimeExpectedException; |
6 | import de.viathinksoft.immortal.gen2.math.MathUtils; |
||
7 | import de.viathinksoft.immortal.gen2.math.MathUtils2; |
||
5 | daniel-mar | 8 | |
9 | /** |
||
10 | * Immortable Number Generator (ING) |
||
11 | * |
||
12 | * @author Daniel Marschall |
||
13 | */ |
||
14 | |||
32 | daniel-mar | 15 | public class Immortal { |
5 | daniel-mar | 16 | |
17 | /** |
||
18 | * Calculates M5 or M6 |
||
19 | * |
||
20 | * @param base |
||
21 | * @param u |
||
22 | * @return |
||
23 | */ |
||
32 | daniel-mar | 24 | public static BigInteger M(ImmortalBase base, BigInteger u) { |
5 | daniel-mar | 25 | BigInteger p, q; |
26 | |||
32 | daniel-mar | 27 | if (base == ImmortalBase.M5) { |
5 | daniel-mar | 28 | p = BigInteger.ONE; |
29 | q = BigInteger.ZERO; |
||
32 | daniel-mar | 30 | } else if (base == ImmortalBase.M6) { |
5 | daniel-mar | 31 | p = BigInteger.ZERO; |
32 | q = BigInteger.ONE; |
||
33 | } else { |
||
34 | p = null; |
||
35 | q = null; |
||
36 | } |
||
37 | |||
38 | BigInteger a = MathUtils2.pow(new BigInteger("2"), u); |
||
39 | BigInteger b = MathUtils2.pow(new BigInteger("5"), u); |
||
40 | |||
41 | // To calculate M5: |
||
42 | // x = 2^u = a mod 1 |
||
43 | // x = 5^u = b mod 0 |
||
44 | |||
45 | // To calculate M6: |
||
46 | // x = 2^u = a mod 0 |
||
47 | // x = 5^u = b mod 1 |
||
48 | |||
49 | try { |
||
50 | return MathUtils.chineseRemainder(p, a, q, b); |
||
51 | } catch (CoPrimeExpectedException e) { |
||
52 | // Can never happen since 2^u and 5^u are always coprimes. |
||
53 | return null; |
||
54 | } |
||
55 | } |
||
56 | |||
57 | /** |
||
58 | * Gets M5(u) |
||
59 | * |
||
60 | * @param u |
||
61 | * Length of number |
||
62 | * @return |
||
63 | */ |
||
64 | public static BigInteger M5(BigInteger u) { |
||
32 | daniel-mar | 65 | return M(ImmortalBase.M5, u); |
5 | daniel-mar | 66 | } |
67 | |||
68 | /** |
||
69 | * Gets M6(u) |
||
70 | * |
||
71 | * @param u |
||
72 | * Length of number |
||
73 | * @return |
||
74 | */ |
||
75 | public static BigInteger M6(BigInteger u) { |
||
32 | daniel-mar | 76 | return M(ImmortalBase.M6, u); |
5 | daniel-mar | 77 | } |
78 | |||
79 | /** |
||
80 | * Toggles between M5 and M6 base. |
||
81 | * |
||
82 | * @param cur |
||
83 | * Number |
||
84 | * @param u |
||
85 | * Length of number (because of possible leading zeros) |
||
86 | * @return Number in opposide base. |
||
7 | daniel-mar | 87 | * @throws Exception |
5 | daniel-mar | 88 | */ |
89 | public static BigInteger toggleBase(BigInteger cur, BigInteger u) |
||
7 | daniel-mar | 90 | throws Exception { |
5 | daniel-mar | 91 | // Converts M6(u) <-> M5(u) |
92 | // M6(u) = 1 + 10^u - M5(u) |
||
93 | // M5(u) = 1 + 10^u - M6(u) |
||
94 | |||
95 | if (u.compareTo(MathUtils2.length(cur)) < 0) { |
||
96 | throw new InvalidLengthException(); |
||
97 | } |
||
98 | |||
99 | return BigInteger.ONE.add(MathUtils2.pow(BigInteger.TEN, u)).subtract(cur); |
||
100 | } |
||
101 | |||
102 | /** |
||
103 | * Toggles between M5 and M6 base. The length of the current number is |
||
104 | * assumed (and no leading zero). |
||
105 | * |
||
106 | * @param cur |
||
107 | * @return |
||
7 | daniel-mar | 108 | * @throws Exception |
5 | daniel-mar | 109 | */ |
7 | daniel-mar | 110 | public static BigInteger toggleBase(BigInteger cur) throws Exception { |
5 | daniel-mar | 111 | try { |
112 | return toggleBase(cur, MathUtils2.length(cur)); |
||
113 | } catch (InvalidLengthException e) { |
||
114 | // Should never happen |
||
115 | return null; |
||
116 | } |
||
117 | } |
||
6 | daniel-mar | 118 | |
119 | public static boolean isImmortable(BigInteger num) { |
||
120 | // Alternativ: nē%10^m == n%10^m |
||
121 | return num.pow(2).toString().endsWith(num.toString()); |
||
122 | } |
||
123 | |||
124 | public static String findNextImmortable(String num) { |
||
125 | if (!isImmortable(new BigInteger(num))) { |
||
126 | return null; |
||
127 | } |
||
128 | for (int i=1; i<=9; i++) { |
||
129 | String s = i+num; |
||
130 | if (isImmortable(new BigInteger(s))) { |
||
131 | return s; |
||
132 | } |
||
133 | } |
||
134 | return "0"+num; |
||
135 | } |
||
5 | daniel-mar | 136 | |
32 | daniel-mar | 137 | private Immortal() { |
5 | daniel-mar | 138 | } |
139 | |||
140 | } |