Problem 445

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
Eventhorizon
Posts: 19
Joined: Fri Sep 23, 2011 2:16 am

Problem 445

Post by Eventhorizon »

I think I just don't get modular arithmetic! I would like to get a better understanding without spoiling this problem so I will try baby steps. Can someone verify the following chain of logic:

Consider n=12, a=10, b=3 and x=6
f(x) = (10.6 + 3) mod 12 = 63 mod 12 = 3
f(f(x)) = f(3) = (10.3 + 3) mod 12 = 33 mod 12 = 9

Conclusion: {n=12, a=10, b=3} cannot be retractive because f(f(x)) != f(x) for x=6
Image

mdean
Posts: 165
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 445

Post by mdean »

Eventhorizon wrote:I think I just don't get modular arithmetic! I would like to get a better understanding without spoiling this problem so I will try baby steps. Can someone verify the following chain of logic:

Consider n=12, a=10, b=3 and x=6
f(x) = (10.6 + 3) mod 12 = 63 mod 12 = 3
f(f(x)) = f(3) = (10.3 + 3) mod 12 = 33 mod 12 = 9

Conclusion: {n=12, a=10, b=3} cannot be retractive because f(f(x)) != f(x) for x=6
What you have looks correct.
Image

Eventhorizon
Posts: 19
Joined: Fri Sep 23, 2011 2:16 am

Re: Problem 445

Post by Eventhorizon »

Thank you mdean. Next step (I assume the following is so trivial as not to be a spoiler) ...

a=1 and b=0 => f(x) = x mod n
x <= n, so
f(x) = x when 0 <= x < n and
f(x) = 0 when x =n

Therefore, f(f(x)) = f(x) for all integer values of x, 0 <= x <= n.

i.e. f(x) is a retraction for all sets {n, a=1, b=0}

Am I right so far?
Image

User avatar
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 445

Post by TheEvil »

Yes, the identity map is always a retraction.
Image

Eventhorizon
Posts: 19
Joined: Fri Sep 23, 2011 2:16 am

Re: Problem 445

Post by Eventhorizon »

Last step, some more interesting retractions:

{n=6, a=3, b=0} is a retraction because
f(0) = 0 => f(f(0)) = f(0) = 0 and f(2) = f(4) = 0
f(3) = 3 => f(f(3)) = f(3) = 3 and f(1) = f(5) = 3

{n=6, a=4, b=3} is a retraction because
f(0) = 0 => f(f(0)) = f(0) = 0 and f(3) = 0
f(2) = 2 => f(f(2)) = f(2) = 2 and f(5) = 2
f(4) = 4 => f(f(4)) = f(4) = 4 and f(1) = 4

So a pattern begins to emerge - I needed to work a little harder with pencil and paper!
Thanks for the replies - they helped!
Image

ironman353
Posts: 11
Joined: Thu Jan 16, 2014 2:29 pm

Re: Problem 445

Post by ironman353 »

It is given in the problem that ∑ R(c) for c=C(100 000,k), and 1 ≤ k ≤99 999 ≡628701600 (mod 1 000 000 007).
My brute force program is unable to get it. Can anyone confirm for some smaller limits?
∑ R(c) for c = 1 to c = 100 is 1839.

thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 445

Post by thundre »

ironman353 wrote:It is given in the problem that ∑ R(c) for c=C(100 000,k), and 1 ≤ k ≤99 999 ≡628701600 (mod 1 000 000 007).
My brute force program is unable to get it. Can anyone confirm for some smaller limits?
∑ R(c) for c = 1 to c = 100 is 1839.
1839 is correct.

Problems 446 and 447 are about the same R function. You can look at them for addtional test values.
Image

ironman353
Posts: 11
Joined: Thu Jan 16, 2014 2:29 pm

Re: Problem 445

Post by ironman353 »

thundre,
Thanks for your reply. I have checked the test values of problem 446 and 447 now.

mdean
Posts: 165
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 445

Post by mdean »

I can't seem to get the given result. If I replace 100,000 with 10, the answer appears to be correct. Can I pm someone this value just to confirm it's correct?

Update: Never mind. Caught a mistake for $\binom{20}3$. Found a "1" where there should have been an "i". Now I just need to figure out how to speed it up. Currently takes about 20 seconds for 100,000. 10,000,000 is going to take quite a while.
Image

Hossein
Posts: 2
Joined: Sat Aug 06, 2016 2:55 pm

Re: Problem 445

Post by Hossein »

1)The problem states : "f(a,b,n) is retraction if ... " . Does it mean :" f(a,b,n) for x is retraction if ..." ?
2) Suppose "the retraction for n" is known. Now, what is the definition of " the number of retractions for n" ?

User avatar
jaap
Posts: 551
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 445

Post by jaap »

Hossein wrote:1)The problem states : "f(a,b,n) is retraction if ... " . Does it mean :" f(a,b,n) for x is retraction if ..." ?
For any a,b,n, we have a function fa,b,n. It is a function of x. Being a retraction is a property of the function as a whole.
Hossein wrote:2) Suppose "the retraction for n" is known. Now, what is the definition of " the number of retractions for n" ?
You are misreading it.
For a given value of n, we can choose any value of 0<=a,b<n to get a function fa,b,n. There are n*n choices for these values of a,b so there are n*n of these functions. How many of them have this property of being a retraction?

Post Reply