/* * This file contains all the classes; it cannot be compiled like this - it * needs to be divided in single files, one for each class. * The best way to use the program is to install a free IDE, like Netbeans. */ package a166133; import java.io.*; import java.math.BigInteger; /** * @author jmason * * * * The main class is A166133. * It just invokes Runner with the number through which you want to generate the sequence. * 10 million for example. Runner opens the output files, hard-codes the first three entries 1, 2, 4, and * then iterates on the main algorithm. The algorithm consists of calculating (last term)^2 - 1, and then finding the least * factor not already in the sequence. Finding the least factor consists first of generating the prime factors, and * then all the factors, be they prime or composite. And then sorting them. Hence you discover the difference between a lazy programmer and a good one. The * lazy programmer writes his own inefficient sort algorithm. The good one spends * time to study how to use the utility sort classes offered by the java libraries. * Guess which type I am? To discover if a divisor is already in the sequence, I use the Array class. This uses * an enormous boolean array for "small" values, and a hash table for larger values. */ public class A166133 { public static void main(String[] args) throws IOException { // 23 minutes for 1 million new Runner(100); // put here the number of terms you want } } package a166133; import java.math.BigInteger; import java.util.ArrayList; import java.io.*; /** * @author jmason */ public class Runner { Array a; //PrimeList pl; public Runner(int loop) throws IOException { int line = 1; //pl = new PrimeList(); // ignore this failed performance improvment // open files FileWriter fw = new FileWriter("out.txt"); // A166133 FileWriter fw2 = new FileWriter("min.txt"); // A256405 FileWriter fw3 = new FileWriter("pos.txt"); // A256409 FileWriter fw4 = new FileWriter("hit.txt"); // A256406 // Class Array is where we know if a number is already in A166133 a = new Array(fw3); // write the first 3 lines according to sequence definition a.put(1, 1); fw.write("1 1\r\n"); fw2.write("1 2\r\n"); a.put(2, 2); fw.write("2 2\r\n"); fw2.write("2 3\r\n"); a.put(3, 4); fw.write("3 4\r\n"); fw2.write("3 3\r\n"); BigInteger value = new BigInteger("4"); // generate the rest of the sequence for (int i = 4; i <= loop ; i++) { BigInteger prev = new BigInteger(value.toString()); BigInteger bi = value.multiply(value); bi = bi.subtract(BigInteger.ONE); // bi now equal (previous ^ 2) -1 // find next value value = newValue(i, bi); // if next value is "maximal", that is, (previous ^ 2) -1 // then write out to A256406 if (value.compareTo(bi) == 0) fw4.write(line++ + " " + prev + "\r\n"); // put the value in the array a.put(i, value); // now and then, write to the console if (i % 1000 == 0) System.out.println(i + " " + value + " " + a.min); // write to A166133 fw.write(i + " " + value + "\r\n"); // write to A256405 fw2.write(i + " " + a.min + "\r\n"); // did sequence die? (probably not) if (value.compareTo(BigInteger.ZERO) == 0) break; } fw.close(); fw2.close(); fw3.close(); fw4.close(); } // 1, 2, 4, 3, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13, 21, 20, 19, 18, 17, 24, 23, 22, 69, 28, 27 // generate new value private BigInteger newValue(int n, BigInteger v) { // get sorted list of all factors, excluding 1, and including the number itself ArrayList list = new FactorList(/* pl */).get(n, v); // find lowest factor not yet in array for (int i = 0; i < list.size() ; i++) { BigInteger bi = (BigInteger)(list.get(i)); if (a.test(bi)) continue; return bi; } return BigInteger.ZERO; } } /* This class maintains an array of all values already in sequence. For speed it uses a boolean array for values up to a certain size; after that, a hash table */ package a166133; import java.math.BigInteger; import java.util.Hashtable; import java.io.*; /** * @author jmason */ public class Array { boolean array[]; int size = 500000000; // below this, use boolean array BigInteger bsize; Hashtable h; public BigInteger min; // this is the minimum number not yet in the sequence int line; FileWriter fw; public Array(FileWriter fw) { this.fw = fw; array = new boolean[size]; bsize = new BigInteger("" + size); h = new Hashtable(); min = new BigInteger("1"); } // set in the array that a number has been inserted into the sequence public void put(int n, BigInteger v) throws IOException { // if it's a big number, use the hash if (v.compareTo(bsize) >= 0) { h.put(v.toString(), v); } else // otherwise the boolean array { int i = Integer.parseInt(v.toString()); array[i] = true; } // if finally the minimum value has been inserted into the sequence, // calculate the new sequence, and write A256405 if (v.compareTo(min) == 0) { line++; fw.write(line + " " + n + "\r\n"); while (true) { min = min.add(BigInteger.ONE); if (test(min) == false) break; } } } public void put(int n, int v) throws IOException { put(n, new BigInteger("" + v)); } // test if a number is already in the sequence public boolean test(BigInteger v) { boolean ret; if (v.compareTo(bsize) >= 0) { ret = (h.get(v.toString()) != null); } else { int i = Integer.parseInt(v.toString()); ret = array[i] ; } //System.out.println("test " + v + " " + ret); return ret; } } /* return sorted factor list of a number - all factors > 1 , up to and including the numerber itself */ package a166133; import java.math.BigInteger; import java.util.ArrayList; /** * @author jmason */ public class FactorList { //PrimeList pl; public FactorList(/*PrimeList pl*/) { /*this.pl = pl;*/ } public ArrayList get(int n, BigInteger v) { ArrayList list = new ArrayList(); // get the prime factors ArrayList pf = new PrimeFactorList(/*pl*/).get(v); // generate all factors for (int i = 0 ; i < pf.size() ; i++) { int actual = list.size(); BigInteger bi = (BigInteger)(pf.get(i)); if (!isin(list, bi)) list.add(bi); for (int j = 0 ; j < actual ; j++) { BigInteger p = (BigInteger)(list.get(j)); try { BigInteger m = p.multiply(bi); if (!isin(list, m)) list.add(m); } catch (Exception e) { System.err.println("v= " + v); System.err.println("p= " + p); System.err.println("bi= " + bi); throw e; } } } // and sort them list = sort(list); return list; } // if factor already in list boolean isin(ArrayList list, BigInteger bi) { for (int i = 0 ; i < list.size() ; i++) { BigInteger p = (BigInteger)(list.get(i)); if (p.compareTo(bi) == 0) return true; } return false; } // rather inefficient sort ArrayList sort(ArrayList list) { ArrayList out = new ArrayList(); BigInteger start = new BigInteger("1"); while (true) { BigInteger curr = null; for (int i = 0 ; i < list.size() ; i++) { BigInteger bi = (BigInteger)(list.get(i)); if (bi.compareTo(start) > 0) { if (curr == null) curr = bi; else if (bi.compareTo(curr) < 0) curr = bi; } } if (curr == null) break; start = curr; out.add(curr); } return out; } } /* generate the prime factors of the input number; better not to call it for 1; returns the numer itself, if prime */ package a166133; import java.math.BigInteger; import java.util.ArrayList; /** * * @author jmason */ public class PrimeFactorList { //PrimeList pl; public PrimeFactorList(/* PrimeList pl */) { /*this.pl = pl; */ } public ArrayList get(BigInteger target) { //System.out.println("PFList " + target); ArrayList list = new ArrayList(); BigInteger v = new BigInteger(target.toString()); while (true) { BigInteger min = minPF(v); //System.out.println("minPF " + v + " = " + min); list.add(min); v = v.divide(min); if (v.compareTo(BigInteger.ONE) == 0) break; } /* String s = "PFList of " + target + " is "; for (int i = 0 ; i < list.size() ; i++) s += (BigInteger)(list.get(i)) + " "; System.out.println(s); */ return list; } // find minimum prime factor of input public BigInteger minPF(BigInteger target) { BigInteger delta = new BigInteger("1"); int n = 0; /* this performance improvement didn't for (Prime p = pl.getFirst(); (p.getValue().multiply(p.getValue())).compareTo(target) <= 0; p = pl.getNext(p) ) */ for (BigInteger bi = new BigInteger("2"); (bi.multiply(bi)).compareTo(target) <= 0; bi = bi.add(delta) ) { //BigInteger bi = p.getValue(); if (target.mod(bi).compareTo(BigInteger.ZERO) == 0) { return bi; } n++; if (n == 2) delta = new BigInteger("2"); } //System.out.println("PFList " + target); return target; } }