Primititive/src/kezvh/primitive/Primitive.java

   1 /**
   2  *
   3  */
   4 package kezvh.primitive;
   5
   6 import java.math.BigInteger;
   7 import java.util.Arrays;
   8 import java.util.HashMap;
   9 import java.util.Iterator;
  10 import java.util.LinkedList;
  11 import java.util.List;
  12 import java.util.Map;
  13 import java.util.Random;
  14
  15 /**
  16  * @author afflux
  17  *
  18  */
  19 public class Primitive {
  20     private static LinkedList<BigInteger> pfacts = new LinkedList<BigInteger>();
  21     private static LinkedList<BigInteger> primes = new LinkedList<BigInteger>();
  22
  23     private static enum Case {
  24         FACTORIAL, PRIMORIAL, EXPONENTIAL
  25     }
  26
  27     private static final Case type = Case.PRIMORIAL;
  28
  29     private static final BigInteger increment(final BigInteger i) {
  30         switch (Primitive.type) {
  31             case FACTORIAL:
  32                 return i.add(BigInteger.ONE);
  33             case PRIMORIAL:
  34                 return i.nextProbablePrime();
  35             case EXPONENTIAL:
  36                 return i.add(i);
  37             default:
  38                 throw new RuntimeException();
  39         }
  40     }
  41
  42     static {
  43         final BigInteger max = new BigInteger("5000");
  44
  45         for (BigInteger cpf = BigInteger.valueOf(2), i = BigInteger.valueOf(2); i.compareTo(max) < 0; i = Primitive.increment(i), cpf = cpf.multiply(i)) {
  46             Primitive.pfacts.addFirst(cpf);
  47             Primitive.primes.addFirst(i);
  48         }
  49
  50         System.out.println("number of pfacts: " + Primitive.pfacts.size());
  51         System.out.println("bits in largest element: " + Primitive.primes.getFirst().toString(2).length());
  52         System.out.println("bits in largest pfact: " + Primitive.pfacts.getFirst().toString(2).length());
  53     }
  54
  55     private static Map<Integer, Character> rad = new HashMap<Integer, Character>() {
  56         {
  57             final char[] chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz`~!@#$%^&*()-_=+[{]}\\|;:'\",<.>/?".toCharArray();
  58             for (int i = 0; i < chars[i]; i++)
  59                 this.put(i, chars[i]);
  60         }
  61     };
  62
  63     /**
  64      * @param args x
  65      */
  66     public static void main(final String... args) {
  67         Primitive.six();
  68     }
  69
  70     /**
  71      *
  72      */
  73     public static void two() {
  74         //        final Random r = new Random(0);
  75         BigInteger foo = new BigInteger("1").nextProbablePrime(); // 686
  76         for (int i = 0; i < 100; i++) {
  77             System.out.println(Primitive.format(foo));
  78             foo = foo.nextProbablePrime(); // 686
  79         }
  80         System.out.println(Primitive.format(foo));
  81     }
  82
  83     /**
  84      *
  85      */
  86     public static void zero() {
  87         final Random r = new Random();
  88         System.out.println(Primitive.format(new BigInteger(500, r).nextProbablePrime())); // .nextProbablePrime()
  89     }
  90
  91     /**
  92      *
  93      */
  94     public static void pointFive() {
  95         //        final Random r = new Random();
  96         //        BigInteger baz = new BigInteger(70, r).nextProbablePrime();
  97         BigInteger baz = new BigInteger("1107336284477113445057");
  98         System.out.println(baz.bitLength());
  99         final LinkedList<BigInteger> dfs = Primitive.dfs(baz);
 100         if (dfs == null) {
 101             System.out.println("null...");
 102             return;
 103         }
 104         final Iterator<BigInteger> i = dfs.descendingIterator();
 105         i.next();
 106         while (i.hasNext()) {
 107             final BigInteger next = i.next();
 108             final BigInteger fact = baz.subtract(next);
 109             final int o = Primitive.pfacts.indexOf(fact);
 110             if (o == -1)
 111                 throw new RuntimeException(fact + " is not a factorial...? next = " + next + ", baz = " + baz);
 112             System.out.println(baz + " - " + (Primitive.pfacts.size() - o + 1) + "! = " + next);
 113             baz = next;
 114         }
 115         System.out.println(dfs);
 116     }
 117
 118     /**
 119      *
 120      */
 121     public static void three() {
 122         System.out.println(Primitive.format(Primitive.pfacts.get(100).nextProbablePrime()));
 123
 124         System.out.println(Primitive.format(Primitive.pfacts.get(99).nextProbablePrime()));
 125
 126         System.out.println(Primitive.format(Primitive.pfacts.get(98).nextProbablePrime()));
 127     }
 128
 129     /**
 130      *
 131      */
 132     public static void one() {
 133         final Random r = new Random();
 134         //        final BigInteger foo = new BigInteger("59");
 135         final BigInteger bar = new BigInteger(80, r).nextProbablePrime();
 136         final BigInteger foo = new BigInteger(80, r).nextProbablePrime();
 137         //        final BigInteger bar = new BigInteger("509");
 138         final BigInteger baz = foo.multiply(bar);
 139         System.out.println(baz.toString(2).length());
 140
 141         //        System.out.print(foo + ": ");
 142         //        System.out.println(Primitive.format(foo));
 143         //        System.out.print(bar + ": ");
 144         //        System.out.println(Primitive.format(bar));
 145         System.out.println(baz + ": ");
 146         System.out.println(Primitive.format(baz));
 147     }
 148
 149     /**
 150      *
 151      */
 152     public static void four() {
 153         final Random r = new Random(System.nanoTime() + System.currentTimeMillis());
 154
 155         int j = 0;
 156         int i = 0;
 157         for (i = 0; i < 100; i++) {
 158             final BigInteger baz = new BigInteger(70, r).nextProbablePrime();
 159             final List<BigInteger> dfs = Primitive.dfs(baz);
 160             if (dfs != null)
 161                 j++;
 162         }
 163
 164         System.out.println(j + " / " + i);
 165         //        System.out.println(baz);
 166         //        if (dfs != null)
 167         //            System.out.println(dfs);
 168         //        else
 169         //            System.out.println("not");
 170     }
 171
 172     /**
 173      *
 174      */
 175     public static void five() {
 176         BigInteger bucket = BigInteger.valueOf(4);
 177         int bits = 2;
 178         int counts = 0, hits = 0;
 179         for (BigInteger i = BigInteger.valueOf(3); true; i = i.nextProbablePrime()) {
 180             if (i.compareTo(bucket) >= 0) {
 181                 System.out.println(bits + ": " + hits + " / " + counts + " = " + (double) hits / counts);
 182                 bucket = bucket.shiftLeft(1);
 183                 hits = counts = 0;
 184                 bits++;
 185             }
 186             counts++;
 187             if (Primitive.hasPropertyOfDifference(i))
 188                 hits++;
 189         }
 190     }
 191
 192     /**
 193      *
 194      */
 195     public static void six() {
 196         final Random r = new Random();
 197         for (int i = 100; i < 101; i++) {
 198             int hits = 0;
 199             for (int j = 0; j < 100; j++) {
 200                 final BigInteger bi = new BigInteger(10 * i, r).nextProbablePrime();
 201                 if (Primitive.hasPropertyOfDifference(bi))
 202                     hits++;
 203             }
 204             System.out.println(i * 10 + ": " + hits + " / " + 100);
 205         }
 206     }
 207
 208     /**
 209      *
 210      */
 211     public static void seven() {
 212         final Random r = new Random();
 213         final BigInteger bi = new BigInteger(100, r).nextProbablePrime();
 214         final int[] partsb = Primitive.moogle2(bi);
 215
 216         for (int i = 1; i < partsb.length; i++) {
 217             final int tmp = partsb[i];
 218             partsb[i] = 0;
 219             final BigInteger pp = Primitive.unmoogle(partsb);
 220             if (pp.isProbablePrime(100))
 221                 System.out.println(i);
 222             partsb[i] = tmp;
 223         }
 224
 225         System.out.println("done");
 226     }
 227
 228     /**
 229      *
 230      */
 231     public static void eight() {
 232         final Random r = new Random();
 233         final BigInteger bi = new BigInteger(200, r).nextProbablePrime();
 234         final int[] partsb = Primitive.moogle2(bi);
 235         System.out.println(bi);
 236         System.out.println(Arrays.toString(partsb));
 237         final List<BigInteger> hmm = Primitive.reach(partsb);
 238         System.out.println(hmm);
 239
 240     }
 241
 242     /**
 243      *
 244      */
 245     public static void nine() {
 246         final Random r = new Random();
 247         final BigInteger bi1 = new BigInteger(501, r).nextProbablePrime();
 248         final BigInteger bi2 = new BigInteger(501, r).nextProbablePrime();
 249         final BigInteger bi = bi1.multiply(bi2);
 250         final BigInteger bi3 = Primitive.squareRoot(bi);
 251         System.out.println(bi);
 252         System.out.println(bi3.multiply(bi3));
 253         System.out.println(bi3.bitLength());
 254
 255     }
 256
 257     private static BigInteger squareRoot(final BigInteger bi) {
 258         final BigInteger two = BigInteger.valueOf(2);
 259         final BigInteger n = bi;
 260         BigInteger i = BigInteger.ONE;
 261         BigInteger g;
 262         do {
 263             g = i;
 264             final BigInteger f = n.divide(g);
 265             final BigInteger h = f.add(g);
 266             i = h.divide(two);
 267         } while (!g.subtract(i).equals(BigInteger.ZERO));
 268         return g;
 269     }
 270
 271     private static List<BigInteger> reach(final int[] partsb) {
 272
 273         for (int i = 0; i < partsb.length - 1; i++) {
 274             if (partsb[i] == 0)
 275                 continue;
 276             final int tmp = partsb[i];
 277             while (partsb[i] > 0) {
 278                 partsb[i]--;
 279                 final BigInteger pp = Primitive.unmoogle(partsb);
 280                 if (BigInteger.ONE.equals(pp))
 281                     return new LinkedList<BigInteger>() {
 282                         {
 283                             this.add(BigInteger.ONE);
 284                         }
 285                     };
 286
 287                 if (pp.isProbablePrime(100)) {
 288                     final List<BigInteger> maybe = Primitive.reach(partsb);
 289                     if (maybe != null) {
 290                         maybe.add(pp);
 291                         return maybe;
 292                     }
 293                 }
 294             }
 295             partsb[i] = tmp;
 296         }
 297         return null;
 298     }
 299
 300     private static int[] moogle2(final BigInteger bi) {
 301         BigInteger divisor = bi.add(BigInteger.ZERO);
 302
 303         final int[] values = new int[Primitive.primes.size()];
 304         int j = 0;
 305         final Iterator<BigInteger> i = Primitive.primes.descendingIterator();
 306         while (i.hasNext()) {
 307             final BigInteger prime = i.next();
 308             final BigInteger[] divs = divisor.divideAndRemainder(prime);
 309             values[j] = divs[1].intValue();
 310             divisor = divs[0];
 311             j++;
 312         }
 313
 314         int x = values.length - 1;
 315         while (values[x] == 0)
 316             x--;
 317
 318         final int[] values2 = new int[x + 1];
 319         for (int y = 0; x >= 0; y++, x--)
 320             values2[y] = values[x];
 321
 322         return values2;
 323     }
 324
 325     private static BigInteger unmoogle(final int[] remainders) {
 326         BigInteger sum = BigInteger.valueOf(remainders[remainders.length - 1]);
 327         final Iterator<BigInteger> i = Primitive.pfacts.descendingIterator();
 328         for (int j = remainders.length - 2; j >= 0; j--) {
 329             final BigInteger pfact = i.next();
 330             sum = sum.add(pfact.multiply(BigInteger.valueOf(remainders[j])));
 331         }
 332         return sum;
 333     }
 334
 335     private static boolean hasPropertyOfDifference(final BigInteger bi) {
 336         final Iterator<BigInteger> i = Primitive.pfacts.descendingIterator();
 337         while (i.hasNext()) {
 338             final BigInteger n = i.next();
 339             if (n.compareTo(bi) >= 0)
 340                 return false;
 341             if (bi.subtract(n).isProbablePrime(100))
 342                 return true;
 343         }
 344         throw new RuntimeException();
 345     }
 346
 347     /**
 348      * @param bi
 349      * @return x
 350      */
 351     public static String format(final BigInteger bi) {
 352         return Primitive.format(bi, " ");
 353     }
 354
 355     /**
 356      *
 357      */
 358     public static final BigInteger THREE = BigInteger.valueOf(3);
 359
 360     private static LinkedList<BigInteger> dfs(final BigInteger b) {
 361         final Iterator<BigInteger> i = Primitive.pfacts.descendingIterator();
 362         while (i.hasNext()) {
 363             final BigInteger pfact = i.next();
 364             //        for (int i = 0; i < Primitive.pfacts.size(); i++) {
 365             //            final BigInteger pfact = Primitive.pfacts.get(Primitive.pfacts.size() - i - 1);
 366             if (b.compareTo(pfact) < 0)
 367                 continue;
 368
 369             final BigInteger next = b.subtract(pfact);
 370             if (next.equals(BigInteger.ONE))
 371                 return new LinkedList<BigInteger>() {
 372                     {
 373                         this.add(BigInteger.ONE);
 374                         this.add(b);
 375                     }
 376                 };
 377             if (next.isProbablePrime(100)) {
 378                 final LinkedList<BigInteger> possible = Primitive.dfs(next);
 379                 if (possible != null) {
 380                     possible.add(b);
 381                     return possible;
 382                 }
 383             }
 384         }
 385         return null;
 386     }
 387
 388     /**
 389      * @param bi
 390      * @param delim
 391      * @return dogs
 392      */
 393     public static String format(final BigInteger bi, final String delim) {
 394         BigInteger current = bi.abs();
 395         final StringBuilder sb = new StringBuilder();
 396
 397         boolean hasvalues = false;
 398         int i = Primitive.pfacts.size() + 1;
 399         if (!"".equals(delim))
 400             System.out.println("original is " + bi.isProbablePrime(100));
 401         for (final BigInteger pfact: Primitive.pfacts) {
 402             i--;
 403             int x = 0;
 404             while (current.compareTo(pfact) >= 0) {
 405                 x++;
 406                 current = current.subtract(pfact);
 407             }
 408             if (x != 0)
 409                 hasvalues = true;
 410             if (hasvalues) {
 411                 if (!"".equals(delim)) {
 412                     final List<Integer> haszx = new LinkedList<Integer>();
 413                     final List<Integer> haszm = new LinkedList<Integer>();
 414
 415                     for (int o = 1; o <= i + 1; o++)
 416                         if (current.subtract(Primitive.pfacts.get(Primitive.pfacts.size() - o)).isProbablePrime(100))
 417                             haszx.add(0, o);
 418
 419                     BigInteger blargh = current.abs();
 420                     //                    System.out.println(Primitive.primes.get(Primitive.pfacts.size() - i).intValue());
 421                     //                    System.out.println(pfact + " " + Primitive.primes.get(Primitive.pfacts.size() - i));
 422                     for (int q = 0; q <= Primitive.primes.get(Primitive.pfacts.size() - i).intValue(); q++) {
 423                         if (blargh.isProbablePrime(100))
 424                             haszm.add(q);
 425                         if (!blargh.equals(bi) && !"".equals(delim) && !BigInteger.ONE.equals(blargh) && !BigInteger.ZERO.equals(blargh) && BigInteger.ZERO.equals(bi.remainder(blargh)))
 426                             System.out.println("= " + blargh + " * " + bi.divide(blargh));
 427                         blargh = blargh.add(pfact);
 428                     }
 429                     System.out.println(haszm);
 430                     System.out.println(haszx);
 431                     System.out.println("- " + x + " * p" + i + "# is " + current.isProbablePrime(100));
 432                 }
 433                 if (Primitive.rad.containsKey(x))
 434                     sb.append(Primitive.rad.get(x) + delim);
 435                 else
 436                     sb.append(Primitive.format(BigInteger.valueOf(x), "") + delim);
 437             }
 438
 439         }
 440         sb.append(Primitive.rad.get(current.intValue()));
 441         return sb.toString();
 442     }
 443 }