Problem 750

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
deWalk
Posts: 4
Joined: Sun Oct 11, 2015 8:23 pm

Problem 750

Post by deWalk »

Just wondering: "Note: G(N) is not defined for all values of N."
How can that be?

G(N) is the minimal drag distance.
Now *if* the numbers in the initial arrangement, when sorted, form a sequence without gaps and double values, it clearly is possible to drag them around to finally form one stack (just drag the [1] on the [2], then the [1+2] on the [3] and so on).
So there exists a candidate and upper bound for G(N) , and therefore also G(N).

The only thing I can think of, is that this suspect sequence: $ 3^n\bmod(N+1), 1\le n\le N $
may produce double values or gaps?
brob26
Posts: 9
Joined: Thu Nov 22, 2018 3:48 am

Re: Problem 750

Post by brob26 »

deWalk wrote: Sun Mar 07, 2021 12:05 amThe only thing I can think of, is that this suspect sequence: $ 3^n\bmod(N+1), 1\le n\le N $
may produce double values or gaps?
Nailed it
Image
deWalk
Posts: 4
Joined: Sun Oct 11, 2015 8:23 pm

Re: Problem 750

Post by deWalk »

Ah, I see, basic number theory, cycle length of $ 3^k\bmod M , k=0,1,... $ should be $ M-1 $ (where M=N+1):

For this M may not contain a factor 3 -
then Euler's theorem tells us that $ \phi(M) $ is a upper bound (multiple) of cycle length,
and $ \phi(M) = M-1 $ iff M is prime.

So for G(N) to be defined, a necessary condition is that M=N+1 is prime.
But what about a sufficient condition ?? :?
brob26
Posts: 9
Joined: Thu Nov 22, 2018 3:48 am

Re: Problem 750

Post by brob26 »

deWalk wrote: Sun Mar 07, 2021 9:29 pm Ah, I see, basic number theory, cycle length of $ 3^k\bmod M , k=0,1,... $ should be $ M-1 $ (where M=N+1):

For this M may not contain a factor 3 -
then Euler's theorem tells us that $ \phi(M) $ is a upper bound (multiple) of cycle length,
and $ \phi(M) = M-1 $ iff M is prime.

So for G(N) to be defined, a necessary condition is that M=N+1 is prime.
But what about a sufficient condition ?? :?
You're correct that $N+1$ must be prime.

The extra condition that needs satisfying is $3$ to be a generator of the multiplicative group mod $(N+1)$, which holds iff $3^{N/p} \not\equiv 1 \mod (N+1)$ for all prime factors $p$ of $N$.
Image
Post Reply