## Problem 149

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
Fogmeister
Posts: 27
Joined: Mon Aug 22, 2011 11:20 am

### Re: Problem 149

Woop!

I was doing something stupid in my algorithm!

Fixed it now after much debugging with the 4x4 grid and it ran and gave me the correct answer in 1.7 seconds

mdean
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

### Re: Problem 149

Well, this problem's going to be a pain to troubleshoot. I may have to comment out most of my program, look at just a corner (maybe 20x20), and add a ton of test code to handle just this corner (which hopefully doesn't introduce different errors...).

Update: All right, finally got back to it. So far, it seems my horizontal and vertical sums are working correctly. I'm testing on the upper left 10x10 square (seems if I print in landscape, 10 numbers is about all that will fit per row...). So either I fouled up on the diagonals or mucked up a limit somewhere...
cska
Posts: 5
Joined: Thu Apr 19, 2012 5:40 pm

### Re: Problem 149

Can you check my results and tell which are wrong:
max in rows: 13414319
max in columns: 11593776
max in anti-diagonals: 10284763
max in diagonals: 10785046
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

### Re: Problem 149

Those numbers are all too low.
find the greatest sum of (any number of) adjacent entries
Are you limiting yourself to whole rows/columns/diagonals? Because many numbers in the table are negative, the maximum sum of adjacent numbers in a row is often greater than the sum of the entire row.
cska
Posts: 5
Joined: Thu Apr 19, 2012 5:40 pm

### Re: Problem 149

I'm not. I also tested my algorithm with few smaller cases and manually checked results and they seemed to be correct, e.g., table:
11  16  -8  -9  10   7
3   8   0  -9  -8  -6
-4  -3  -2  -8 -10 -20
8   6  10 -20   7   3
1   2   7   8   6  10
-4   2  -3   2  -8   7
results:
max in rows: 34
max in columns: 31
max in anti-diagonals: 19
max in diagonals: 25
Can you check these?
mdean
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

### Re: Problem 149

Based on what I can see, those values look correct. Does your algorithm work for this row?

5 -3 1 -2 5
cska
Posts: 5
Joined: Thu Apr 19, 2012 5:40 pm

### Re: Problem 149

No it wasn't, I had to modify my code to handle such cases correctly.. Thanks a lot.
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### Re: Problem 149

I've been trying to squeeze the correct values out of that LFG. I am getting s[10] correctly, but for some weird reason s[100] is always -357419. I don't think there's an overflow. What could possibly go wrong with s[k] = ((s[k-24] + s[k-55] + 1000000) mod 1000000) - 500000?

Could someone be so kind and confirm or decline
s[17] = 134343,
s[55] = -1343089,
s[1000] = 355076,
s[123456] = -1414215?
49.157.5694.1125
mpiotte
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm

### Re: Problem 149

leghorn wrote:.. What could possibly go wrong with s[k] = ((s[k-24] + s[k-55] + 1000000) mod 1000000) - 500000? ...
What would you say is the range a valid values for s[k]? Are all your values in this range?
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### Re: Problem 149

It's like this in Pascal.

Code: Select all

const MAX_LENGTH = 4000000;

var s: array of longint;
k: longint;

begin
setlength(s, MAX_LENGTH+1);
{ LFG: fill array }
for k := 1 to 55 do
s[k] := ((100003 - 200003*k + 300007*k*k*k) mod 1000000) - 500000;
for k := 56 to MAX_LENGTH do
s[k] := ((s[k-24] + s[k-55] + 1000000) mod 1000000) - 500000;
end.
I don't think I'm giving anything else away but the things which are already in the description. Though I can't seem to locate the error
49.157.5694.1125
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 4:54 pm
Contact:

### Re: Problem 149

Are your values of s[10] and s[100] correct?
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### Re: Problem 149

Alas, no.
I am getting s[10] correctly, but for some weird reason s[100] is always -357419.
I just don't see what I might be missing...

I've also tested things in D:

Code: Select all

import std.stdio, std.algorithm, std.container;

immutable uint MAX_LENGTH = 4_000_000;

int main()
{
uint k;
long j;

/* fill array */
long[] s = new long[MAX_LENGTH+1]; s[0] = 0;

for (k = 1; k < 56; k++)
{
j = (100_003 - 200_003*k + 300_007*k*k*k) % 1_000_000;
s[k] = j - 500_000;
}

for (k = 56; k <= MAX_LENGTH; k++)
{
j = (s[k-24] + s[k-55] + 1_000_000) % 1_000_000;
s[k] = j - 500_000;
}

return 0;
}
That also gives s[10] correctly = -393027, but s[100] is incorrect with -422827.

Weird stuff that even s[100]@Pascal and s[100]@D are different although the calculations are basically the same.
49.157.5694.1125
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 149

leghorn wrote:I've been trying to squeeze the correct values out of that LFG. I am getting s[10] correctly, but for some weird reason s[100] is always -357419. I don't think there's an overflow. What could possibly go wrong with s[k] = ((s[k-24] + s[k-55] + 1000000) mod 1000000) - 500000?

Could someone be so kind and confirm or decline
s[17] = 134343,
s[55] = -1343089,
s[1000] = 355076,
s[123456] = -1414215?
There is an overflow. These are the numbers you get if you use signed 32bit integers everywhere, but for example 300007*k*k*k already overflows for k>24.
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### Re: Problem 149

Once again you saved my day, jaap!

I'd mistaken the compiler to internally use maximum precision, but I failed.
49.157.5694.1125
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### Re: Problem 149

Since I've read that in several publications... Do you, too, consider the maximum subsequence sum = 0 if all items in that sequence are < 0?
cska wrote:Can you check my results and tell which are wrong:
max in rows: 13414319
max in columns: 11593776
max in anti-diagonals: 10284763
max in diagonals: 10785046
Speaking of rows, I get xxxx2415. Sound reasonable?
49.157.5694.1125
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

### Re: Problem 149

Never mind. I think I've worked it out...
49.157.5694.1125
mscha
Posts: 6
Joined: Sat Jan 21, 2017 9:55 pm

### Problem 149

For $56 ≤ k ≤ 4000000$, $s_k = [s_{k−24} + s_{k−55} + 1000000] (modulo 1000000) − 500000.$
What's the point of adding a million, modulo one million?
hk