October 24th, 2017 at 4:54:05 PM
permalink

The problem with brute force is, you have to do 13 multiplications in each step. Mine starts with 13, then does a multiplication and a division in each step - that is, until the 13th digit is a zero, at which point you know the next 13 products will all be zero, so you can skip ahead 13 digits.

October 24th, 2017 at 5:14:18 PM
permalink

Quote:ThatDonGuyThe problem with brute force is, you have to do 13 multiplications in each step. Mine starts with 13, then does a multiplication and a division in each step - that is, until the 13th digit is a zero, at which point you know the next 13 products will all be zero, so you can skip ahead 13 digits.

Yea, I realize brute force isn’t the best. Skipping once hitting a 0 is probably the most optimial, trying to wrack my brain for something better and not thinking of anything.

October 24th, 2017 at 7:17:02 PM
permalink

Quote:ThatDonGuyThe problem with brute force is, you have to do 13 multiplications in each step. Mine starts with 13, then does a multiplication and a division in each step - that is, until the 13th digit is a zero, at which point you know the next 13 products will all be zero, so you can skip ahead 13 digits.

If you are optimizing for speed it would probably be quicker to do addition and subtraction instead of the multiplication and division.

October 25th, 2017 at 1:31:14 AM
permalink

You can optimize a bit by not bothering to check if the next number is smaller than the number rolling off the back of the 13 digit number. ie when going from 9876543219876 to 8765432198765 you don't have to check. the problem is when you then have an increase you have to multiply the skipped digits again, but I;m sure something clever could be done to make it worth the optimization.

October 25th, 2017 at 2:15:46 AM
permalink

I'd think step one would be to split the 1000 digit number by 0's and make an array. Ignore arrays (or sets?) with fewer than 13 digits.

If there are 13 numbers in a set, multiply them all, and you're done for that set. If there are 14, then compare digit #1 with #14. If 1 is larger than 14, then your numbers are 1-13. If 14 is larger then 2-14.

If there are 15 numbers, then you know digits 3-13 must exist in the biggest number thingie. Multiply 1 and 2, 2 and 14, 14 and 15. Whichever product is highest, that set of 2 is going to be in the biggest 13.

If there are 16 digits, then all EXCEPT the first three and final three numbers are needed. Mutiply 1,2,3 and 2,3,14 and 3,14,15 and 14,15,16. Highest product will be the answer (for that set).

Of course this gets a bit cumbersome, perhaps, when you start to get many more digits. And once you get to like 25 or 26 digits, it doesn't work anymore. Although I suppose you could break it up into a few smaller arrays (so, three 17 digit arrays or so?).

If any set's first or last number is a 1, it can be ignored, assuming the +13'th number isn't also a 1. Maybe.

After all this nonsense, you're left with a bunch of sets of 13 which are possibilities to be the highest, but you've also removed a majority of the original 988 sets.

Of the remaining sets, you rearrange the numbers from lowest to highest. Get rid of all the 1s, since multiplying by 1 obviously does nothing, AFAIK. :)

Think I just pooped my pants but I'll edit this or make. New reply.

If there are 13 numbers in a set, multiply them all, and you're done for that set. If there are 14, then compare digit #1 with #14. If 1 is larger than 14, then your numbers are 1-13. If 14 is larger then 2-14.

If there are 15 numbers, then you know digits 3-13 must exist in the biggest number thingie. Multiply 1 and 2, 2 and 14, 14 and 15. Whichever product is highest, that set of 2 is going to be in the biggest 13.

If there are 16 digits, then all EXCEPT the first three and final three numbers are needed. Mutiply 1,2,3 and 2,3,14 and 3,14,15 and 14,15,16. Highest product will be the answer (for that set).

Of course this gets a bit cumbersome, perhaps, when you start to get many more digits. And once you get to like 25 or 26 digits, it doesn't work anymore. Although I suppose you could break it up into a few smaller arrays (so, three 17 digit arrays or so?).

If any set's first or last number is a 1, it can be ignored, assuming the +13'th number isn't also a 1. Maybe.

After all this nonsense, you're left with a bunch of sets of 13 which are possibilities to be the highest, but you've also removed a majority of the original 988 sets.

Of the remaining sets, you rearrange the numbers from lowest to highest. Get rid of all the 1s, since multiplying by 1 obviously does nothing, AFAIK. :)

Think I just pooped my pants but I'll edit this or make. New reply.

00111100101100001011011100110101101100101011001010010000001101111011100110110001101100001011100100010000001101100011010010110110101100001001000000110111101110011011000110110000101110010

October 25th, 2017 at 2:39:32 AM
permalink

Okay that was a false alarm, all's good, thank you for your concerns.

Actually I'm not really sure what I'd do next. And I guess part of my assumption (which probably isn't good) is that the computer would be getting bogged down by such big numbers and that was part of the "optimization" game (sorta like 9^(9^9) problem)......turns out 9^13 isn't all that big. =\

Actually I'm not really sure what I'd do next. And I guess part of my assumption (which probably isn't good) is that the computer would be getting bogged down by such big numbers and that was part of the "optimization" game (sorta like 9^(9^9) problem)......turns out 9^13 isn't all that big. =\

00111100101100001011011100110101101100101011001010010000001101111011100110110001101100001011100100010000001101100011010010110110101100001001000000110111101110011011000110110000101110010

October 25th, 2017 at 4:35:25 AM
permalink

I never did well in classes where we had to figure out the time-complexity of algorithms, but my general understanding is that time-complexity increases with the amount of decisions a algorithm has to make.

I'm thinking the simple 0 check is best way about this, so I'm going to post another challenge, but if anyone thinks of something better for any of these please post.

Challenge #3

A little more maths in this one, and I do not think it can be brute forced in any reasonable amount of time.

I'm thinking the simple 0 check is best way about this, so I'm going to post another challenge, but if anyone thinks of something better for any of these please post.

Challenge #3

A little more maths in this one, and I do not think it can be brute forced in any reasonable amount of time.

The sequence of triangle numbers is generated by adding the natural numbers.

So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1

3: 1,3

6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

October 25th, 2017 at 6:18:49 AM
permalink

T(12375) = 76,576,500 = 2

Each divisor is the product of {1, 2, 4} {1, 3, 9} {1, 5, 25, 125} {1, 7} {1, 11} {1, 13} {1. 17}

The number of factors a positive integer N has = (P(2) + 1) (P(3) + 1) (P(5) + 1) (P(7) + 1) P((11) + 1)...

where P(K) is the number of times the prime K appears in N's prime factorization

For example, 25,200 = 2

// This assumes int Primes[] is defined as a constant array of all primes < 10,000

int PrimesCount = Primes.Length;

int[] Factors = new int[PrimesCount];

int FactorCount = 0;

int TCount = 1;

int T = 1;

// int P;

while (FactorCount < 500)

{

for (N = 0; N < PrimesCount; N++)

{

Factors[N] = 1;

}

TCount++;

T += TCount;

N = T;

for (P = 0; Primes[P] * Primes[P] <= N; P++)

{

while (N % Primes[P] == 0)

{

Factors[P]++;

N /= Primes[P];

}

}

for (P = 0; P < PrimesCount && Primes[P] != N; P++) ;

if (P < PrimesCount)

{

Factors[P]++;

}

FactorCount = 1;

for (N = 0; N < PrimesCount; N++)

{

FactorCount *= Factors[N];

}

}

October 25th, 2017 at 6:20:54 AM
permalink

For challenge #2, since multiplication is commutative shouldn't the largest sum of the sequence of 13 numbers with no zeros also be the largest product? Is there any point in doing any multilpication?

October 25th, 2017 at 6:29:35 AM
permalink

Quote:DRichFor challenge #2, since multiplication is commutative shouldn't the largest sum of the sequence of 13 numbers with no zeros also be the largest product? Is there any point in doing any multilpication?

9991111111111 has product 729 and sum 37

2222222222222 has product 8192 and sum 26