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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
cloaknsmoke
Posts: 1
Joined: Sun Jul 01, 2007 11:47 pm

Problem 149

Post by cloaknsmoke »

The term "modulo" can mean different things depending on the circumstances or language. My question is which specific version of modulo is this question refering to?
User avatar
euler
Administrator
Posts: 3441
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

Re: 149 clarification

Post by euler »

I'm intrigued, what is your language and what are the alternative meanings?

As far as I know there is only one meaning in English, certainly in the context it is presented. Modulo refers to the operation of taking remainders. For example, 17 [cong] 3 mod 7.

But generally it's always a good idea to check, as there can be nothing more frustrating than investing several hours on a problem with a misplaced interpretation.
User avatar
hk
Administrator
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: 149 clarification

Post by hk »

I'm not sure but I think with "language" is meant: programming language.
Programming languages differ how they handle n mod m when either n or m or both are less than zero.
In this problem we have taken care that that should not happen. If it does another data type for k must be used as k^3 has overflowed.
Image
User avatar
jdrandall123
Posts: 65
Joined: Sun Mar 26, 2006 11:57 am
Location: New York, USA

Re: 149 clarification

Post by jdrandall123 »

Euler: I am afraid I disagree with you on this one: in mathematics, mod n defines an equivalence relation; in computer science. it defines a function.

In math, a=b (mod n) means n divides a-b. This is an equivalence relation on the integers. For example, if n=2, the equivalence classes are the odd and even integers. When a computer language says 3 mod 2=1, it is picking a representative for that equivalence class. Different languages will pick different slightly different representatives.

As hk says, problem 149 has no ambiguity if you choose your representatives mod n to be 0,....,n-1. I don't get the point about overflow: surely this is an implementation detail rather than the mathematics of the problem.
User avatar
hk
Administrator
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: 149 clarification

Post by hk »

jdrandall123 wrote: I don't get the point about overflow: surely this is an implementation detail rather than the mathematics of the problem.
The other day we had a participant that asked about this problem and did not realise k^3 exceeds 32 bit integer capacity.
I thought perhaps this question was inspired by such an error.
Image
User avatar
euler
Administrator
Posts: 3441
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

Re: 149 clarification

Post by euler »

jdrandall123 wrote:Euler: I am afraid I disagree with you on this one: in mathematics, mod n defines an equivalence relation; in computer science. it defines a function.
I'm not quite sure how you are disagreeing?

Certainly in computing, mod(x,n) is a function that strictly means the mapping of x on to a single member of the complete residue system {0, 1, 2, ... , n-1}. In mathematics it can be used in two ways: (i) an equivalence relation: x [cong] y mod n iff (x-y)|n, or, (ii) the modulo operator: x mod n = y, where 0 [le] y < n; sometimes referred to as the fifth rule of arithmetic: add (1+2=3), subtract (5-3=2), multiply (2*4=8), divide (12/3=4), and modulo (11%7=4).

But even with the first usage, it is the same as testing equality of x and y when they are both mapped to members of the residue class modulo n; for example, 18 [cong] 11 mod 7 because 18 [cong] 4 and 11 [cong] 4, and this could be further expressed with equality using the operator rather than congruence as 18 mod 7 = 11 mod 7.

In other words, there is nothing not encompassed in my "generic" explanation of modulo: the operation of taking remainders.

However, after now contemplating this further I can better appreciate the significance of the question that was being asked. So I wonder if the wording needs to be modified to make it absolutely clear that we are referring to the operator form?
User avatar
jdrandall123
Posts: 65
Joined: Sun Mar 26, 2006 11:57 am
Location: New York, USA

Re: 149 clarification

Post by jdrandall123 »

euler wrote:Certainly in computing, mod(x,n) is a function that strictly means the mapping of x on to a single member of the complete residue system {0, 1, 2, ... , n-1}.
This is what I am disagreeing with. Languages agree on the value of mod(x,n) when x>=0 and n>0. If either is negative, some languages give a value of mod(x,n) in the range -|n|,...,0, depending on the signs, and there is no consistency across languages. I think this is what the original poster meant.
mfh
Posts: 2
Joined: Fri Jul 13, 2007 2:26 pm

Re: 149 clarification

Post by mfh »

euler wrote:Certainly in computing, mod(x,n) is a function that strictly means the mapping of x on to a single member of the complete residue system {0, 1, 2, ... , n-1}. In mathematics it can be used in two ways: (i) an equivalence relation: x [cong] y mod n iff (x-y)|n, or, (ii) the modulo operator: x mod n = y, where 0 [le] y < n
ad (i) : you mean n | (x-y)

ad (ii) : in maple, the result of " a mod b " equals `mod`(a,b) where (the global / environment(?) variable) "mod" must be set either to modp (default) or to mods (often preferrable),
where modp maps into [0,...,b) and mods maps into (-b/2,b/2].
IMHO there is not any reason to treat the case of integer b differently from the general case.
AFAIK, especially for b=2pi, the "mods" convention is at least as common as the "modp" convention.

PS: however, I never heared of a mod function mapping into (-n,0]... - although this is a conceivable possibility for the "remainder upon division" of a or by a negative number.

PPS: all that said, returning to the initial subject, in general I think its a nice idea to keep the chosen style of leaving the statement of problems somehow imprecise, provided the intended meaning can be guessed e.g. from given examples
User avatar
jdrandall123
Posts: 65
Joined: Sun Mar 26, 2006 11:57 am
Location: New York, USA

Re: 149 clarification

Post by jdrandall123 »

mfh wrote: PS: however, I never heared of a mod function mapping into (-n,0]... - although this is a conceivable possibility for the "remainder upon division" of a or by a negative number.
See http://www.lysator.liu.se/c/bwk-tutor.html#arithmetic.
User avatar
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

Re: Problem 149

Post by Jochen_P »

I got wrong results with my LFG implementation. S10 is 407000 here and not as the description states -393027 ...
I guess that has got something to do with the fact that I don't understood the meaning of the square brackets

[100003 - 200003k + 300007k3]

What do they indicate?
Image
elr
Posts: 67
Joined: Thu Apr 09, 2009 9:47 am

Re: Problem 149

Post by elr »

they doesn't have any special meanings they just normal brackets
Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 149

Post by daniel.is.fischer »

It's unlikely that the wrong result for S10 is caused by overflow in this case. But if you forgot to multiply 200003 by k, you would get exactly the wrong result you did.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
User avatar
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

Re: Problem 149

Post by Jochen_P »

Oh my, how could I overlook that 200003k :shock:
Thanx Daniel, it now generates the expected results :oops:
Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 149

Post by daniel.is.fischer »

Jochen_P wrote:Oh my, how could I overlook that 200003k :shock:
That's easy. All you need to do is start thinking about the algorithm before carefully and completely reading the spec.
Il faut respecter la montagne -- c'est pourquoi les gypa&egrave;tes sont l&agrave;.
User avatar
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

Re: Problem 149

Post by Jochen_P »

What proofs once more that males aren't capable of multitasking :D
Image
quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: Problem 149

Post by quilan »

daniel.is.fischer wrote:
Jochen_P wrote:Oh my, how could I overlook that 200003k :shock:
That's easy. All you need to do is start thinking about the algorithm before carefully and completely reading the spec.
I'm well acquainted with that... I fully completed both Problem 189 (View Problem) and Problem 167 (View Problem) in a completely & utterly incorrect manner (i.e. solved a WAY harder problem) before I finally re-read the problem description & instantly solved the proper way.
ex ~100%'er... until the gf came along.
Image
zwuupeape
Posts: 189
Joined: Tue Jun 09, 2009 6:11 pm

Re: Problem 149

Post by zwuupeape »

What harder problem have you solved for 189 ?
quilan
Posts: 182
Joined: Fri Aug 03, 2007 11:08 pm

Re: Problem 149

Post by quilan »

zwuupeape wrote:What harder problem have you solved for 189 ?
Solving for the number, if rotations / mirrors were actually non-distinct patterns. Basically, the pattern X, when rotated 60* was the same as X in my solving. This leads to (of course) a much smaller number number than the correct answer as many patterns are reflections / rotations of others. It took me a solid month to finally finish the algorithm for the harder problem before I tried it as the answer and (shock!) it didn't work... I took 5 minutes to re-read carefully the problem statement, and realized that I'd solved the correct problem on the first day. I was actually thrown off by that one line into thinking it was harder than it should have been.
ex ~100%'er... until the gf came along.
Image
LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Re: Problem 149

Post by LarryBlake »

I'm loading the LFG numbers into an array that starts with an index of zero. I do get array[10] = -393027 and array[100] = 86613, but that means that I'm really looking at the 11th and 101st numbers. Am I doing it correctly?

EDIT: Now that I reread the problem, I'm sure I'm not. Never mind. :oops:
Image
Fogmeister
Posts: 27
Joined: Mon Aug 22, 2011 11:20 am

Re: Problem 149

Post by Fogmeister »

What sort of run times are people getting for this?

I though I had quite a good algorithm set up but it going to take well over 1 minute.

Maybe around 5 or 6 minutes I think?

And I'm not 100% certain that it's correct either :?
Image
Post Reply