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

Don't post any spoilers
Comments, questions and clarifications about PE problems.
Eventhorizon
Posts: 19
Joined: Fri Sep 23, 2011 2:16 am

Problem 445

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
mdean
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 445

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

Re: Problem 445

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?
TheEvil
Posts: 84
Joined: Sun Nov 13, 2011 10:38 am
Location: Szeged, Hungary

Re: Problem 445

Yes, the identity map is always a retraction.
Eventhorizon
Posts: 19
Joined: Fri Sep 23, 2011 2:16 am

Re: Problem 445

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!
ironman353
Posts: 11
Joined: Thu Jan 16, 2014 2:29 pm

Re: Problem 445

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

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.
ironman353
Posts: 11
Joined: Thu Jan 16, 2014 2:29 pm

Re: Problem 445

thundre,
Thanks for your reply. I have checked the test values of problem 446 and 447 now.
mdean
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 445

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.
Hossein
Posts: 2
Joined: Sat Aug 06, 2016 2:55 pm

Re: Problem 445

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" ?
jaap
Posts: 554
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 445

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?