My solutions to 28 problems from Project Euler, written over four days. Click Run to see a solution’s output and running time, or . Problem statements are shortened; the links go to the full problems on projecteuler.net (CC BY-NC-SA 4.0).
import java.io.*;
import java.util.StringTokenizer;
import java.math.BigInteger;
/**
* Created by mihailod, 24.05.2008., 00.33.16
*/
public class PrimeNumbers {
private static final int N = 78498;
public static final int[] PRIMES64 = new int[N];
public static final BigInteger[] PRIMES = new BigInteger[N];
public static void init() {
}
static {
final long start = System.currentTimeMillis();
try {
final BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("primes.txt")));
final String line = br.readLine();
final StringTokenizer st = new StringTokenizer(line, ", ");
int i=0;
while(st.hasMoreTokens()) {
final String token = st.nextToken();
PRIMES64[i] = Integer.parseInt(token);
PRIMES[i] = new BigInteger(token);
i++;
}
} catch(Exception e) {
e.printStackTrace();
}
final long ms = System.currentTimeMillis() - start;
System.out.println(N + " primes initialized in " + ms + "ms");
}
}
import java.math.BigInteger;
/**
* Created by mihailod, 24.05.2008., 11.20.02
*/
public class PrimeTest {
private static BigInteger ZERO = BigInteger.ZERO;
private static BigInteger ONE = BigInteger.ONE;
private static BigInteger TWO = ONE.add(ONE);
private static BigInteger SIX = TWO.add(TWO).add(TWO);
private static BigInteger MILLION = new BigInteger("1000000");
public static boolean isPrimeSuperNaive(final long n) {
for(final int p : PrimeNumbers.PRIMES64) {
if(n % p == 0) {
//Util.p("\n" + n + " is not prime!");
//Util.p("divide it by precomputed " + p + " and you get " + dr[0] + " and remainder " + dr[1]);
return false;
}
}
return true;
}
public static boolean isPrimeNaive(final BigInteger n) {
long start = System.currentTimeMillis();
/*for(final BigInteger p : PrimeNumbers.PRIMES) {
final BigInteger dr[] = n.divideAndRemainder(p);
if(dr[1].compareTo(ZERO) == 0 && n.compareTo(p) != 0) {
//Util.p("\n" + n + " is not prime!");
//Util.p("divide it by precomputed " + p + " and you get " + dr[0] + " and remainder " + dr[1]);
return false;
}
}*/
//Util.p("Sanity check took " + Util.msToReadableTime(System.currentTimeMillis() - start));
start = System.currentTimeMillis();
float percentPrev = 0;
float percent;
long msPrev = start;
long ms;
final BigInteger sqrt = TWO.pow(n.bitLength() / 2);
BigInteger feedbackGranularity = MILLION; // try this first, increase if too small
BigInteger firstToTest = new BigInteger((PrimeNumbers.PRIMES[PrimeNumbers.PRIMES.length - 1].add(TWO)).toString());
BigInteger k = firstToTest.divide(SIX);
for(;;) {
if(k.compareTo(sqrt) > 0) {
break;
}
final BigInteger prev = k.subtract(ONE);
final BigInteger next = prev.add(TWO);
BigInteger[] dr = n.divideAndRemainder(prev);
if(dr[1].compareTo(ZERO) == 0) {
//Util.p("\n" + n + " is not prime!");
//Util.p("divide it by " + prev + " and you get " + dr[0] + " and remainder " + dr[1]);
return false;
}
dr = n.divideAndRemainder(next);
if(dr[1].compareTo(ZERO) == 0) {
//Util.p("\n" + n + " is not prime!");
//Util.p("divide it by " + prev + " and you get " + dr[0] + " and remainder " + dr[1]);
return false;
}
k = k.add(SIX);
if(k.divideAndRemainder(feedbackGranularity)[1].intValue() < SIX.intValue()) {
percent = k.floatValue() * 100 / sqrt.floatValue();
ms = System.currentTimeMillis();
final double msDiff = System.currentTimeMillis() - msPrev;
// let's estimate time remaining
final double percentDiff = percent - percentPrev;
final boolean estimateOK;
if(percentDiff < 0.1) {
estimateOK = false;
feedbackGranularity = feedbackGranularity.multiply(TWO);
} else {
estimateOK = true;
}
if(estimateOK) {
final double msForPercent = msDiff / percentDiff;
final double estimateTotal = msForPercent * 100;
final double estimateRemaininig = estimateTotal - msForPercent * percent;
//Util.p(((int)(percent * 100)) / 100f + "% done, " + Util.msToReadableTime((long)estimateRemaininig) + " to go...");
} else {
//Util.p(percent + "% done, ETA unavailable yet...");
}
msPrev = ms;
percentPrev = percent;
}
}
//Util.p("\n" + n + " is prime!");
ms = System.currentTimeMillis() - start;
//Util.p(n.bitLength() + " bits, running time " + Util.msToReadableTime(ms));
return true;
}
}
/**
* Created by mihailod, Mar 9, 2009, 8:57:51 PM
*
* Find the sum of all the multiples of 3 or 5 below 1000.
*
*/
public class Problem1 {
public static void main(final String[] args) {
long sum = 0;
for (int i=3; i<1000; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i;
}
}
System.out.println("sum = " + sum);
}
}
import java.math.BigInteger;
/**
* Created by mihailod, Mar 10, 2009, 8:42:31 PM
*/
public class Problem12 {
public static void main(final String[] args) {
for (int i=1; i<1000000000; i++) {
if (i % 10000 == 0) {
System.out.println("i = " + i);
}
long num = generateTriangleNum(i);
//System.out.print("num = " + num);
int divisors = findDivisors(num);
//System.out.println(" divisors = " + divisors);
if (divisors > 500) {
System.out.println("divisors = " + divisors);
System.out.println("num = " + num);
break;
}
}
}
private static int findDivisors(long n) {
int divisors = 0;
double maxdivdouble = Math.sqrt((double)n);
int maxdivint = (int)maxdivdouble;
for (int i=1; i<=maxdivint; i++) {
if (n % i == 0) {
divisors+=2;
}
}
return divisors;
}
private static long generateTriangleNum(int n) {
long num = 0;
for (int i=1; i<=n; i++) {
num += i;
}
return num;
}
}
import java.util.StringTokenizer;
import java.math.BigInteger;
/**
* Created by mihailod, Mar 10, 2009, 7:44:50 PM
*
* Find the first ten digits of the sum of one-hundred 50-digit numbers.
*/
public class Problem13 {
public static void main(final String[] args) {
BigInteger sum = BigInteger.ZERO;
StringTokenizer st = new StringTokenizer(s, "\n");
while (st.hasMoreTokens()) {
String token = st.nextToken();
BigInteger bi = new BigInteger(token);
sum = sum.add(bi);
}
System.out.println("sum = " + sum);
}
private static final String s =
"37107287533902102798797998220837590246510135740250\n" +
"46376937677490009712648124896970078050417018260538\n" +
"74324986199524741059474233309513058123726617309629\n" +
"91942213363574161572522430563301811072406154908250\n" +
"23067588207539346171171980310421047513778063246676\n" +
"89261670696623633820136378418383684178734361726757\n" +
"28112879812849979408065481931592621691275889832738\n" +
"44274228917432520321923589422876796487670272189318\n" +
"47451445736001306439091167216856844588711603153276\n" +
"70386486105843025439939619828917593665686757934951\n" +
"62176457141856560629502157223196586755079324193331\n" +
"64906352462741904929101432445813822663347944758178\n" +
"92575867718337217661963751590579239728245598838407\n" +
"58203565325359399008402633568948830189458628227828\n" +
"80181199384826282014278194139940567587151170094390\n" +
"35398664372827112653829987240784473053190104293586\n" +
"86515506006295864861532075273371959191420517255829\n" +
"71693888707715466499115593487603532921714970056938\n" +
"54370070576826684624621495650076471787294438377604\n" +
"53282654108756828443191190634694037855217779295145\n" +
"36123272525000296071075082563815656710885258350721\n" +
"45876576172410976447339110607218265236877223636045\n" +
"17423706905851860660448207621209813287860733969412\n" +
"81142660418086830619328460811191061556940512689692\n" +
"51934325451728388641918047049293215058642563049483\n" +
"62467221648435076201727918039944693004732956340691\n" +
"15732444386908125794514089057706229429197107928209\n" +
"55037687525678773091862540744969844508330393682126\n" +
"18336384825330154686196124348767681297534375946515\n" +
"80386287592878490201521685554828717201219257766954\n" +
"78182833757993103614740356856449095527097864797581\n" +
"16726320100436897842553539920931837441497806860984\n" +
"48403098129077791799088218795327364475675590848030\n" +
"87086987551392711854517078544161852424320693150332\n" +
"59959406895756536782107074926966537676326235447210\n" +
"69793950679652694742597709739166693763042633987085\n" +
"41052684708299085211399427365734116182760315001271\n" +
"65378607361501080857009149939512557028198746004375\n" +
"35829035317434717326932123578154982629742552737307\n" +
"94953759765105305946966067683156574377167401875275\n" +
"88902802571733229619176668713819931811048770190271\n" +
"25267680276078003013678680992525463401061632866526\n" +
"36270218540497705585629946580636237993140746255962\n" +
"24074486908231174977792365466257246923322810917141\n" +
"91430288197103288597806669760892938638285025333403\n" +
"34413065578016127815921815005561868836468420090470\n" +
"23053081172816430487623791969842487255036638784583\n" +
"11487696932154902810424020138335124462181441773470\n" +
"63783299490636259666498587618221225225512486764533\n" +
"67720186971698544312419572409913959008952310058822\n" +
"95548255300263520781532296796249481641953868218774\n" +
"76085327132285723110424803456124867697064507995236\n" +
"37774242535411291684276865538926205024910326572967\n" +
"23701913275725675285653248258265463092207058596522\n" +
"29798860272258331913126375147341994889534765745501\n" +
"18495701454879288984856827726077713721403798879715\n" +
"38298203783031473527721580348144513491373226651381\n" +
"34829543829199918180278916522431027392251122869539\n" +
"40957953066405232632538044100059654939159879593635\n" +
"29746152185502371307642255121183693803580388584903\n" +
"41698116222072977186158236678424689157993532961922\n" +
"62467957194401269043877107275048102390895523597457\n" +
"23189706772547915061505504953922979530901129967519\n" +
"86188088225875314529584099251203829009407770775672\n" +
"11306739708304724483816533873502340845647058077308\n" +
"82959174767140363198008187129011875491310547126581\n" +
"97623331044818386269515456334926366572897563400500\n" +
"42846280183517070527831839425882145521227251250327\n" +
"55121603546981200581762165212827652751691296897789\n" +
"32238195734329339946437501907836945765883352399886\n" +
"75506164965184775180738168837861091527357929701337\n" +
"62177842752192623401942399639168044983993173312731\n" +
"32924185707147349566916674687634660915035914677504\n" +
"99518671430235219628894890102423325116913619626622\n" +
"73267460800591547471830798392868535206946944540724\n" +
"76841822524674417161514036427982273348055556214818\n" +
"97142617910342598647204516893989422179826088076852\n" +
"87783646182799346313767754307809363333018982642090\n" +
"10848802521674670883215120185883543223812876952786\n" +
"71329612474782464538636993009049310363619763878039\n" +
"62184073572399794223406235393808339651327408011116\n" +
"66627891981488087797941876876144230030984490851411\n" +
"60661826293682836764744779239180335110989069790714\n" +
"85786944089552990653640447425576083659976645795096\n" +
"66024396409905389607120198219976047599490197230297\n" +
"64913982680032973156037120041377903785566085089252\n" +
"16730939319872750275468906903707539413042652315011\n" +
"94809377245048795150954100921645863754710598436791\n" +
"78639167021187492431995700641917969777599028300699\n" +
"15368713711936614952811305876380278410754449733078\n" +
"40789923115535562561142322423255033685442488917353\n" +
"44889911501440648020369068063960672322193204149535\n" +
"41503128880339536053299340368006977710650566631954\n" +
"81234880673210146739058568557934581403627822703280\n" +
"82616570773948327592232845941706525094512325230608\n" +
"22918802058777319719839450180888072429661980811197\n" +
"77158542502016545090413245809786882778948721859617\n" +
"72107838435069186155435662884062257473692284509516\n" +
"20849603980134001723930671666823555245252804609722\n" +
"53503534226472524250874054075591789781264330331690";
}
import java.util.StringTokenizer;
/**
* Created by mihailod, Mar 10, 2009, 7:52:03 PM
*/
public class Problem14 {
private static final String s =
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n" +
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n" +
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n" +
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n" +
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n" +
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n" +
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n" +
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n" +
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n" +
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n" +
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n" +
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n" +
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n" +
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n" +
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n" +
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n" +
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n" +
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n" +
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n" +
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";
private static int a[][] = new int[20][20];
static {
int x;
int y = 0;
StringTokenizer st = new StringTokenizer(s, "\n");
while (st.hasMoreTokens()) {
String line = st.nextToken();
StringTokenizer st1 = new StringTokenizer(line, " ");
x = 0;
while (st1.hasMoreTokens()) {
String numberString = st1.nextToken();
System.out.println("numberString = " + numberString);
int number = Integer.parseInt(numberString);
a[x][y] = number;
x++;
}
y++;
}
for (int i=0; i<20; i++) {
for (int j=0; j<20; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println("\n");
}
}
/**
* What is the greatest product of four adjacent numbers in any direction
* (up, down, left, right, or diagonally) in the 2020 grid?
*/
public static void main(final String[] args) {
// horizontal
for (int i=0; i<17; i++) {
for (int j=0; j<20; j++) {
}
}
}
}
import java.util.ArrayList;
/**
* Created by mihailod, Mar 10, 2009, 8:13:43 PM
*/
public class Problem14real {
public static void main(final String[] args) {
int max = 0;
int index = 0;
for (int i=1; i<=1000000; i++) {
if (i % 50000 == 0) {
System.out.println("i = " + i);
}
int len = makeSequence(i).size();
if (len > max) {
max = len;
index = i;
}
}
System.out.println("max = " + max);
System.out.println("index = " + index);
}
private static ArrayList makeSequence(long n) {
ArrayList<Long> al = new ArrayList<Long>();
while (true) {
al.add(n);
if (n == 1) {
break;
} else if (n % 2 == 0) {
n = n/2;
} else {
n = 3*n + 1;
}
}
//System.out.println("al = " + al);
return al;
}
}
import java.math.BigInteger;
/**
* Created by mihailod, Mar 9, 2009, 9:17:01 PM
*
* Each new term in the Fibonacci sequence is generated
* by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
*
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence
which do not exceed four million.
problem 25: What is the first term in the Fibonacci sequence to contain 1000 digits?
*/
public class Problem2 {
private final static BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE);
public static void main(final String[] args) {
int termNumber = 1;
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;
BigInteger sum = BigInteger.ZERO;
while (true) {
if(a.toString().length() == 1000) {
System.out.println("a = " + a);
System.out.println("termNumber = " + (termNumber - 1));
break;
}
//System.out.print(a + " ");
//System.out.println(b + " ");
/*if (b.compareTo(BigInteger.valueOf(4000000)) > 0) {
System.out.println("sum = " + sum);
break;
}
if (a.mod(TWO).compareTo(BigInteger.ZERO) == 0) {
sum = sum.add(a);
}
if (b.mod(TWO).compareTo(BigInteger.ZERO) == 0) {
sum = sum.add(b);
}*/
BigInteger oldb = b;
a = a.add(b);
b = a.add(oldb);
termNumber +=2;
}
}
}
import java.math.BigInteger;
/**
* Created by mihailod, Mar 9, 2009, 10:05:11 PM
*
* Find the sum of the digits in the number 100!
*/
public class Problem20 {
public static void main(final String[] args) {
BigInteger fact = BigInteger.ONE;
for (int i=1; i<=100; i++) {
fact = fact.multiply(BigInteger.valueOf(i));
}
System.out.println("fact = " + fact);
String factString = fact.toString();
int sum = 0;
for (int i=0; i<factString.length(); i++) {
sum += factString.charAt(i) - '0';
}
System.out.println("sum = " + sum);
}
}
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Collections;
import java.io.BufferedReader;
import java.io.FileReader;
/**
* Created by mihailod, Mar 11, 2009, 7:52:25 PM
*
* For example, when the list is sorted into alphabetical order,
* COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53,
* is the 938th name in the list.
* So, COLIN would obtain a score of 938 * 53 = 49714.
*
* What is the total of all the name scores in the file?
*/
public class Problem22 {
public static void main(final String[] args) {
}
private static ArrayList<String> a = new ArrayList<String>();
static {
try {
BufferedReader br = new BufferedReader(new FileReader("22.txt"));
String line = br.readLine();
StringTokenizer st = new StringTokenizer(line, ",");
while(st.hasMoreTokens()) {
String token = st.nextToken();
token = token.substring(1, token.length() - 1);
a.add(token);
}
Collections.sort(a);
long total = 0;
for (int i=0; i<a.size(); i++) {
int position = i + 1;
String s = a.get(i);
int worth = 0;
for (int j=0; j<s.length(); j++) {
worth += s.charAt(j) - 'A' + 1;
}
worth *= position;
total += worth;
}
System.out.println("total = " + total);
} catch (Exception e) {
e.printStackTrace();
}
}
}
import java.math.BigInteger;
/**
* Created by mihailod, Mar 9, 2009, 9:32:48 PM
*
* What is the largest prime factor of the number 600851475143 ?
*/
public class Problem3 {
public static void main(final String[] args) {
for (long i = 3; i < 600851475143l; i++) {
if ((600851475143l % i == 0) && PrimeTest.isPrimeNaive(new BigInteger("" + i))) {
System.out.println(" *** factor i = " + i);
}
}
}
}
import java.util.ArrayList;
/**
* Created by mihailod, Mar 11, 2009, 9:14:18 AM
*
* The number, 197, is called a circular prime because all rotations
* of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?
*/
public class Problem35 {
public static void main(final String[] args) {
int counter = 0;
for (int i = 0; i< PrimeNumbers.PRIMES64.length; i++) {
long p = PrimeNumbers.PRIMES64[i];
if (isCircular(p)) {
System.out.println("p = " + p);
counter++;
}
}
System.out.println("counter = " + counter);
}
private static boolean isPrime(long p) {
for (int i = 0; i< PrimeNumbers.PRIMES64.length; i++) {
if (p == PrimeNumbers.PRIMES64[i]) {
return true;
}
}
return false;
}
private static boolean isCircular(long p) {
String s = String.valueOf(p);
// 1234 -> 2341 3412 4123
for (int i=1; i<s.length(); i++) {
String firstPart = s.substring(0, i);
String secondPart = s.substring(i, s.length());
String rot = secondPart + firstPart;
long pp = Long.valueOf(rot);
if (!isPrime(pp)) {
return false;
}
}
return true;
}
}
/**
* Created by mihailod, Mar 9, 2009, 10:49:56 PM
*
* Find the largest palindrome made from the product of two 3-digit numbers.
*
* Problem 36:
* Find the sum of all numbers less than one million,
* which are palindromic in base 10 and base 2.
*/
public class Problem4 {
public static void main(final String[] args) {
int sum = 0;
for(int i=1; i<1000000; i++) {
String base10 = String.valueOf(i);
String base2 = Integer.toString(i, 2);
if (isPalindrome(base10) && isPalindrome(base2)) {
sum += i;
}
}
System.out.println("sum = " + sum);
}
public static void main1(final String[] args) {
int max = 0;
for(int i=100; i<1000; i++) {
for(int j=100; j<1000; j++) {
int prod = i * j;
if(isPalindrome(String.valueOf(prod)) && prod > max) {
max = prod;
}
}
}
System.out.println("max = " + max);
}
public static boolean isPalindrome(String s) {
for(int i=0; i<s.length() / 2; i++) {
if(s.charAt(i) != s.charAt(s.length() - 1 - i)) {
return false;
}
}
System.out.println("palindrome s = " + s);
return true;
}
}
import java.util.Hashtable;
/**
* Created by mihailod, Mar 11, 2009, 11:30:13 PM
*
* Pentagonal numbers are generated by the formula, Pn=n(3n-1)/2.
* The first ten pentagonal numbers are:
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
It can be seen that P4 + P7 = 22 + 70 = 92 = P8.
However, their difference, 70 - 22 = 48, is not pentagonal.
Find the pair of pentagonal numbers, Pj and Pk,
for which their sum and difference is pentagonal
and D = |Pk - Pj| is minimised; what is the value of D?
*/
public class Problem44 {
static long pents[] = new long[5000];
private static final long N = 5000;
static Hashtable ht = new Hashtable();
public static void main(final String[] args) {
long start = System.currentTimeMillis();
for (int i=0; i<N; i++) {
long ii = (long)i;
long p = (ii*(3*ii - 1))>>1;
pents[i] = p;
if (p > 0) {
ht.put(p, p);
}
}
for (int i=1; i<pents.length; i++) {
/*if (i % 10 == 0) {
System.out.println("i = " + i);
}*/
long p1 = pents[i];
for (int j=i; j<pents.length; j++) {
long p2 = pents[j];
long sum = p1 + p2;
long diff = p1 > p2 ? p1 - p2 : p2 - p1;
if (ht.get(diff) != null && ht.get(sum) != null) {
System.out.print("p1 = " + p1);
System.out.println(" p2 = " + p2);
System.out.println("diff = " + diff);
System.out.println("done in " + (System.currentTimeMillis() - start) + "ms");
}
}
}
}
}
/**
* Created by mihailod, Mar 11, 2009, 9:55:04 PM
*
* Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
Pentagonal Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n-1) 1, 6, 15, 28, 45, ...
It can be verified that T285 = P165 = H143 = 40755.
Find the next triangle number that is also pentagonal and hexagonal.
*/
public class Problem45 {
private static int N = 100001;
public static void main(final String[] args) {
long start = System.currentTimeMillis();
long time = System.currentTimeMillis();
//for (long i=1; i<N; i++) {
// if (i % 10000 == 0) {
// System.out.println("i = " + i + " in " + (System.currentTimeMillis() - time) + "ms");
// time = System.currentTimeMillis();
// }
// long t = (i*(i+1))>>1;
for (long j=1; j<N; j++) {
long p = (j*(3*j - 1))>>1;
//if (t < p || t > p) {
// continue;
//} else {
// System.out.println("candidate " + p + " t = " + i + " p = " + j + "...");
//}
for (long k=1; k<N; k++) {
long h = k *(2*k - 1);
if (h > p) {
break;
}
if (p == h /*&& t == p*/) {
System.out.print("GOTCHA " + p);
//System.out.print(" t = " + i);
System.out.print(" p = " + j);
System.out.println(" h = " + k);
if(p > 40755) {
System.out.println("It took: " + (System.currentTimeMillis() - start) + "ms" );
System.exit(0);
}
}
}
}
//}
}
}
import java.math.BigInteger;
/**
* Created by mihailod, Mar 9, 2009, 10:10:41 PM
*
* Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.
*
* 97: 28433 * 2^(7830457+1)
Find the last ten digits of this prime number.
*/
public class Problem48 {
public static void main(final String[] args) {
/*BigInteger sum = BigInteger.ZERO;
for (int i=1; i<=1000; i++) {
BigInteger addition = (BigInteger.valueOf(i)).pow(i);
sum = sum.add(addition);
}
System.out.println("sum = " + sum);*/
// 97
BigInteger a = BigInteger.valueOf(28433);
BigInteger two = BigInteger.ONE.add(BigInteger.ONE);
BigInteger power = two.pow(7830457+1);
BigInteger result = a.multiply(power);
System.out.println("result = " + result);
}
}
import java.util.ArrayList;
import java.util.Arrays;
/**
* Created by mihailod, Mar 11, 2009, 8:43:35 PM
*
* The arithmetic sequence, 1487, 4817, 8147,
* in which each of the terms increases by 3330,
* is unusual in two ways:
* (i) each of the three terms are prime, and,
* (ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes,
exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence?
*/
public class Problem49 {
public static void main(final String[] args) {
}
private static boolean satisfy(int a, int b, int c) {
if (a == b || b == c || a == c) {
return false;
}
if (a - b != b - c) {
return false;
}
String as = String.valueOf(a);
String bs = String.valueOf(b);
String cs = String.valueOf(c);
int aa[] = new int[4];
int ba[] = new int[4];
int ca[] = new int[4];
for (int i=0; i<4; i++) {
aa[i] = as.charAt(i) - '0';
ba[i] = bs.charAt(i) - '0';
ca[i] = cs.charAt(i) - '0';
}
Arrays.sort(aa);
Arrays.sort(ba);
Arrays.sort(ca);
for (int i=0; i<4; i++) {
if (!(aa[i] == ba[i] && ba[i] == ca[i])) {
return false;
}
}
return true;
}
private static ArrayList<Integer> a = new ArrayList<Integer>();
static {
for (int i=0; i<PrimeNumbers.PRIMES64.length; i++) {
int p = PrimeNumbers.PRIMES64[i];
if (String.valueOf(p).length() == 4) {
a.add(p);
}
}
//System.out.println("a = " + a);
for (int i=0; i<a.size() - 2; i++) {
int p1 = a.get(i);
for (int j=i; j<a.size() - 1; j++) {
int p2 = a.get(j);
for (int k=j; k<a.size(); k++) {
int p3 = a.get(k);
if(satisfy(p1, p2, p3)) {
System.out.print(p1);
System.out.print(" " + p2);
System.out.println(" " + p3);
}
}
}
}
}
}
/**
* Created by mihailod, Mar 9, 2009, 9:08:38 PM
*
* What is the smallest number divisible by each of the numbers 1 to 20?
*/
public class Problem5 {
public static void main(final String[] args) {
long num = 20;
while(true) {
if (divisible(num)) {
System.out.println("num = " + num);
break;
}
num += 20;
}
}
private static boolean divisible(long num) {
for (int i=2; i<20; i++) {
if (num % i != 0) {
return false;
}
}
return true;
}
}
import java.math.BigInteger;
import java.util.ArrayList;
/**
* Created by mihailod, Mar 11, 2009, 9:14:03 PM
*
* The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand
that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
*/
public class Problem50 {
private static int ppp = 0;
private static int localmax = 0;
private static int findlongestsumstartingwith(int pointer) {
localmax = 0;
ArrayList<Integer> al = new ArrayList<Integer>();
int sum = PrimeNumbers.PRIMES64[pointer];
al.add(sum);
int num = 1;
int counter = pointer + 1;
while (true) {
if(counter > PrimeNumbers.PRIMES64.length - 2) {
return localmax;
}
sum += PrimeNumbers.PRIMES64[counter];
al.add(PrimeNumbers.PRIMES64[counter]);
num++;
BigInteger bi = BigInteger.valueOf(sum);
if(bi.isProbablePrime(5)) {
ppp = sum;
localmax = num;
//System.out.println("al = " + al);
//System.out.println("ppp = " + ppp);
//System.out.println("num = " + num);
//return num;
}
counter++;
}
}
public static void main(final String[] args) {
int longest = 0;
for (int i=0; i<10/*PrimeNumbers.PRIMES64.length*/; i++) {
if (i % 50000 == 0) {
System.out.println("i = " + i);
}
int candidate = findlongestsumstartingwith(i);
System.out.println("candidate = " + candidate);
if (candidate > longest) {
longest = candidate;
}
}
System.out.println("longest = " + longest);
System.out.println("ppp = " + ppp);
}
}
import java.math.BigInteger;
/**
* Created by mihailod, Mar 10, 2009, 9:08:18 PM
*
* Considering natural numbers of the form, a^b,
* where a, b < 100, what is the maximum digital sum?
*/
public class Problem56 {
public static void main(final String[] args) {
int max = 0;
for (int i=1; i<101; i++) {
BigInteger a = BigInteger.valueOf(i);
for (int j=1; j<101; j++) {
BigInteger exp = a.pow(j);
int ds = digitalSum(exp);
if (ds > max) {
max = ds;
}
}
}
System.out.println("max = " + max);
}
private static int digitalSum(BigInteger bi) {
String s = bi.toString();
int sum = 0;
for (int i=0; i<s.length(); i++) {
sum += s.charAt(i) - '0';
}
return sum;
}
}
/**
* Created by mihailod, Mar 9, 2009, 9:26:49 PM
*
* Find the difference between the sum of the squares
* of the first one hundred natural numbers and the square of the sum.
*/
public class Problem6 {
public static void main(final String[] args) {
int sum = 0;
int sumOfSquares = 0;
for (int i=1; i<=100; i++) {
sum += i;
sumOfSquares += i * i;
}
System.out.println("sum = " + sum);
long squareOfSum = sum * sum;
System.out.println("squareOfSum = " + squareOfSum);
System.out.println("sumOfSquares = " + sumOfSquares);
long diff = squareOfSum - sumOfSquares;
System.out.println("diff = " + diff);
}
}
import java.math.BigInteger;
/**
* Created by mihailod, Mar 9, 2009, 9:45:57 PM
*
* Find the 10001st prime.
*
*
* problem 10: Find the sum of all the primes below two million.
*
* problem 16: What is the sum of the digits of the number 2^1000?
*/
public class Problem7 {
public static void main7(final String[] args) {
System.out.println(PrimeNumbers.PRIMES[10000]);
}
// false answer 987654103
public static void mainpan(final String[] args) {
long ms = System.currentTimeMillis();
for (long i=2143; i>1; i--) {
if (i % 10000000 == 0) {
System.out.print("i = " + i);
long took = System.currentTimeMillis() - ms;
ms = System.currentTimeMillis();
System.out.println(" took = " + took);
}
/**
* 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
*/
if (i % 2 == 0 || i % 3 == 0 || i % 5 ==0 || i % 7 == 0 || i % 11 == 0 || i % 13 ==0 ||
i % 17 == 0 || i % 19 == 0 || i % 23 ==0 || i % 29 == 0) {
continue;
}
if (!isPanDigital(i)) {
continue;
}
/*if (!PrimeTest.isPrimeSuperNaive(i)) {
continue;
}*/
final BigInteger bi = BigInteger.valueOf(i);
if (bi.isProbablePrime(5)) {
System.out.println("OLE! bi = " + bi);
//break;
}
}
}
private static boolean isPanDigital(final long l) {
final String s = String.valueOf(l);
final int len = s.length();
for (int i=0; i<len; i++) {
final int digit = s.charAt(i) - '0';
if(digit > s.length() - 1) {
return false;
}
final int start = i+1;
for (int j=start; j<len; j++) {
final int d = s.charAt(j) - '0';
if(digit == d) {
return false;
}
}
}
return true;
}
public static void main10(final String[] args) {
long sum = 0;
for(int i=2; i<2000000; i++) {
if(i % 100000 == 0) {
System.out.println("i = " + i);
}
BigInteger bi = BigInteger.valueOf(i);
if(bi.isProbablePrime(5)) {
sum += bi.longValue();
}
}
System.out.println("sum = " + sum);
}
public static void main(final String[] args) {
BigInteger b = BigInteger.ONE.add(BigInteger.ONE);
b = b.pow(1000);
System.out.println("b = " + b);
String s = b.toString();
int sum = 0;
for(int i=0; i<s.length(); i++) {
sum += s.charAt(i) - '0';
}
System.out.println("sum = " + sum);
}
}
/**
* Created by mihailod, Mar 9, 2009, 10:33:42 PM
*
* Find the greatest product of five consecutive digits in the 1000-digit number.
*/
public class Problem8 {
private static final String s =
"73167176531330624919225119674426574742355349194934" +
"96983520312774506326239578318016984801869478851843" +
"85861560789112949495459501737958331952853208805511" +
"12540698747158523863050715693290963295227443043557" +
"66896648950445244523161731856403098711121722383113" +
"62229893423380308135336276614282806444486645238749" +
"30358907296290491560440772390713810515859307960866" +
"70172427121883998797908792274921901699720888093776" +
"65727333001053367881220235421809751254540594752243" +
"52584907711670556013604839586446706324415722155397" +
"53697817977846174064955149290862569321978468622482" +
"83972241375657056057490261407972968652414535100474" +
"82166370484403199890008895243450658541227588666881" +
"16427171479924442928230863465674813919123162824586" +
"17866458359124566529476545682848912883142607690042" +
"24219022671055626321111109370544217506941658960408" +
"07198403850962455444362981230987879927244284909188" +
"84580156166097919133875499200524063689912560717606" +
"05886116467109405077541002256983155200055935729725" +
"71636269561882670428252483600823257530420752963450";
public static void main(final String[] args) {
int maxProd = 0;
for (int i=0; i<s.length() - 4; i++) {
String sub = s.substring(i, i+5);
int candidateProd = findProd(sub);
if (candidateProd > maxProd) {
maxProd = candidateProd;
}
}
System.out.println("maxProd = " + maxProd);
}
private static int findProd(String s) {
return (s.charAt(0) - '0') * (s.charAt(1) - '0') *
(s.charAt(2) - '0') * (s.charAt(3) - '0') * (s.charAt(4) - '0');
}
}
/**
* Created by mihailod, Mar 9, 2009, 11:04:32 PM
*
* There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
*/
public class Problem9 {
public static void main(final String[] args) {
for (int a=0; a<1001; a++) {
for (int b=1; b<1001; b++) {
for (int c=1; c<1001; c++) {
if (a*a + b*b == c*c && a + b + c == 1000) {
System.out.println("abc = " + a * b * c);
}
}
}
}
}
}
/**
* Created by mihailod, Mar 9, 2009, 9:08:52 PM
*/
public class Root {
public static void main(final String[] args) {
Problem44.main(null);
}
}
/**
* Created by mihailod, 24.05.2008., 13.35.57
*/
public class Util {
public static String msToReadableTime(final long ms) {
final long h = ms / (1000*60*60);
final long m = (ms % (1000*60*60)) / (1000*60);
final long s = ((ms % (1000*60*60)) % (1000*60)) / 1000;
if(h == 0 && m == 0 && s == 0) {
return ms == 0 ? "negligible" : ms + "ms";
}
final StringBuilder sb = new StringBuilder();
sb.append(h > 0 ? h + "h " : " ");
sb.append(m > 0 ? m + "m " : " ");
sb.append(s > 0 ? s + "s " : " ");
return sb.toString();
}
public static void p(final String s) {
System.out.println(s);
}
public static String makeSpacePadder(final int len) {
final StringBuilder sb = new StringBuilder(len);
for(int i=0; i<len; i++) {
sb.append(" ");
}
return sb.toString();
}
}