Problem 148

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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
3n1gm4
Posts: 34
Joined: Sun Jul 20, 2008 1:46 pm

Problem 148

Post by 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?
User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problem #148

Post by 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
Posts: 34
Joined: Sun Jul 20, 2008 1:46 pm

Re: Problem #148

Post by 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
Posts: 67
Joined: Thu Apr 09, 2009 9:47 am

Re: Problem 148

Post by 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) ?
Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 148

Post by daniel.is.fischer »

100 rows is correct, 1000 and 10000 not (both too high).
I suspect overflow.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
elr
Posts: 67
Joined: Thu Apr 09, 2009 9:47 am

Re: Problem 148

Post by 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 ?
Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 148

Post by daniel.is.fischer »

1000 is correct, the others not.
For 7500 rows, the answer is 3753960.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
elr
Posts: 67
Joined: Thu Apr 09, 2009 9:47 am

Re: Problem 148

Post by elr »

thanks alot i have manage to solve it :)
i realy enjoyed this problem
Image
estanford
Posts: 10
Joined: Sun Sep 13, 2009 12:06 pm

Re: Problem 148

Post by 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
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Re: Problem 148

Post by 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. :)
Image
bobfin
Posts: 9
Joined: Thu Oct 22, 2009 7:06 am

Re: Problem 148

Post by 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
User avatar
jaap
Posts: 555
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 148

Post by jaap »

50 is the first incorrect one (should be 786), so I guess your second method also has overflow issues.
bobfin
Posts: 9
Joined: Thu Oct 22, 2009 7:06 am

Re: Problem 148

Post by bobfin »

Thanks for identifying first incorrect result. Second algorithm didn't correctly deal with the evolving patterns but has been fixed now.
WhiteDemon
Posts: 1
Joined: Sun Mar 05, 2017 2:54 pm

Re: Problem 148

Post by 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.
User avatar
sjhillier
Administrator
Posts: 558
Joined: Sun Aug 17, 2014 4:59 pm
Location: Birmingham, UK
Contact:

Re: Problem 148

Post by sjhillier »

WhiteDemon wrote: Sun Mar 05, 2017 3:24 pm 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
Posts: 7
Joined: Mon Sep 24, 2012 11:58 am

Re: Problem 148

Post by whatteaux »

sjhillier wrote: Sun Mar 05, 2017 8:16 pmAs 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).
User avatar
hk
Administrator
Posts: 11113
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 148

Post by hk »

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