Project Euler Forum

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?

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

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 ??

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$.