## 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
cloaknsmoke
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
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.
hk
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### 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.
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 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.
hk
Posts: 11040
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

### Re: 149 clarification

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
Posts: 3441
Joined: Sun Mar 05, 2006 4:49 pm
Location: Cheshire, England
Contact:

### Re: 149 clarification

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?
jdrandall123
Posts: 65
Joined: Sun Mar 26, 2006 11:57 am
Location: New York, USA

### Re: 149 clarification

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

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
jdrandall123
Posts: 65
Joined: Sun Mar 26, 2006 11:57 am
Location: New York, USA

### Re: 149 clarification

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.
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

### Re: Problem 149

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

### 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 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;.
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

### Re: Problem 149

Oh my, how could I overlook that 200003k
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

Jochen_P wrote:Oh my, how could I overlook that 200003k
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;.
Jochen_P
Posts: 55
Joined: Mon Oct 05, 2009 10:47 am
Location: Stuttgart, Germany

### Re: Problem 149

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

### Re: Problem 149

daniel.is.fischer wrote:
Jochen_P wrote:Oh my, how could I overlook that 200003k
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.
zwuupeape
Posts: 189
Joined: Tue Jun 09, 2009 6:11 pm

### Re: Problem 149

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

### Re: Problem 149

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.
LarryBlake
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.
Fogmeister
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