Guest User

Primorial 0.0.2

a guest
Apr 13th, 2019
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 8.53 KB | None | 0 0
  1. import java.math.BigInteger;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.Scanner;
  5.  
  6. public class Primorial {
  7.      static BigInteger zero = BigInteger.ZERO;
  8.      static BigInteger one = BigInteger.ONE;
  9.      static BigInteger two = BigInteger.valueOf(2);
  10.      static BigInteger five = BigInteger.valueOf(5);
  11.  
  12.     public static void main(String[] args) {
  13.         Scanner s = new Scanner(System.in);
  14.  
  15.         while (true) {
  16.             primorial(s.nextBigInteger());
  17.         }
  18.     }
  19.  
  20.      static void primorial(BigInteger c) {
  21.         BigInteger d = sqrt(c);
  22.         BigInteger e = c.subtract(d.multiply(d));
  23.         BigInteger f = two.multiply(d).add(one).subtract(e);
  24.  
  25.         Object[] Q = getPrimeSeries(d);
  26.         BigInteger[] qPrimes = (BigInteger[]) Q[0];
  27.         BigInteger q = (BigInteger) Q[1];
  28.  
  29.         BigInteger qc = q.multiply(c);
  30.         BigInteger d_qc = sqrt(qc);
  31.         BigInteger e_qc = qc.subtract(d_qc.multiply(d_qc));
  32.         BigInteger f_qc = two.multiply(d_qc).add(one).subtract(e_qc);
  33.         System.out.println("primes = " + Arrays.toString(qPrimes));
  34.         System.out.println("q = " + q);
  35.         System.out.println("qc = " + qc);
  36.         System.out.println("d_qc = " + d_qc);
  37.         System.out.println("e_qc = " + e_qc);
  38.         System.out.println("f_qc = " + f_qc);
  39.  
  40.         /** Difference */
  41.         //BigInteger difference = qc.subtract(c);
  42.         //System.out.println("(qc - c) = " + difference);
  43.  
  44.         /** Trimming the difference */
  45.         //BigInteger trimmed = difference;
  46.         //BigInteger amountTrimmed = one;
  47.         //while (isFactor(trimmed, two)) {
  48.         //    trimmed = trimmed.divide(two);
  49.         //}
  50.         //amountTrimmed = difference.divide(trimmed);
  51.  
  52.         //System.out.println("(qc - c) / " + amountTrimmed + " = " + trimmed);
  53.  
  54.         int mode = -3;
  55.         System.out.println("mode = " + mode);
  56.  
  57.         /*
  58.         0 = iterate the odd column from c with all multiples of q primes
  59.         1 = iterate the even column from c with all multiples of q primes
  60.        -1 = iterate the even column from c with only even multiples of q primes
  61.         2 = iterate the odd column from qc with all multiples of q primes
  62.         3 = iterate the even column from qc with all multiples of q primes
  63.        -3 = iterate the even column from qc with only even multiples of q primes
  64.          */
  65.  
  66.         //defaulting to mode 0
  67.          BigInteger column = getOddColumn(e, f.negate());
  68.  
  69.          switch (mode) {
  70.             default:
  71.              case 0: column = getOddColumn(e, f.negate()); break;
  72.             case -1:
  73.              case 1: column = getEvenColumn(e, f.negate()); break;
  74.             case  2: column = getOddColumn(e_qc, f_qc.negate()); break;
  75.             case -3:
  76.             case  3: column = getEvenColumn(e_qc, f_qc.negate()); break;
  77.         }
  78.  
  79.         VQCElement test;
  80.         BigInteger a;
  81.         BigInteger b;
  82.  
  83.         //iterating variables
  84.         BigInteger i;
  85.         int j;
  86.  
  87.         BigInteger qPrime;
  88.         BigInteger multiplier;
  89.  
  90.         boolean modelt0 = mode < 0;
  91.         boolean ieq1 = true;
  92.         long iterations = 0;
  93.  
  94.         solved:
  95.         for (i = one;;) {
  96.             for (j = 0; j < qPrimes.length; j++){
  97.                 iterations++;
  98.  
  99.                 qPrime = qPrimes[j];
  100.                 multiplier = i;
  101.                 test = getElement(column, one, getT(column, multiplier.multiply(qPrime)));
  102.  
  103.  
  104.                 BigInteger gcd = c.gcd(test.a);
  105.                 if (!gcd.equals(one)) {
  106.                     a = gcd;
  107.                     b = c.divide(gcd);
  108.                     break solved;
  109.                 }
  110.             }
  111.  
  112.             if (modelt0) {
  113.                 if (ieq1) {
  114.                     ieq1 = false;
  115.                     i = two;
  116.                 } else {
  117.                     i = i.add(two);
  118.                 }
  119.             } else {
  120.                 i = i.add(one);
  121.             }
  122.         }
  123.  
  124.         System.out.println();
  125.  
  126.         System.out.println("iterations = " + iterations);
  127.         System.out.println(test);
  128.         System.out.println("x = " + qPrime + " * " + multiplier);
  129.         System.out.println("c = " + a + " * " + b);
  130.  
  131.         System.out.println();
  132.     }
  133.  
  134.     /** Returns Object[]{BigInteger[] qPrimes, BigInteger q} */
  135.      static Object[] getPrimeSeries(BigInteger d) {
  136.         BigInteger q = five;
  137.  
  138.         BigInteger nextPrime = five;
  139.         ArrayList<BigInteger> primeList = new ArrayList<>();
  140.         primeList.add(q);
  141.         while (lt(q, d)) {
  142.             nextPrime = nextPrime.nextProbablePrime();
  143.  
  144.             /** End in 01 constraint */
  145.             if (nextPrime.toString(2).endsWith("01")) {
  146.                 q = q.multiply(nextPrime);
  147.                 primeList.add(nextPrime);
  148.             }
  149.         }
  150.  
  151.         BigInteger[] qPrimes = primeList.toArray(new BigInteger[0]);
  152.         return new Object[]{qPrimes, q};
  153.     }
  154.  
  155.      static VQCElement getElement(BigInteger e, BigInteger n, BigInteger t) {
  156.         VQCElement v = new VQCElement();
  157.         v.e = e;
  158.         v.n = n;
  159.         v.t = t;
  160.  
  161.         v.x = getX(e, t);
  162.  
  163.         /* define a(x) = ((x^2 + e) / (2*n)) // 1 */
  164.         v.a = (v.x.pow(2)).add(e).divide(two.multiply(v.n));
  165.  
  166.         /* define define d(x) = ((x^2 + e) / (2*n) + x) // 1 */
  167.         v.d = v.a.add(v.x);
  168.         v.f = two.multiply(v.d).add(one).subtract(v.e);
  169.         v.b = v.a.add(two.multiply(v.x)).add(two.multiply(v.n));
  170.         v.c = v.a.multiply(v.b);
  171.  
  172.         return v;
  173.     }
  174.  
  175.     static BigInteger getOddColumn(BigInteger e, BigInteger negative_f) {
  176.         if (e.and(one).equals(zero)) return negative_f;
  177.         else return e;
  178.     }
  179.  
  180.     static BigInteger getEvenColumn(BigInteger e, BigInteger negative_f) {
  181.         if (e.and(one).equals(zero)) return e;
  182.         else return negative_f;
  183.     }
  184.  
  185.      static BigInteger getX(BigInteger e, BigInteger t) {
  186.         BigInteger subtrahend = one;
  187.  
  188.         if (e.and(one).equals(zero)) {
  189.             subtrahend = two;
  190.         }
  191.  
  192.         return two.multiply(t).subtract(subtrahend);
  193.     }
  194.  
  195.      static BigInteger getT(BigInteger e, BigInteger x) {
  196.         BigInteger addend = one;
  197.  
  198.         if (e.and(one).equals(zero)) {
  199.             addend = two;
  200.         }
  201.  
  202.         return x.add(addend).divide(two);
  203.     }
  204.  
  205.      static boolean gt(BigInteger i, BigInteger i2) { return i.compareTo(i2) > 0; }
  206.      static boolean gteq(BigInteger i, BigInteger i2) { return i.compareTo(i2) >= 0; }
  207.      static boolean lt(BigInteger i, BigInteger i2) { return i.compareTo(i2) < 0; }
  208.  
  209.      static BigInteger sqrt(BigInteger n) {
  210.         if (n.equals(zero)) return zero;
  211.  
  212.         if (gt(n, zero)) {
  213.             int bitLength = n.bitLength(); //ceil(log(n, 2))
  214.             BigInteger root = one.shiftLeft(bitLength >> 1); //right-shifting by one equals dividing by two
  215.  
  216.             while (!isSqrt(n, root)) {
  217.                 root = root.add(n.divide(root));
  218.                 root = root.shiftRight(1);
  219.             }
  220.  
  221.             return root;
  222.         }
  223.  
  224.         throw new ArithmeticException("Complex result");
  225.     }
  226.  
  227.      static boolean isSqrt(BigInteger n, BigInteger root) {
  228.         BigInteger lowerBound = root.multiply(root);
  229.  
  230.         BigInteger upperBound = root.add(one).multiply(root.add(one));
  231.  
  232.         return gteq(n, lowerBound) && lt(n, upperBound);
  233.     }
  234.  
  235.     static class VQCElement {
  236.          BigInteger a;
  237.          BigInteger b;
  238.          BigInteger c;
  239.          BigInteger d;
  240.          BigInteger td; //2d
  241.          BigInteger e;
  242.          BigInteger f;
  243.          BigInteger i;
  244.          BigInteger j;
  245.          BigInteger n;
  246.          BigInteger x;
  247.          BigInteger t;
  248.  
  249.          int cm4;
  250.          int em4;
  251.  
  252.          boolean isTrivial = false;
  253.  
  254.          public VQCElement clone() {
  255.             VQCElement c = new VQCElement();
  256.             c.a = a;
  257.             c.b = b;
  258.             c.c = this.c;
  259.             c.d = d;
  260.             c.td = td;
  261.             c.e = e;
  262.             c.f = f;
  263.             c.i = i;
  264.             c.j = j;
  265.             c.n = n;
  266.             c.x = x;
  267.             c.t = t;
  268.             c.cm4 = cm4;
  269.             c.em4 = em4;
  270.             c.isTrivial = isTrivial;
  271.  
  272.             return c;
  273.         }
  274.  
  275.          String getCoordinates() {
  276.             return "(" + e + ", " + n + ", " + t + ")";
  277.         }
  278.  
  279.          String toElementString() {
  280.             return "{" + e + ":" + n + ":" + d + ":" + x + ":" + a + ":" + b + "} ";
  281.         }
  282.  
  283.          public String toString() {
  284.             return toElementString() + getCoordinates();
  285.         }
  286.     }
  287. }
Advertisement
Add Comment
Please, Sign In to add comment