Project Euler - problem 50

I resolved Euler's problem 50 quite dirty by iterating over all primes in the generated sieve to find for each prime the maximum of possible terms for the sum of a sequence starting at this prime.
<br />long time = currentTimeMillis();<br />final TIntArrayList sieve = Maths.sieve(999999);<br />int maxSum = 0, maxStart = 0, maxEnd = 0, maxTerms = 0;<br />for (int start = 0, max = sieve.size(); start < max - 21; start++) {<br /> int sum = sieve._data[start], end = start + 1;<br /> for (; end < max; end++) {<br /> int s = sum + sieve._data[end];<br /> if (s <= sum) break; // overflow !<br /> sum = s;<br /> final int terms = end - start + 1;<br /> if (maxTerms < terms && sieve.binarySearch(sum) >= 0) {<br /> maxStart = sieve._data[start];<br /> maxEnd = sieve._data[end];<br /> maxSum = sum;<br /> maxTerms = terms;<br /> out.println("S(" + maxStart + "," + maxEnd + ")=" + maxSum + " (" + maxTerms + " terms) in " + (currentTimeMillis() - time) + "ms");<br /> }<br /> }<br />}<br />out.println("=> MAX: S(" + maxStart + "," + maxEnd + ")=" + maxSum + " (" + maxTerms + " terms) in " + (currentTimeMillis() - time) + "ms");<br />
Outputs:

S(7,3931)=997651 (543 terms) in 85ms

Project Euler - problem 49

Problem 49: i created a sieve up to 9999 and checked each prime number which have the same properties to match the sequence.
<br />long time = currentTimeMillis();<br />// create a sieve up to maximum prime number having 4 digits<br />final TIntArrayList sieve = Maths.sieve(9999);<br />for (int i = 0, max = sieve.size(); i < max - 2; i++) {<br /> final int prime = sieve.get(i);<br /> if (prime > 1000 && prime < 9999<br /> && sieve.binarySearch(prime + 3330) >= 0<br /> && sieve.binarySearch(prime + 6660) >= 0<br /> && Maths.arePermutations(prime, prime + 3330, prime + 6660))<br /> System.out.println(prime + " " + (prime + 3330) + " " + (prime + 6660));<br />}<br />out.println(" in " + (currentTimeMillis() - time) + "ms");<br />
Outputs:

1487 4817 8147
2969 6299 9629
 in 20ms

Project Euler - problem 48

Euler's Problem 48 can be quickly resolved in Java thanks to BigIntegers, like this:
<br />final long time = currentTimeMillis();<br />BigInteger sum = BigInteger.ZERO;<br />for (int n = 1; n <= 1000; n++) <br /> sum = sum.add(BigInteger.valueOf(n).pow(n));<br />out.println(sum + " in " + (currentTimeMillis() - time) + "ms");<br />Outputs:

...797271283465789498383642350667978127819110846700 in 387ms

But a more clever way of computing big numbers can be done here, simply using int or long primitives, by using modulo operations all the time. Modulo operation has the following properties:
If

a1 = r1 mod b

and

a2 = r2 mod b

• a1+b2 = r1+r2 mod b

• a1*b2 = r1*r2 mod b

• a1^n = r1^n mod b

We only want to keep the ten last digits. So it means we want to apply a modulo 10^10 to the number found, or we could say that we only care about the 10 right digits, it means we can do all operations modulo 10000000000;

Example:

We want to keep only the two last digits of the resulting numbers. So we apply mod 100 to the results.

131+145=276

,

276 mod 100 = 76

131*145=18995

,

18995 mod 100 = 95

131^3=2248091

,

2248091 mod 100 = 91

But we could also have done this, using modulo operations:

131 mod 100 = 31, 145 mod 100 = 45

=> 2 last digits of 131+145:

131+145 mod 100 = ((131 mod 100) + (145 mod 100)) mod 100 = 76

=> 2 last digits of 131*145:

131*145 mod 100 = ((131 mod 100) * (145 mod 100)) mod 100 = 1395 mod 100 = 95

=> 2 last digits of 131^3:

131^3 mod 100 = (((31 mod 100) * (145 mod 100)) mod 100)*31 mod 100 = 91

Modulo operation enables to keep only significant part when executing operation. Hence, we can compute the remaining part of a big number only using primitives types.

So we can develop methods to execute add, multiply and pow operations modulo n:
<br />public static long multiplyMod(long a, long b, long mod) {<br /> return ((a % mod) * (b % mod)) % mod;<br />}<br /><br />public static long addMod(long a, long b, long mod) {<br /> return ((a % mod) + (b % mod)) % mod;<br />}<br /><br />public static long powMod(long a, long exp, long mod) {<br /> a = a % mod;<br /> long pow = 1;<br /> while (exp-- > 0) pow = (pow * a) % mod;<br /> return pow;<br />}Then, our program becomes:
<br />long time = currentTimeMillis();<br />final long mod = 10000000000L;<br />long s = 0;<br />for (int n = 1; n <= 1000; n++) <br /> s = Maths.addMod(Maths.powMod(n, n, mod), s, mod);<br />out.println(s + " in " + (currentTimeMillis() - time) + "ms");<br />
And the output is far more faster:

9110846700 in 88ms

Project Euler - problem 47

For Problem 47, we need to list the 4 consecutive numbers having 4 different prime factors. Obviously the first number to begin iterating is

n = 2 * 3 * 5 * 7

and we will increment by 1 each time. For each number n we need to extract its factors (such method has already be done in previous problems) and check its size. To extract the factors of a number, we need to have a prime list and check if numbers are prime. To avoid computing primes, a create a Sieve of 100000 primes and extends it in demand. Then i use this prime sieve to extract the factors of the number n.

<br />final long time = currentTimeMillis();<br /><br />// will stock our results, just for display<br />final List<List<Maths.Factor>> results = new ArrayList<List<Maths.Factor>>(4);<br />final int[] numbers = new int[4];<br /><br />// create a prime sieve to reuse it to find factors to avoid repeated calls of trial division<br />TIntArrayList sieve = Maths.sieve(100000);<br />int max = sieve.last();<br /><br />// check all numbers starting at 2*3*5*7 which is the first composite of 4 different primes<br />for (int n = 2 * 3 * 5 * 7, consecutive = 0; ; n++) {<br /><br /> // if n is above the sieve limit, we extend the sieve up to 2n primes<br /> if (n > max) {<br /> sieve = Maths.sieveExtend(100000, sieve);<br /> max = sieve.last();<br /> }<br /><br /> // then we extract the different prime factors of n.<br /> List<Maths.Factor> factors = Maths.decompSieve(n, sieve);<br /><br /> // if the count is 4, we increment our counter. Otherwise, we reset it.<br /> if (factors.size() == 4) {<br /> results.add(consecutive, factors);<br /> numbers[consecutive++] = n;<br /> } else consecutive = 0;<br /><br /> // we have a result, we display it.<br /> if (consecutive == 4) {<br /> for (int i = 0; i < numbers.length; i++)<br /> System.out.println(numbers[i] + ": " + results.get(i));<br /> out.println(" in " + (currentTimeMillis() - time) + "ms");<br /> break;<br /> }<br />}<br />
The source code is here.
I hardly reuse the Maths class which contains the Sieve and decomposition methods.
The program outputs:

134043: [3^1, 7^1, 13^1, 491^1]
134044: [2^2, 23^1, 31^1, 47^1]
134045: [5^1, 17^1, 19^1, 83^1]
134046: [2^1, 3^2, 11^1, 677^1]
 in 3890ms

Project Euler - problem 46

Problem 46 is easy: I maintained to list: one for squares and one for primes. Then i iterate over all numbers and checked them against these list:

• When i find an even number i, i add its square to the square list
• When i find an odd number i, i try, for all primes p below i to check if the square list contains

(i-p)/2

final long time = currentTimeMillis();
final TIntArrayList squares = new TIntArrayList(1000);
squares.add(new int[]{1, 4, 9, 16, 25, 36, 49, 64});
final TIntArrayList primes = new TIntArrayList(1000);
primes.add(new int[]{2, 3, 5, 7});
for (int i = 9; ; i++) {
    squares.add(i * i);
    if ((i & 1) == 1) {
        if (Maths.isPrime(i, primes)) primes.add(i);
        else {
            int pos = -1;
            for (int pIndex = 1, max = primes.size(), p; pIndex < max && (p = primes.getQuick(pIndex)) < i; pIndex++) {
                pos = squares.binarySearch((i - p) >> 1);
                if (pos >= 0) {
                    //out.println(i + "=" + p + "+2*" + squares.getQuick(pos));
                    break;
                }
            }
            if (pos < 0) {
                out.println("Not valid for: " + i + " in " + (currentTimeMillis() - time) + "ms");
                return;
            }
        }
    }
}

The isPrime method check if a number p is prime by using the supplied prime list. Its a sort of memoizer to avoid computing same primes again and again.

The output is:

Not valid for: 5777 in 54ms

Project Euler - problem 45

Euler's Problem 45:

final long time = currentTimeMillis();
for (int i = 286; ; i++) {
    final long ti = Maths.triangle(i);
    final long n = Maths.isHexagonal(ti);
    final long m = Maths.isPentagonal(ti);
    if (n != -1 && m != -1) {
        out.println("T(" + i + ")=P(" + m + ")=H(" + n + ")=" + ti);
        out.println("T(" + i + ")=" + Maths.triangle(i));
        out.println("P(" + m + ")=" + Maths.pentagonal(m));
        out.println("H(" + n + ")=" + Maths.hexagonal(n));
        out.println(" in " + (currentTimeMillis() - time) + "ms");
        break;
    }
}

I've already done some methods to compute and check for pentagonal, triangle and hexagonal numbers. You can find them here.

Project Euler - problem 44

Problem 44: i thought about this problem very hard, but in reality it is really simple to solve.
You can see that the pentagonal sequence 1, 5, 12, 22, 35, 51, 70, 92, 117,... can be generated by the following recursive definition:

P(1) = 1
P(n) = P(n-1) + 3n - 2

So what we can do is iterating over each P(k) and put P(k) in a list. Each time we create a new pentagonal number, we check each numbers from P(k-1) to P(1) to check if the difference is in the list. If yes, we then have to check if the sum of P(k) minus P(j) is a pentagonal number.
To know if a number is pantagonal, Wikipedia helped. we have to check if

(sqrt{24*number+1}+1)/6

is a natural number.
<br />final long time = currentTimeMillis();<br />TIntArrayList pentagonals = new TIntArrayList();<br />pentagonals.add(1);<br />for (int k = 2; ; k++) {<br /> final int pk = pentagonals.getQuick(k - 2) + 3 * k - 2;<br /> pentagonals.add(pk);<br /> for (int j = k - 2; j >= 0; j--) {<br /> final int d = pk - pentagonals.getQuick(j);<br /> if (pentagonals.binarySearch(d) > 0 && Maths.isPentagonal(pk + pentagonals.getQuick(j))) {<br /> out.println(d + " in " + (currentTimeMillis() - time) + "ms");<br /> return;<br /> }<br /> }<br />}
isPentagonal method:

public static boolean isPentagonal(int number) {
    double test = (sqrt(24 * number + 1) + 1) / 6;
    return test == (int) test;
}

Project Euler - problem 43

Euler Problem 43: i've first tried to iterate over all numbers and when a pandigital was found, execute divisibility tests. But it is really long. So i splitted the problem in small parts to avoid working with big numbers, and i regularly used divisibility tests to validate numbers.

• d7d8d9 is divisible by 13
• d8d9d10 is divisible by 17
  

So we can find d7d8d9d10 by combining the list of numbers divisible by 13 or 17 having 2 digits in common. Iterating over multiples is easy as we increment the counters by 2, 5, 13, 17, ... each time.

<br />// search for combinations of multiples of 13 (d7d8d9) and 17 (d8d9d10) to build d7d8d9d10<br />final TIntArrayList list_d7d8d9d10 = new TIntArrayList();<br />for (int d8d9d10 = 17; d8d9d10 < 987; d8d9d10 += 17) { // 017 to 987<br /> for (int d7d8d9 = 13; d7d8d9 < 987; d7d8d9 += 13) { // 013 to 987<br /> if (d7d8d9 % 100 == d8d9d10 / 10) {<br /> final int d7d8d9d10 = d7d8d9 * 10 + d8d9d10 % 10;<br /> if (Maths.hasDifferentDigitsForLength(d7d8d9d10, 4)) {<br /> final int offset = list_d7d8d9d10.binarySearch(d7d8d9d10);<br /> if (offset < 0) list_d7d8d9d10.insert(-offset - 1, d7d8d9d10);<br /> }<br /> }<br /> }<br />}<br />System.out.println("d7d8d9d10: " + list_d7d8d9d10);<br />

• d2d3d4 is divisible by 2
• d4d5d6 is divisible by 5
• d3d4d5 is divisible by 3
  

d4d5d6 can't end with 0, because if d6 = 0, for d6d7d8 to be divisible by 11, d7 = d8: 011, 022, 033, ... Since we are looking for pandigital numbers, all digits must be different.
So to find all d4d5d6 we will increment by 10 each time.

So we will combine all d2d3d4 numbers by d4d5d6 numbers having d4 in common, and i will check if the sum of digits d3d4d5 is divisible by 3.

<br />// search for multiples of 2 (d2d3d4), 3 (d3d4d5) and 5 (d4d5d6) to build d2d3d4d5d6<br />final TIntArrayList list_d2d3d4d5d6 = new TIntArrayList();<br />for (int d4d5d6 = 15; d4d5d6 < 987; d4d5d6 += 10) { // 015 to 987, skipping cases where d6 = 0<br /> for (int d2d3d4 = 12; d2d3d4 < 987; d2d3d4 += 2) { // 012 to 987<br /> final int d4 = d2d3d4 % 10;<br /> // if d4 is the same digit in both numbers, we can combine them and check<br /> // if d3d4d5 is a multiple of 3<br /> if (d4d5d6 / 100 == d4 && ((d2d3d4 % 100) / 10 + d4 + (d4d5d6 % 100) / 10) % 3 == 0) {<br /> final int d2d3d4d5d6 = d2d3d4 * 100 + d4d5d6 % 100;<br /> if (Maths.hasDifferentDigitsForLength(d2d3d4d5d6, 5)) {<br /> int offset = list_d2d3d4d5d6.binarySearch(d2d3d4d5d6);<br /> if (offset < 0) list_d2d3d4d5d6.insert(-offset - 1, d2d3d4d5d6);<br /> }<br /> }<br /> }<br />}<br />System.out.println("d2d3d4d5d6: " + list_d2d3d4d5d6);<br />
Then we combine all d2d3d4d5d6 and d7d8d9d10 numbers found to form a 9-digit number and we check remaing divisibility tests

• d5d6d7 is divisible by 7
• d6d7d8 is divisible by 11

Then we try for each values of d1 if d1d2d3d4d5d6d7d8d9d10 is pandigital

<br />// now builds the whole number<br />final TLongArrayList list_d1d2d3d4d5d6d7d8d9d10 = new TLongArrayList();<br />for (int i = 0, max_i = list_d2d3d4d5d6.size(); i < max_i; i++) {<br /> for (int j = 0, max_j = list_d7d8d9d10.size(); j < max_j; j++) {<br /> final int d2d3d4d5d6 = list_d2d3d4d5d6.getQuick(i);<br /> final int d7d8d9d10 = list_d7d8d9d10.getQuick(j);<br /> if (((d7d8d9d10 / 100) % 10 - d7d8d9d10 / 1000 + (d2d3d4d5d6 % 10)) % 11 == 0<br /> && ((d2d3d4d5d6 % 100) * 10 + d7d8d9d10 / 1000) % 7 == 0) {<br /> for (long d1 = 1; d1 <= 9; d1++) { // for each d1 from 0 to 9<br /> final long d1d2d3d4d5d6d7d8d9d10 = (d1 * 100000L + d2d3d4d5d6) * 10000L + d7d8d9d10;<br /> if (Maths.isPandigital(d1d2d3d4d5d6d7d8d9d10, 0, 9)) {<br /> System.out.println(d1d2d3d4d5d6d7d8d9d10);<br /> final int offset = list_d1d2d3d4d5d6d7d8d9d10.binarySearch(d1d2d3d4d5d6d7d8d9d10);<br /> if (offset < 0) list_d1d2d3d4d5d6d7d8d9d10.add(d1d2d3d4d5d6d7d8d9d10);<br /> }<br /> }<br /> }<br /> }<br />}<br />System.out.println("d1d2d3d4d5d6d7d8d9d10: " + list_d1d2d3d4d5d6d7d8d9d10);<br />
And we compute the sum:

<br />// compute the sum<br />long sum = 0;<br />for (int i = 0, max_i = list_d1d2d3d4d5d6d7d8d9d10.size(); i < max_i; i++) {<br /> sum += list_d1d2d3d4d5d6d7d8d9d10.getQuick(i);<br />}<br />out.println("sum: " + sum + " in " + (currentTimeMillis() - time) + "ms");<br />
See complete source code here.

Jabbify in Blogger

I've seen today this post on Comet Daily on Jabbify.

Jabbify is a cool way to add chatting on your web site. It's not a trivial chat system, or a complex one requiring php. What is cool about Jabbify is that it installs in few seconds and communicate through Jabber. They automatically provide a Jabber user matching your domain. Once you added this user to your contact list, you can chat from your Gtalk, Pidgin or any other IM software with the users visiting your website. If they need support, they just have to leave a message, which will directly popup in your IM software.

On integrate jabbify in blogger, just add the following javascript to your template:

<br /><script src="http://jabbify.com/side.js" type="text/javascript"></script><br />
I tried it in this blog, but finally i disabled it since i didn't found a way to start the chat window minimized...

Project Euler - problem 42

Problem 42:
For each word in the list, we get it's word value v. We then check if there is a solution for the equation:

v=t_n=0.5*n*(n+1)

The positive integer solutions (which have no fractional part) correspond to t_n, the Nth triangle number.

0.5*n^2+0.5*n-v=0

Solutions:

n1=(-0.5+sqrt{0.5^2+4*0.5*v})/2*0.5

and

n2=(-0.5-sqrt{0.5^2+4*0.5*v})/2*0.5

Which gives:

n1=-0.5+sqrt{0.25+2*v}

and

n2=-0.5-sqrt{0.25+2*v}

We will only compute n1 since n2 will be negative.

<br />public static void main(String[] args) throws Exception {<br /> final long time = currentTimeMillis();<br /> int count = 0;<br /> for (Scanner scanner = new Scanner(new File("data/words.txt")).useDelimiter(","); scanner.hasNext();) {<br /> String word = scanner.next();<br /> int v = value(word);<br /> double n1 = -0.5 + Math.sqrt(0.25 + 2 * v);<br /> if (n1 == (int) n1) {<br /> count++;<br /> System.out.println(word + ": t(" + (int) n1 + ")=" + v);<br /> }<br /> }<br /> out.println(count + " in " + (currentTimeMillis() - time) + "ms");<br />}<br /><br />private static int value(String s) {<br /> s = s.toUpperCase();<br /> int v = 0;<br /> for (int i = 0, max = s.length(); i < max; i++) v += s.charAt(i) - 64;<br /> return v;<br />}<br />

Project Euler - problem 41

Problem 41 requires little thinking since testing all primes up to 987654321 is too expensive in Java. So we must try to reduce the quantity of prime numbers to generate for testing against our pandigital test.

A number is divisible by 3 if its digit sum is a multilple of 3. We try to find the maximum pandigital number not divisible:

9+8+7+6+5+4+3+2+1=45
8+7+6+5+4+3+2+1=36
6+5+4+3+2+1=21
5+4+3+2+1=15
3+2+1=6
2+1=3

Divisible by 3 => There can't be any 1-9, 1-8, 1-6, 1-5 pandigital prime.

7+6+5+4+3+2+1=28
4+3+2+1=10

Not divisible by 3. So we will check primes from 7654321 to 1234567 and then if not found from 4321 to 1234.

<br />long time = currentTimeMillis();<br />for (int i = 7654321; i >= 1234567; i -= 2) {<br /> if (Maths.isPandigital(i, 7) && Maths.isPrime(i)) {<br /> out.println(i + " in " + (currentTimeMillis() - time) + "ms");<br /> break;<br /> }<br />}<br />
Outputs:

7652413 in 8ms

I reused isPandigital method and isPrime method from previous problems.

Source code here.

Project Euler - problem 40

Problem 40:

<br />long time = currentTimeMillis();<br />StringBuilder sb = new StringBuilder();<br />for (int i = 0; sb.length() <= 1000000; i++) sb.append(i);<br />int prd = 1;<br />for (int i = 1; i <= 1000000; i *= 10) {<br /> out.println(sb.charAt(i));<br /> prd *= (sb.charAt(i) - 48);<br />}<br />out.println(prd + " in " + (currentTimeMillis() - time) + "ms");<br />
Outputs:

1
1
5
3
7
2
1
210 in 58ms

Project Euler - problem 39

Problem 39 is also very easy if you already solved problem 9
I've already made a method to recover Pythagorean triplets:

<br />public static List<Triplet> pythagoreanTriplet(int sum) {<br /> List<Triplet> set = new ArrayList<Triplet>();<br /> sum >>= 1;<br /> for (int m = 2, max = sqrtCeil(sum); m < max; m++) {<br /> if (sum % m == 0) {<br /> int sm = sum / m;<br /> while ((sm & 1) == 0) sm >>= 1;<br /> for (int k = (m & 1) == 1 ? m + 2 : m + 1, m2 = m << 1; k < m2 && k <= sm; k += 2) {<br /> if (sm % k == 0 && gcd(k, m) == 1) {<br /> int d = sum / (k * m);<br /> int n = k - m;<br /> set.add(new Triplet(d * (m * m - n * n), (d * m * n) << 1, d * (m * m + n * n)));<br /> }<br /> k += 2;<br /> }<br /> }<br /> }<br /> return set;<br />}<br />
So here is Problem's 39 code:

<br />final long time = currentTimeMillis();<br />List<Triplet> max = pythagoreanTriplet(1);<br />for (int n = 2; n <= 1000; n++) {<br /> List<Triplet> triplets = pythagoreanTriplet(n);<br /> if (triplets.size() > max.size()) max = triplets;<br />}<br />out.println(max.get(0).sum() + " : " + max + " in " + (currentTimeMillis() - time) + "ms");<br />
Solution found in 13ms:

840 : [(210,280,350), (140,336,364), (315,168,357), (252,240,348), (350,120,370), (390,56,394), (399,40,401)] in 13ms

Source code here !`

Project Euler - problem 38

Just finished Problem 38 ! We have the samples:

- 192 X (1,2,3) = 192384576

192*1=192
192*2=384
192*3 576

- 9 X (1,2,3,4,5) = 918273645

9*1=9
9*2=18
9*3=27
9*4=36
9*5=45

We call M the multiplicator we need to find.
- 918273645 is not the greatest (you can test it). So M will start with 9.
- M cannot end with 5 or 0, otherwise it will be divisible by 10 and will contain a 0 when multiplied by 2.

We know that n > 1. So for the minimal value n=2 we have:

- 9 X (1,2) => too few digits
- 98 X (1,2) => too few digits (98196)
- 987 X (1,2) => too few digits (98196294)
- 9876 X (1,2) => 9 digits (987619752) !
- 9183 X (1,2) => 9 digits (918318366) !

918273645 is not the greatest. So for a 4-digits number M, the maximum is between 9183... and 9876...

for n = 3:

- 98 X (1,2,3) => 8 digits (98196294)
- 987 X (1,2,3) => 11 digits (98719742961)
- 919 X (1,2,3) => 11 digits (91918382757)

for n = 3, when we try with the minimal number M = 919 to give a pandigital number just after 918273645, we end up with 11 digits.

So M is clearly between 9183 and 9876, and n = 2.

<br />final long time = currentTimeMillis();<br />for (int n = 9876; n >= 9183; n--) {<br /> // equivalent to 100000*n + 2*n to create the concatenation of the pandigital number <br /> final int number = (n << 5) * 3125 + (n << 1);<br /> if (n % 5 != 0 && Maths.isPandigital(number, 10)) {<br /> System.out.println(number);<br /> }<br />}<br />out.println(" in " + (currentTimeMillis() - time) + "ms");<br />
isPandigital method:

<br />/**<br /> * Check if the number is 1-n pandigital<br /> *<br /> * @param number number to check<br /> * @param n number of digits to allow (1-n)<br /> * @return true if it is pandigital from 1 to n<br /> */<br />public static boolean isPandigital(int number, int n) {<br /> int flags = 0;<br /> for (int d = 1 << (number % 10); number > 0; number /= 10, d = 1 << (number % 10)) {<br /> if ((flags & d) != 0) return false;<br /> flags |= d;<br /> }<br /> int mask = ((1 << n) - 1) ^ 1;<br /> return (flags & mask) == mask;<br />}<br />
Source code here !

Project Euler - problem 37

Problem 37 is also easy. I reused heavily the Sieve method used in previous problems and added a sieveExtend() method to extend a Sieve list to a given number of prime.

We know that sieve(8)=23 is the first truncable prime since 1x is not truncable (1 not prime).

So for each prime in the sieve list, we check its truncation from right, then from left, and if all remaining numbers are found in the sieve list then is means that the number is truncable.

<br />final long time = currentTimeMillis();<br />final TIntArrayList truncables = new TIntArrayList(11);<br />TIntArrayList sieve = Maths.sieve(1000000);<br />// sieve(8)=23 is the first truncable prime since 1x is not truncable (1 not prime)<br />for (int i = 8; truncables.size() < 11; i++) {<br /> if (i == sieve.size())<br /> sieve = Maths.sieveExtend(10000, sieve);<br /> int mask = 0;<br /> // check by truncating right first, which will give us<br /> // the number's length to truncate left after<br /> int prime = sieve.getQuick(i);<br /> boolean checkComplete = false;<br /> boolean truncable = true;<br /> for (; !checkComplete && (prime /= 10) > 0; mask++)<br /> if (sieve.binarySearch(prime) < 0)<br /> checkComplete = !(truncable = false);<br /> // - If checkComplete is true, it means the prime has already been<br /> // added to our truncate list, or it is not a truncable prime.<br /> // - If checkComplete is false, it means all truncations from right<br /> // passed the test, and we know truncate from left<br /> if (!checkComplete) {<br /> prime = sieve.getQuick(i);<br /> mask = (int) Math.pow(10, mask);<br /> for (; !checkComplete && mask >= 10; mask /= 10)<br /> if (sieve.binarySearch(prime %= mask) < 0)<br /> checkComplete = !(truncable = false);<br /> }<br /> // now we know are numner is truncable<br /> if (truncable) truncables.add(sieve.getQuick(i));<br />}<br />final int[] sum = {0};<br />truncables.forEach(new TIntProcedure() {<br /> public boolean execute(int prime) {<br /> sum[0] += prime;<br /> return true;<br /> }<br />});<br />out.println(sum[0] + " : " + truncables + " in " + (currentTimeMillis() - time) + "ms");<br />
The source code can be found here. It requires the Maths class here also.

Project Euler - problem 36

Number 36 is the one i resolved faster. By doing previous problems, we already had to implement a isPalindromic method and a reverse method. S oit was trivial adapting them to any base.

Numbers must be palindromic in base 2 and 10. It means the numbers cannot end with 0. In base 2, it means we can skip all odd numbers.

<br />int sum = 0;<br />for (int i = 1; i < 1000000; i += 2) {<br /> if(isPalindromic(i, 10) && isPalindromic(i, 2)) sum+=i;<br />}<br />
Here is the isPalindromic method:

<br />public static boolean isPalindromic(int number, int base) {<br /> return number == reverse(number, base);<br />}<br />
Here is the reverse method:

<br />public static int reverse(int number, int base) {<br /> int reverse = 0;<br /> while (number != 0) {<br /> reverse = reverse * base + number % base;<br /> number /= base;<br /> }<br /> return reverse;<br />}<br />

Project Euler - problem 35

Problem 35:

I uses the Sieve method to list all primes up to 1000000.

If a prime has one of 0, 2, 4, 5, 6 or 8, it means that a permutation of the number will end up to be divisible by 2 or 5.
So for a prime number to be circular, its digits can only be 1, 3, 7 or 9.

For each prime, we first get its digits and check if there are only 1, 3, 7 or 9.
Then we rotate its digits and check if the resulting number is in the prime list.

<br />final long time = currentTimeMillis();<br />// prime list before 1000000<br />final TIntArrayList primes = Sieve.max(1000000);<br />final TIntArrayList circulars = new TIntArrayList(primes.size());<br />// for each prime, check if it is a circular prime<br />primes.forEach(new TIntProcedure() {<br /> public boolean execute(int prime) {<br /> // for 1-digit primes, direclty ad them<br /> if (prime < 10) {<br /> circulars.add(prime);<br /> return true;<br /> }<br /> // if the prime is already in the circular list, ignore it<br /> else if (circulars.contains(prime)) return true;<br /> // for N-digits primes, check if the digits are only 1, 3, 7 or 9<br /> int length = 0;<br /> for (int num = prime; num > 0; num /= 10) {<br /> int digit = num % 10;<br /> length++;<br /> if (digit == 2 || digit == 4 || digit == 5 || digit == 6 || digit == 8) return true;<br /> }<br /> final TIntArrayList probableCircular = new TIntArrayList(length);<br /> probableCircular.add(prime);<br /> for (; length > 1; length--) {<br /> prime = rotate(prime);<br /> // if the number is prime, add it to the probable circular list if not already there<br /> if (primes.contains(prime)) {<br /> if (!probableCircular.contains(prime)) probableCircular.add(prime);<br /> }<br /> // otherwise exit and check other number<br /> else return true;<br /> }<br /> // if we are here, it means all permutations are primes. So the primes are circular.<br /> out.println(probableCircular);<br /> circulars.add(probableCircular.toNativeArray());<br /> return true;<br /> }<br />});<br />out.println(circulars);<br />out.println(circulars.size() + " in " + (currentTimeMillis() - time) + "ms");<br />
Checkoutthe source code.

Project Euler - problem 34

Number 34 of Project Euler:

Numbers of 2 digits can only be composed with [0..4] since their factorial is below 99
Combinations of 0, 1, 2 and 3 are not valid since to small
The only possibilities are numbers like ?4 and 4? where ? is in [0..4]. As the number contains 4, it will be between 14 (1!+4!=25) and 44 (4!+4!=48)

=> give a try, there is no possibility (14, 24, 34, 44, 43, 42, 41)

So our numbers begins with 3 digits

9! = 362880

So the maximum number we can product with 9! is such that length(N)*9!=N

For 7 digits: 9999999 gives 7*9!=2540160 (7 digits)
For 8 digits: 99999999 gives 8*9!=2903040 (7 digits also !)

It means that we cannot produce numbers greater than 7 digits.

The Factorion of an n-digit number cannot exceed n·9!. So the maximum to check will be 2540160.

<br />int s = 0;<br />for (int i = 100; i < 2540160; i++) {<br /> final int[] sum = new int[]{0};<br /> final int n = i;<br /> digits(i).forEach(new TIntProcedure() {<br /> public boolean execute(int digit) {<br /> sum[0] += fact(digit);<br /> return sum[0] <= n;<br /> }<br /> });<br /> if (sum[0] == n) {<br /> System.out.println(n);<br /> s += n;<br /> }<br />}<br />

Complete source code of all the Project Euler problems, plus this one here.

Project Euler - problem 33

Number 33 is really easy ! I've just solved it in less than 1 hour ;)

The numerator n=N1N0 and denominator d=D1D0 have 2 digits, and the value is less than 1. So:

10 <= n <= 98
n+1 <= d <= 99

We then must find when n and d have one digit in common, except when they are both multiples of 10 (this is the trivial case).

10/10, 10/20, ...

We also can remove all cases when at least one is a multiple of 10.
Because if n is a multiple of 10 and we find a case where d has a common digit, it will be either 0 (both multiples of 10), or 1,2,3,... and in this case the fraction value is 0. So:

11 <= n <= 98
n+1 <= d <= 99

When we found a case where there is a common digit, such as 49/98, we simply check if the fraction without the common digit gives the same value.

<br />final long time = System.currentTimeMillis();<br />int N = 1;<br />int D = 1;<br />for (float n = 11; n <= 98; n++) {<br /> float n0 = n % 10;<br /> if (n0 != 0) {<br /> float n1 = (n - n0) / 10;<br /> for (float d = n + 1; d <= 99; d++) {<br /> float d0 = d % 10;<br /> if (d0 % 10 != 0) {<br /> float d1 = (d - d0) / 10f;<br /> if (n0 == d0 && n1 != d1 && n1 / d1 == n / d) {<br /> System.out.println(n + "/" + d + "=" + n1 + "/" + d1);<br /> N *= n1;<br /> D *= d1;<br /> } else if (n1 == d0 && n0 != d1 && n0 / d1 == n / d) {<br /> System.out.println(n + "/" + d + "=" + n0 + "/" + d1);<br /> N *= n0;<br /> D *= d1;<br /> } else if (n1 == d1 && n0 != d0 && n0 / d0 == n / d) {<br /> System.out.println(n + "/" + d + "=" + n0 + "/" + d0);<br /> N *= n0;<br /> D *= d0;<br /> } else if (n0 == d1 && n1 != d0 && n1 / d0 == n / d) {<br /> System.out.println(n + "/" + d + "=" + n1 + "/" + d0);<br /> N *= n1;<br /> D *= d0;<br /> }<br /> }<br /> }<br /> }<br />}<br />int gcd = Maths.gcd(N, D);<br />System.out.println((N / gcd) + "/" + (D / gcd) + " in " + (System.currentTimeMillis() - time) + "ms");<br />

Project Euler - problem 32

It's been a while since i did not have time to play a little ;) Project's Euler number 32 is a sort of problem that can be solve by checking all possibilities through code, but with a little thinking we can improve the range to check. Here is how:

We try to find which combination can produce 9 digits from 1 to 9.

9*8=72 (4 digits)
9*87=783 (6 digits)
9*876=7884 (8 digits)
9*1234=11106 (10 digits)
8*1234=9872 (9 digits)

So a digit from 1 to 8 multiplied by a 4-digit number can give a 4-digit number

98*76=7448 (8 digits)
98*765=74970 (10 digits)
12*345=4140 (9 digits)

So we must also check 2-digit numbers multiplied by 3-digit numbers

Here is an optimized Java code version:

<br />final long time = System.currentTimeMillis();<br />final TIntHashSet products = new TIntHashSet();<br />final BitSet bitSet = new BitSet(9);<br />// 1-digit number by a 4-digit number<br />for (int i = 1234; i <= 9876; i++) {<br /> for (int j = 1; j <= 8; j++) {<br /> int prd = i * j;<br /> if (prd >= 1234 && prd <= 9876) {<br /> bitSet.clear();<br /> if (forEachDigit(i * 100000 + j * 10000 + prd, new TIntProcedure() {<br /> public boolean execute(int value) {<br /> if (value == 0) return false;<br /> if (bitSet.get(value - 1)) return false;<br /> bitSet.set(value - 1);<br /> return true;<br /> }<br /> })) products.add(prd);<br /> }<br /> }<br />}<br />// 2-digit number by a 3-digit number<br />for (int i = 123; i <= 987; i++) {<br /> for (int j = 12; j <= 98; j++) {<br /> int prd = i * j;<br /> if (prd >= 1234 && prd <= 9876) {<br /> bitSet.clear();<br /> if (forEachDigit(i * 1000000 + j * 10000 + prd, new TIntProcedure() {<br /> public boolean execute(int value) {<br /> if (value == 0) return false;<br /> if (bitSet.get(value - 1)) return false;<br /> bitSet.set(value - 1);<br /> return true;<br /> }<br /> })) products.add(prd);<br /> }<br /> }<br />}<br />int sum = 0;<br />TIntIterator it = products.iterator();<br />while(it.hasNext()) sum+=it.next();<br />System.out.println(sum + " in " + (System.currentTimeMillis() - time) + "ms");<br />
* I'm using GNU trove, which is a Java Collection API which work directly with primitives to avoid boxing and unboxing.
* I'm using a BitSet, to check for repeating digits to avoid doing string transforming and doing unnecessary tasks
* The forEachDigit method is simply implemented like this:

<br />public static boolean forEachDigit(int number, TIntProcedure procedure) {<br /> do {<br /> if(!procedure.execute(number % 10)) return false;<br /> }<br /> while ((number /= 10) > 0);<br /> return true;<br />}<br />

Project Euler - problem 31

Problem 31 of Project Euler:

The monetary base is composed of 8 multiplicand:

200=200*a+100*b+50*c+20*d+10*e+5*f+2*g+1*h

We can already have a counter started at 2, when a = 1, when a = 0 and b = 2. So we find the remaining possibilities like this:

<br />long time = System.currentTimeMillis();<br />int count = 2; // for a = 1, a = 0 and b = 2`<br />for (int b = 0; b <= 1; b++)<br /> for (int c = 0; 100 * b + 50 * c <= 200; c++)<br /> for (int d = 0; 100 * b + 50 * c + 20 * d <= 200; d++)<br /> for (int e = 0; 100 * b + 50 * c + 20 * d + 10 * e <= 200; e++)<br /> for (int f = 0; 100 * b + 50 * c + 20 * d + 10 * e + 5 * f <= 200; f++)<br /> for (int g = 0; 100 * b + 50 * c + 20 * d + 10 * e + 5 * f + 2 * g <= 200; g++)<br /> count++;<br />System.out.println(count + " in " + (System.currentTimeMillis() - time) + "ms");<br />

Project Euler - Problem 30

Number 30 is really easy. I didn't have time to play since this evening and got it now !
We must find the sum of the numbers N = abc...z = a^5 + b^5 + ... + z^5
If n has 1 digit, there is no possible sum. Thus, N has at least 2 digits.
To find the maximum value, we check when the sum of the biggest possible digits is not the expected number of digits.
Example:

• 3 digits numbers will be found by checking from
  1^5 + 0^5 + 0^5 to 9^5 + 9^5 + 9^5 = 177147
• 4 digits numbers will be found by checking from
  1 to 9^5 + 9^5 + 9^5 + 9^5 = 236196
• 5 digits numbers will be found by checking from
  1 to 9^5 + 9^5 + 9^5 + 9^5 + 9^5 = 295245
• 6 digits numbers will be found by checking from
  1 to 9^5 + 9^5 + 9^5 + 9^5 + 9^5 + 9^5 = 354294 (354294 is 6 digits long)
• 7 digits numbers will be found by checking from
  1 to 9^5 + 9^5 + 9^5 + 9^5 + 9^5 + 9^5 + 9^5 = 413343
  

Oups ! 413343 is 6 digits long. So it means that even if we have the maximum digit value 9, we cannot have any number composed of 7 digits with powers of 5.

So we will check numbers from 100 to 354294.

<br />long time = System.currentTimeMillis();<br />int[] powers = new int[10];<br />for (int i = 0; i < 10; i++) powers[i] = (int) Math.pow(i, 5);<br />int res = 0;<br />for (int i = 100; i <= 354294; i++) {<br /> int powsum = 0;<br /> for (int q = i; q > 0; q = q / 10) powsum += powers[q % 10];<br /> if (i == powsum) res += i;<br />}<br />System.out.println(res + " in " + (System.currentTimeMillis() - time) + "ms");<br />