ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 71
  • Posts: 3177
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.
gamerfreak
gamerfreak
Joined: Dec 28, 2014
  • Threads: 34
  • Posts: 1434
October 24th, 2017 at 5:14:18 PM permalink
Quote: ThatDonGuy

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.


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.
DRich
DRich
Joined: Jul 6, 2012
  • Threads: 64
  • Posts: 3428
October 24th, 2017 at 7:17:02 PM permalink
Quote: ThatDonGuy

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.



If you are optimizing for speed it would probably be quicker to do addition and subtraction instead of the multiplication and division.
someone
someone
Joined: Nov 9, 2014
  • Threads: 0
  • Posts: 31
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.
RS
RS
Joined: Feb 11, 2014
  • Threads: 51
  • Posts: 5999
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.
00111100101100001011011100110101101100101011001010010000001101111011100110110001101100001011100100010000001101100011010010110110101100001001000000110111101110011011000110110000101110010
RS
RS
Joined: Feb 11, 2014
  • Threads: 51
  • Posts: 5999
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. =\
00111100101100001011011100110101101100101011001010010000001101111011100110110001101100001011100100010000001101100011010010110110101100001001000000110111101110011011000110110000101110010
gamerfreak
gamerfreak
Joined: Dec 28, 2014
  • Threads: 34
  • Posts: 1434
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.
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?
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 71
  • Posts: 3177
October 25th, 2017 at 6:18:49 AM permalink

T(12375) = 76,576,500 = 22 x 32 53 x 7 x 11 x 13 x 17 has 576 divisors
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 = 24 x 32 x 52 x 7, so P(2) = 4, P(3) = 2, P(5) = 2, P(7) = 1, and P(N) = 0 for all other primes


// 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];
}
}

DRich
DRich
Joined: Jul 6, 2012
  • Threads: 64
  • Posts: 3428
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?
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 71
  • Posts: 3177
October 25th, 2017 at 6:29:35 AM permalink
Quote: DRich

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?


9991111111111 has product 729 and sum 37
2222222222222 has product 8192 and sum 26

  • Jump to: