Problem 149
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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 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.

 Posts: 1
 Joined: Sun Jul 01, 2007 11:47 pm
Problem 149
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?
 euler
 Administrator
 Posts: 3441
 Joined: Sun Mar 05, 2006 4:49 pm
 Location: Cheshire, England
 Contact:
Re: 149 clarification
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.
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.
Re: 149 clarification
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.
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.
 jdrandall123
 Posts: 65
 Joined: Sun Mar 26, 2006 11:57 am
 Location: New York, USA
Re: 149 clarification
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 ab. 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,....,n1. I don't get the point about overflow: surely this is an implementation detail rather than the mathematics of the problem.
In math, a=b (mod n) means n divides ab. 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,....,n1. I don't get the point about overflow: surely this is an implementation detail rather than the mathematics of the problem.
Re: 149 clarification
The other day we had a participant that asked about this problem and did not realise k^3 exceeds 32 bit integer capacity.jdrandall123 wrote: I don't get the point about overflow: surely this is an implementation detail rather than the mathematics of the problem.
I thought perhaps this question was inspired by such an error.
 euler
 Administrator
 Posts: 3441
 Joined: Sun Mar 05, 2006 4:49 pm
 Location: Cheshire, England
 Contact:
Re: 149 clarification
I'm not quite sure how you are disagreeing?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.
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, ... , n1}. In mathematics it can be used in two ways: (i) an equivalence relation: x [cong] y mod n iff (xy)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 (53=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?
 jdrandall123
 Posts: 65
 Joined: Sun Mar 26, 2006 11:57 am
 Location: New York, USA
Re: 149 clarification
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.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, ... , n1}.
Re: 149 clarification
ad (i) : you mean n  (xy)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, ... , n1}. In mathematics it can be used in two ways: (i) an equivalence relation: x [cong] y mod n iff (xy)n, or, (ii) the modulo operator: x mod n = y, where 0 [le] y < n
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
 jdrandall123
 Posts: 65
 Joined: Sun Mar 26, 2006 11:57 am
 Location: New York, USA
Re: 149 clarification
See http://www.lysator.liu.se/c/bwktutor.html#arithmetic.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.
Re: Problem 149
I got wrong results with my LFG implementation. S_{10} 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 + 300007k^{3}]
What do they indicate?
I guess that has got something to do with the fact that I don't understood the meaning of the square brackets
[100003  200003k + 300007k^{3}]
What do they indicate?
Re: Problem 149
they doesn't have any special meanings they just normal brackets
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 11:15 pm
 Location: Bremen, Germany
Re: Problem 149
It's unlikely that the wrong result for S_{10} 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ètes sont là.
Re: Problem 149
Oh my, how could I overlook that 200003k
Thanx Daniel, it now generates the expected results
Thanx Daniel, it now generates the expected results
 daniel.is.fischer
 Posts: 2400
 Joined: Sun Sep 02, 2007 11:15 pm
 Location: Bremen, Germany
Re: Problem 149
That's easy. All you need to do is start thinking about the algorithm before carefully and completely reading the spec.Jochen_P wrote:Oh my, how could I overlook that 200003k
Il faut respecter la montagne  c'est pourquoi les gypaètes sont là.
Re: Problem 149
What proofs once more that males aren't capable of multitasking
Re: Problem 149
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 reread the problem description & instantly solved the proper way.daniel.is.fischer wrote:That's easy. All you need to do is start thinking about the algorithm before carefully and completely reading the spec.Jochen_P wrote:Oh my, how could I overlook that 200003k
ex ~100%'er... until the gf came along.
Re: Problem 149
What harder problem have you solved for 189 ?
Re: Problem 149
Solving for the number, if rotations / mirrors were actually nondistinct 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 reread 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.zwuupeape wrote:What harder problem have you solved for 189 ?
ex ~100%'er... until the gf came along.

 Posts: 100
 Joined: Sat Aug 29, 2009 8:49 pm
Re: Problem 149
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.
EDIT: Now that I reread the problem, I'm sure I'm not. Never mind.

 Posts: 27
 Joined: Mon Aug 22, 2011 11:20 am
Re: Problem 149
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
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