Optimization of the digital algorithm <= 2 (similar to Project Euler 303)

Question

I am creating a program to solve Project Euler Problem 303 My method for finding f(n) hardly brute force:

 static BigInteger findFn(int n){ Long Fn = new Long(n); String test = Fn.toString(); Long multiplier = new Long("1"); long counter = 0; boolean done = false; BigInteger fn = new BigInteger("0"); while(!done){ counter = 0; BigInteger tempOne = new BigInteger(multiplier.toString()); BigInteger tempTwo = new BigInteger(Fn.toString()); BigInteger product = tempOne.multiply(tempTwo); test = product.toString(); for(int i = 0; i < test.toString().length(); i++){ if(Character.getNumericValue(test.toString().charAt(i)) <= 2){ counter++; }else{ //Is it better to set done = true here as opposed to breaking? break; //breaks if it encounters any number in the multiple >2. } } if(counter == test.length()){ fn = product; done = true; break; } multiplier++; } return fn; } 

Works well on most rooms, but there are a few (usually those ending in 9) that it just got stuck. I think BigIntegers slows this down, so firstly, is there somewhere where I used BigInteger where it is not needed? Secondly, there should be an alternative method or some other trick to reduce the number of loops that I did not think about. Any thoughts to give me a push in the right direction?

Thanks!!

Answer 1

I think that you could cut 67% of your trials just by looking at a number in one place on the tested number, because if it does not happen before 0, 1 or 2, then it doesn’t matter what the others go.

Note that if the number ends with 1, then the number that it multiplies must end with 0, 1 or 2 so that the last digit of the result is <= 2. Thus, you check 1 then 2, and if they do not work, then you test 10, 11, 12, then 20, 21, 22. So, if the test number ends with 1, you have now reduced your tests by 70%.

For XXX2, the multiplier will have to end at 0, 1, 5, or 6. This will remove 60%. You can continue for 3-9.

Answer 2

How about trying a different way?

I solved this problem by creating numbers consisting of 0, 1, and 2 from smallest to largest, and looking at whom this number is a multiple of. Moreover, I used the template for 9, 99, etc. (By the way, you don’t need BigInteger different from them. Since you precompute them, get rid of BigInteger), but I found their values ​​similar to your bruteforce method, increasing the multiplicity of the number of interest, as mentioned earlier. The result popped up after about 6 seconds. If you want to see my solution, here .

Answer 3

test is a string, so there is no need to call it toString() . Not a big improvement, but it makes the code a little cleaner.

Above my head, here is an algorithm that BigInteger completely avoided.

 For each multiplier Set carry = 0 Set multiple = "" Iterate through the digits of the multiplier from right to left Set temp = digit * n + carry if (right-most digit of temp > 2) break and go to next multiplier else Set carry = temp / 10 // drop last digit and carry result 

This basically makes a long multiplication with the ability to break out of it as soon as the number> 2 is found. Note that to solve the problem we really do not need to get F(n) , just F(n)/n , which is the first factor, for which the previous iteration of digits is completed. Then just sum the smallest factor for each n .

Without trying to do this, I am sure that this will only work with int values.

Update

So, I played with some code and got it to work 1 <= n <= 100 . It looks like a factor for n = 999 > 2 ^ 31, so we need to use at least 64-bit values. Not sure what a multiplier is. My code has been working in LinqPad for over 21 minutes and passed 3.2 * 10 ^ 9 with no result. Of course, there might be a problem with my code.

Answer 4

Try to keep the results as you move forward. You can use them to make reduced guesses for your multiples.

Suppose that an acceptable LCM for some X is Y, with Y = RX. Then you know that Y is also lower for all {X, 2X, 3X, 4X, ... (R-1) X}.

Answer 5

Not sure if the following idea will help:

• Let P(N, M) = the digits of M base 10 are (<= 2) and M multiple of N
• Let G(N) = Some M such that P(N, M) .

• Let F(N) = M such that P(N, M) and M minimal.

  Important Note: F(N) <= G(N) .

  I would like G(N) be "reasonable" in the sense that it is not gratuitously large and is easily calculated. Perhaps you can efficiently recoup it by using F(N') for the smaller components of N' of N ( N digits possible).

  Knowing G(N) can be extremely useful ... Perhaps you can work with it in the opposite direction. Perhaps you can do some kind of binary search with it.

  If this technique is generally useful, I suggest that hard mathematics should find G(N) . The rest would probably be some kind of clever technique in computer technology.

Answer 6

To reduce the number of iterations, you can increase the trial product by 1, instead of increasing the trial factor by 1. Then you check if the trial product is divided by the argument f (). This will allow you to quickly move to larger values, since you can skip the numeric values ​​4 through 9 in the product when adding 1.

Below, the C code ends in less than 5 minutes on a 2.4 GHz PC:

 #include <stdio.h> #include <string.h> #include <assert.h> #include <stddef.h> #include <time.h> typedef unsigned uint; typedef unsigned char uint8; typedef unsigned long long uint64; uint64 f(uint n, uint64* multiplier) { uint8 carry, digits[20]; // 20 digits max for 64-bit values uint digcnt = 1, i; uint64 result; assert(n > 0); #if 0 // short cut: // // f(9) = 12222 = 9 * 1358 // f(99) = 1122222222 = 99 * 11335578 // f(999) = 111222222222222 = 999 * 111333555778 // f(9999) = 11112222222222222222 = 9999 * 1111333355557778 if (n == 9999) { *multiplier = 11112222222222222222ULL / 9999; return 11112222222222222222ULL; } #endif memset(digits, 0, sizeof(digits)); for (;;) { carry = 1; for (i = 0; carry; i++) { assert(i < sizeof(digits)); carry += digits[i]; digits[i] = carry % 3; carry /= 3; } if (i >= digcnt) digcnt = i; result = 0; for (i = 0; i < digcnt; i++) result = result * 10 + digits[digcnt - 1 - i]; if (result % n == 0) { *multiplier = result / n; break; } } return result; } int main(void) { uint i; uint64 sum = 0, product, multiplier; time_t t; char* p; for (i = 1; i <= 10000; i++) { product = f(i, &multiplier); printf("%s ", ((time(&t), p = ctime(&t)), p[strlen(p) - 1] = '\0', p)); printf("f(%u) = %llu = %u * %llu\n", i, product, i, multiplier); sum += multiplier; } printf("%s ", ((time(&t), p = ctime(&t)), p[strlen(p) - 1] = '\0', p)); printf("sum(f(n)/n) = %llu\n", sum); return 0; } 

Output:

 Mon Jan 9 12:18:22 2012 f(1) = 1 = 1 * 1 Mon Jan 9 12:18:22 2012 f(2) = 2 = 2 * 1 Mon Jan 9 12:18:22 2012 f(3) = 12 = 3 * 4 Mon Jan 9 12:18:22 2012 f(4) = 12 = 4 * 3 Mon Jan 9 12:18:22 2012 f(5) = 10 = 5 * 2 Mon Jan 9 12:18:22 2012 f(6) = 12 = 6 * 2 Mon Jan 9 12:18:22 2012 f(7) = 21 = 7 * 3 Mon Jan 9 12:18:22 2012 f(8) = 112 = 8 * 14 Mon Jan 9 12:18:22 2012 f(9) = 12222 = 9 * 1358 ... Mon Jan 9 12:18:39 2012 f(9998) = 111122211112 = 9998 * 11114444 Mon Jan 9 12:22:50 2012 f(9999) = 11112222222222222222 = 9999 * 1111333355557778 Mon Jan 9 12:22:50 2012 f(10000) = 10000 = 10000 * 1 Mon Jan 9 12:22:50 2012 sum(f(n)/n) = 1111981904675169 

If you change #if 0 to #if 1 and turn on the short cut mentioned in Peter Laurie's comment, it will end in about 1 minute.

Answer 7

Here is my contribution to this interesting issue. Forgive me for using Java and BigInteger, but based on my testing, I was not such a blocker (the calculated sum [1, 100] takes less than a second and the sum [1, 10000] is about 4.5 million on my 2.4 dual core). And out of these 4+ minutes, about 4 minutes is spent on f (9999). Pretty unexpected.

 import java.math.BigInteger; public class Main { public static void main(String args[]) { BigInteger result = BigInteger.ZERO; for (int i = 1; i <= 10000; ++i) { BigInteger r = f(BigInteger.valueOf(i)); System.out.println("i=" + i + " r=" + r); result = result.add(r.divide(BigInteger.valueOf(i))); } System.out.println("result=" + result); } // Find smallest x * value which consists only of numbers {0, 1, 2}. private static BigInteger f(BigInteger value) { BigInteger retVal = value; while (!check(retVal)) { BigInteger remainder = remainder(retVal); BigInteger mult = remainder.subtract(retVal.remainder(remainder)) .divide(value); retVal = retVal.add(value.multiply(mult.max(BigInteger.ONE))); } return retVal; } // Find highest remainder for given value so that value % retVal = // XYYYYY.. Where X > 2 and 0 <= Y <= 9. private static BigInteger remainder(BigInteger value) { BigInteger curVal = BigInteger.TEN; BigInteger retVal = BigInteger.TEN; while (value.compareTo(BigInteger.TEN) >= 0) { curVal = curVal.multiply(BigInteger.TEN); value = value.divide(BigInteger.TEN); if (value.remainder(BigInteger.TEN).intValue() > 2) { retVal = curVal; } } return retVal; } // Check if given value contains only 0, 1 and 2. private static boolean check(BigInteger value) { do { if (value.remainder(BigInteger.TEN).intValue() > 2) { return false; } value = value.divide(BigInteger.TEN); } while (value.compareTo(BigInteger.ZERO) == 1); return true; } }