2

I'm sorry for my bad english. English is not my main language.

I've been trying to study this and its patterns for a while. You can see this in many ways, but the first way I saw this was from a geometrical point of view. I saw this as convexes polygons. Firstly you'll say it has $n$ vertices, and display them from $0$ to $n-1$ in any direction. Then you'll go the vertex of the position you are $+1$, then $+2$, then $+3$ and so on.
For example let's say that $n=5$. Then You'll have: $$ -\:\: 0\:\: 1\:\: 2\:\: 3\:\: 4 $$ You start from $0$, then go to $0+1= 1$, then you go to $1+2 = 3$ etc.

Then you go to $3+3 = 6$. Note that if you represent this as a polygon you go back to $1$, since $$6 ≡ 1 \mod 5.$$

Eventually, if you keep doing these modulo sums, it results in a total of 3 vertices that you've passed through: 0,1,3. And lets put ${V(5) = 3}$.

Here's something I coded

The first thing I noticed was that $2^n$ polygons they reached all vertices.
Somehow the $n=2$ case is special. If, for example, you want to know $$ V(6) = V(2) \cdot V(3). $$ and $V(2)=2$
Multiplication seems working when you use even numbers. Another example: $$V(34) = 18,\quad V(17\cdot2) = V(17) \cdot V(2),$$ and $V(17) = 9$.
That might be the reason that $2^n$ polygons reach all vertices, since $V(2^n)$ is obtained as the $n$-fold product of $V(2)$ by itself. So its reasonable that it reaches all vertices.
Can anyone please help me find a better explanation and help me to dig this out?

Also, what if I need to calculate $V(n)$ when $n$ is odd? What's the way or expression to get there?

If you're confused, this might help. https://prnt.sc/pitus0

Palaomath
  • 21

1 Answers1

1

The vertex numbers you find are all in the series $$0+1+2+3+... +k=\frac{k(k+1)}{2},$$

when considered modulo $n$.

If $n$ is an odd prime

The sum can be written as $\frac{1}{2}(k+\frac{1}{2})^2-\frac{1}{8}$ and the number of these modulo $n$ is the same as the number of squares i.e. $V(n)=\frac{n+1}{2}.$

Did you find that was always the case?

If $n$ is any odd number

By the proof given above, the answer is still the number of squares modulo $n$ and the easiest way of finding these is given by sequence https://oeis.org/A000224.

If $n$ is a power of 2

You have spotted a really interesting result that every integer can be written in the form $\frac{k(k+1)}{2}$ modulo such an $n$.

This can be proved by showing that for $0\le k<l\le n-1$ the two expressions $\frac{k(k+1)}{2}$ and $\frac{l(l+1)}{2}$ are different modulo $n$. We will then have $n$ different numbers of this form which is what we want.

The proof is to consider $$X=\frac{l(l+1)}{2}-\frac{k(k+1)}{2}=\frac{(l-k)(l+k+1)}{2}$$

Now only one of $l-k$ and $l+k+1$ can be even and so, for X to be $0$ modulo $n$, $2n$ must divide either $l-k$ or $l+k+1$. However, both these numbers are greater than $0$ but less than $2n$. Hence we do have have $n$ different numbers of the required form.

  • I'm sorry, I didn't follow. What is with these numbers of squares you said? – Palaomath Oct 14 '19 at 00:43
  • Are you familiar with modular arithmetic? –  Oct 14 '19 at 00:45
  • yeah but I'm kinda rusty. I've studied it a long time ago – Palaomath Oct 14 '19 at 00:52
  • You have spotted really interesting results but you do need to know some modular arithmetic results to prove your results. For odd prime $n$ I have used the fact that a lot is known about what numbers can be expressed as squares modulo n. It turns out that precisely half of the non-zero remainders modulo $n$ can be so expressed, together with 0 this means we can express (n+1)/2 remainders as squares. Your result about powers of 2 is also a great result. I will add a proof above but you might need to study some more modular arithmetic before considering it. See how it goes. –  Oct 14 '19 at 00:58
  • Sure man, thanks. – Palaomath Oct 14 '19 at 01:34
  • @S.Dolan This is a fairly small point, but to make it easier for people to check on any mentioned use of OEIS, you should include an explicit link, e.g., https://oeis.org/A000224 , instead of just stating it like you did, i.e., "sequence A000224 in the OEIS", perhaps by having something like the "A000224" text be an appropriate hyperlink. – John Omielan Oct 14 '19 at 05:17
  • 1
    Yes, I've done this now. –  Oct 14 '19 at 12:23