Problem 148

[3n1gm4]

Help me understand my mistake please

First 7 rows, there are 28 number not divisible by 7 on a total of 28
First 8 rows, there are 30 number not divisible by 7 on a total of 36
First 9 rows, there are 34 number not divisible by 7 on a total of 45
First 10 rows, there are 40 number not divisible by 7 on a total of 55
First 20 rows, there are 153 number not divisible by 7 on a total of 210
First 30 rows, there are 305 number not divisible by 7 on a total of 465
First 40 rows, there are 549 number not divisible by 7 on a total of 820
First 50 rows, there are 876 number not divisible by 7 on a total of 1275
First 60 rows, there are 1236 number not divisible by 7 on a total of 1830
First 70 rows, there are 1689 number not divisible by 7 on a total of 2485
First 80 rows, there are 2272 number not divisible by 7 on a total of 3240
First 90 rows, there are 2964 number not divisible by 7 on a total of 4095
First 100 rows, there are 3729 number not divisible by 7 on a total of 5050

These are few rows:
Row 7 [1, 7, 21, 35, 35, 21, 7, 1]
Row 8 [1, 8, 28, 56, 70, 56, 28, 8, 1]
Row 9 [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

The result for Row 100 is wrong (because the right one is in the examples), do you see any mistake in my rows?

[stijn263]

First 7 rows, there are 28 number not divisible by 7 on a total of 28
First 8 rows, there are 30 number not divisible by 7 on a total of 36
First 9 rows, there are 34 number not divisible by 7 on a total of 45
First 10 rows, there are 40 number not divisible by 7 on a total of 55
First 20 rows, there are 147 number not divisible by 7 on a total of 210
.
.
First 100 rows, there are 2361 number not divisible by 7 on a total of 5050

Apart from row 7-10, you got them all wrong

[3n1gm4]

Yes I'm looking at more rows now, the ending number is 0, don't know why... anyway generating row by row should not be the way, I think...there are too large numbers uhm... there should be an other way, thank you

[elr]

for some reason my answer does not accepted

the answer i getting for the problem limit (1 billion) begin with 1632....

for 100 rows i getting 2361
for 1000 rows i getting 167727
and for 10000 rows i getting 16395490

can someone verify my 1000,10000 answers or provide example for number of rows other than 100 (as at the problem page) ?

[daniel.is.fischer]

100 rows is correct, 1000 and 10000 not (both too high).
I suspect overflow.

[elr]

i manage to find some bug at my code and fixed now i getting :


1000 -> 118335
10000 -> 9573240
1000000 -> 93311603424
10000000 -> 9329607230440

however still my answer does not accepted

is it possible to have a valid example for limit other than 100 ?

[daniel.is.fischer]

1000 is correct, the others not.
For 7500 rows, the answer is 3753960.

[elr]

thanks alot i have manage to solve it
i realy enjoyed this problem

[estanford]

Would anyone mind doing me a huge favor and checking what the answer is for all the rows up to the 847425746th? I have a few versions of my current algorithm, and they give me different answers depending on which assumptions I make about certain relevant algebraic structures.


EDIT: I just realized that row count is perilously close to 10^9. I'd originally calculated it as the wrong number, much lower than its true value. I'll just run my brute force attack the rest of the way and use that to supplement my partial, and be back with more questions if there are still any errors.

[LarryBlake]

elr, I see that I have been making exactly the same mistakes you have. I think I'm on the right track now...

And yes, this is a very nice problem.

[bobfin]

Hi I seem to have hit the wall on this one. I've used two algorithms. First a brute force job that attemps to examine each row entry. This breaks down arround row 50 with overflow and won't be used to solve the problem but does provide a check on my second algorithm which simply calculates row totals. Results are consistent upto row 40 which gives me some confidence but my second algorithm fails with the row 100 check.
Can anyone verify the following:
First 7 rows, there are 28 numbers not divisible by 7 on a total of 28
First 8 rows, there are 30 numbers not divisible by 7 on a total of 36
First 9 rows, there are 34 numbers not divisible by 7 on a total of 45
First 10 rows, there are 40 numbers not divisible by 7 on a total of 55
First 20 rows, there are 147 numbers not divisible by 7 on a total of 210
First 30 rows, there are 295 numbers not divisible by 7 on a total of 465
First 40 rows, there are 510 numbers not divisible by 7 on a total of 820
First 50 rows, there are 792 numbers not divisible by 7 on a total of 1275
First 60 rows, there are 1098 numbers not divisible by 7 on a total of 1830
First 70 rows, there are 1540 numbers not divisible by 7 on a total of 2485
First 80 rows, there are 1920 numbers not divisible by 7 on a total of 3240
First 90 rows, there are 2457 numbers not divisible by 7 on a total of 4095
First 100 rows, there are 2985 numbers not divisible by 7 on a total of 5050 - wrong should be 2361

[jaap]

50 is the first incorrect one (should be 786), so I guess your second method also has overflow issues.

[bobfin]

Thanks for identifying first incorrect result. Second algorithm didn't correctly deal with the evolving patterns but has been fixed now.

[WhiteDemon]

Hi, everyone. My first post here.

I think I have the correct solution but turns out there is an issue with my solution as it is not being accepted.

Here are the solutions for the first x rows where y is the no. of entries not divisible by 7. I don't know if there is any other way I can find the bug in my solution

x = 1000, y = number removed
x = 10000, y = number removed
x = 100000, y = number removed
x = 1000000, y = number removed
x = 10000000, y = number removed

My solution is in python and I have confirmed my answers for many values. Since the solution is not accepted, the error is probably due to the high x value.

[sjhillier]

Hi, everyone. My first post here.

I think I have the correct solution but turns out there is an issue with my solution as it is not being accepted.

My solution is in python and I have confirmed my answers for many values. Since the solution is not accepted, the error is probably due to the high x value.

Welcome. I've removed the numbers since it's giving away a little too much information to others. The examples in PE problem statements are carefully chosen to be helpful, but not too helpful!

I am however prepared to reveal that you are very much on the right track. As you have guessed, the problem is almost certainly something to do with numerical accuracy with the higher numbers. I don't use python much, so can't help you much with number storage limitations and overflows in that language, but that is likely to be the area to look at.

[whatteaux]

As you have guessed, the problem is almost certainly something to do with numerical accuracy with the higher numbers. I don't use python much, so can't help you much with number storage limitations and overflows in that language, but that is likely to be the area to look at.

Firstly, Python has no upper limit to its integer numeric values and never overflows (i.e. built-in, automatic, "BigIntegers"), so one might need to look at the algorithm rather than numeric representation problems.

Secondly, my Java and c# versions of this one don't use BigIntegers - simple 'long' is big enough - so my Python version doesn't use its auto BigIntegers anyway (and finishes in under a millisecond).

[hk]

It seems that you have solved the problem, so no need to go further into this matter.