y amigos

Question

Podemos ver que en el sistema decimal de cada uno de $12345679\times k$ $(k\in\mathbb N, k\lt 81, k\ \text{is coprime to $9$})$ (nota! no $123456789$) tiene cada número de $0$ $9$a excepción de un número como sus números de dos dígitos .

$$12345679\times 2=[0]24691358$$ $$12345679\times 4=[0]49382716$$ $$12345679\times 5=[0]61728395$$ $$12345679\times 7=[0]86419753$$ $$12345679\times 8=[0]98765432$$ $$12345679\times 10=123456790$$ $$\vdots$$ $$12345679\times 77=950617283$$ $$12345679\times 79=975308641$$ $$12345679\times 80=987654320$$ $$(12345679\times 82=1012345678)$$

He estado pensando acerca de su generalización.

Aquí está mi pregunta.

Pregunta : Es el siguiente proposición es verdadera?

La proposición : Vamos a $n\ge2\in\mathbb Z.$ cualquier $k\in\mathbb N$ tal que $k\lt n^2$ $k$ es coprime a $n$, si tenemos en cuenta $$[1,2,3,\cdots, (n-3),(n-2),n]_{n+1}\times k$$ como un número con $n$-dígitos en base $n+1$, entonces tiene cada número de $0$ $n$a excepción de un número como sus números de dos dígitos, donde $$[1,2,3,\cdots, (n-3),(n-2),n]_{n+1}$$ representa a $123\cdots(n-3)(n-2)n$ base $n+1$.

Ejemplo : Los ejemplos en la parte superior son las $n=9$ de los casos de la proposición.

Comentario : Supongamos que el $n$-ésimo número de dígitos de un número con $n-1$ dígitos es $0$.

Por ejemplo, supongamos que tratamos $$12345679\times 2=24691358$$ como $$12345679\times 2=[0]24691358.$$

Motivación : yo he conocido a la siguiente :

$$12345679\times 9=111111111$$ $$12345679\times 18=222222222$$ $$\vdots$$ $$12345679\times 72=888888888$$ $$12345679\times 81=999999999$$

Entonces, me encontré con que la propiedad en la parte superior ya ha sido conocido.

A pesar de que he tratado de demostrar que la proposición es verdadera, me estoy enfrentando dificultades. ¿Alguien puede probar o refutar?

P. S. $1$ :

Antes he publicado esta pregunta en matemáticas de desbordamiento, pero fue considerado como off-topic. Sin embargo, recibí comentarios de S. Carnahan allí.

"No se trata simplemente de una manifestación de la base de $n+1$ expansión de $1/n^2$?"

"Asumimos $k\lt n$, ya que la adición de $j/n$ sólo añade copias de $j$, conservando el patrón. La progresión de un dígito a la siguiente de la expansión es la suma de la $k$ fib el próximo dígito no tiene llevar, y $k+1$ fib el próximo dígito tiene un transporte. El símbolo $n−k$ es necesariamente omitido, y no hay prematuro periodicidad (ya que el orden multiplicativo de a $n+1$ mod $n^2$ sin cambios). "

Yo creo que estos comentarios deben ser cierto, pero estos no son evidentes para mí.

P. S. $2$ :

Voy a escribir la prueba de la $k\lt n$ de los casos para obtener más consejos de usted. Esto es debido a que estoy en la dificultad de probar la siguiente aunque creo que la prueba de la $k\lt n$ de los casos estaría bien.

Lo que no puedo probar es : Si la proposición es verdadera para $k\lt n$, entonces es cierto para $n\lt k\lt n^2.$

(Aunque esto puede ser obvio, no puedo llegar a una rigurosa prueba de ello...por favor hágamelo saber.)

En la siguiente, voy a escribir la prueba de la $k\lt n$ de los casos.

Prueba : en Primer lugar, se utiliza el siguiente hecho (por supuesto, la prueba es necesaria, pero es fácil de probar).

Hecho : $[1,2,3,\cdots,(n-3),(n-1),n]\times n=[1,1,1,\cdots, 1,1,1]$ (con $n$ $1$s)

El uso de este hecho, podemos ver $$\begin{align}[1,2,3,\cdots, (n-3),(n-2),n]\times k&=[1,1,1,\cdots,1,1,1]\div n\times k\\&=[1,1,1,\cdots,1,1,1]\times k\div n\\&=[k,k,k,\cdots,k,k,k]\div n.\end{align}$$

En la siguiente, vamos a considerar en mod $n$.

Podemos ver que los restos en el proceso de cálculo de $$[k,k,k,\cdots,k,k,k]\div n$$ son $$k,2k,3k,\cdots,(n-1)k,nk(\equiv 0).$$ Desde $k$ es coprime a $n$, podemos ver fácilmente que no es $i\not=j\ (1\le i,j\le n-1)$ tal que $$ik\equiv jk.$$ Esto lleva inmediatamente que la respuesta para $$[k,k,k,\cdots,k,k,k]\div n$$ tiene diferentes números como números de dos dígitos. Q. E. D.

P. S. $3$ : Ahora tengo una pregunta.

Puedo decir lo siguiente en el último paso de la prueba de arriba? Pensé que era obvio, pero ahora siento que esto no parece obvio...

"Esto lleva inmediatamente que la respuesta para $$[k,k,k,\cdots,k,k,k]\div n$$ tiene diferentes números como números de dos dígitos."

Answer 1

Como la persona de Matemáticas de Desbordamiento dio a entender, tu pregunta se ve mejor en el paradigma de la base de $n$ expansión de $1/(n-1)^2$.

Considere la siguiente suma: $\displaystyle \sum_{k=1}^\infty \frac{k}{n^{k+1}}$. Esto es igual a $\displaystyle \frac{1}{n^2} + \frac{2}{n^3} + \frac{3}{n^4} + \frac{4}{n^5} + \cdots$ hacia el infinito, que es a su vez igual a $\displaystyle \frac{n}{(n-1)^2}$.

El número de $1n^{n-3} + 2n^{n-4} + 3n^{n-5} + \cdots + (n-3)n^1 + (n-1)$) (que es $12345679$ base $10$) es simplemente esta expansión multiplicado por $n^{n-2}$, para producir $\displaystyle \frac{n^{n-1}}{(n-1)^2}$, y, a continuación, truncando la parte decimal. Así que, ya que sólo estamos cambiando de lugares decimales, echemos un vistazo a lo que sucede sólo en el caso de $\displaystyle \frac{1}{(n-1)^2}$ porque es más fácil trabajar con.

En el caso de $\displaystyle \frac{1}{(n-1)^2}$, la expansión en base a $n$ es igual a $$ \frac{1}{n^2} + \frac{2}{n^3} + \frac{3}{n^4} + \frac{4}{n^5} + \cdots + \frac{n-1}{n^{n}} + \frac{n}{n^{n+1}} + \cdots$$

Now, here's an example of that in action in base 10:

0.0 1 2 3 4 5 6 7 9 0 1 2 3 ...
  0       4       8     1 2  ...
    1       5       9     1 3 ...
      2       6     1 0        ...
        3       7     1 1       ...

You'll notice that the tens digit of 10 butts into the place value of the ones digit of 9, causing a carry over and increasing the value of 8 in that place to 9.

For multiples of $\displaystyle \frac{1}{(n-1)^2}$ = $\displaystyle \frac{k}{(n-1)^2}$ , the same deal applies only in multiples. For $k = 2$, for example, $\displaystyle \frac{2}{(n-1)^2}$ is just equal to:

$$ \frac{2}{n^2} + \frac{4}{n^3} + \frac{6}{n^4} + \frac{8}{n^5} + \cdots + \frac{2(n-1)}{n^{n}} + \frac{2n}{n^{n+1}} + \cdots$$

All that changes is that the numbers being added as place values go into two digits more quickly.

0.0 2 4 6 9 1 3 5 8 0 2 4 6 ...
  0       8     1 6     2 4  ...
    2     1 0     1 8     2 6 ...
      4     1 2     2 0        ...
        6     1 4     2 2       ...

Notice that the digit increases by $2$ each time now, except when the tens digit of the next number increases by $1$, in which case it increases by $3$.

Also notice that there is no $7 (= 9 - 2)$ in this expansion, just as there was no $8(= 9 - 1)$ in the first one. This is because when you try to get $7$ (e.g. with the $6$ in $16$ + the $1$ in $18$), the $2$ in $20$ butts in and forces the $7$ to carry again, increasing it to $8$.

This basically means that whenever the ones digit would become a number that's $7$ or greater, it increases by $3$ rather than $2$. But that just means that we can treat $7$ as skipped entirely, and in fact we're actually always just moving $2$ steps forward in the cyclic sequence $0, 1, 2, 3, 4, 5, 6, 8, 9$.

And this applies in general, for $k/(n-1^2)$, we're moving $k$ steps forward in the sequence $[0, 1, 2, 3, 4, 5, 6, \cdots, n-1]$ with $(n - 1 - k)$ removed. This "trick" even works with numbers that aren't relatively prime to $n - 1$:

$$ 3 / 81 = 0.037037037037037... = \text{3 steps forward in } [0, 1, 2, 3, 4, 5, 7, 8, 9] $$ $$ 9 / 81 = 0.111111111111111... = \text{9 steps forward in } [1, 2, 3, 4, 5, 6, 7, 8, 9] $$

In base 7:

$$ 2_7 / 51_7 = 0.025025025025025..._7 = \text{2 steps forward in } [0, 1, 2, 3, 5, 6] $$ $$ 3_7 / 51_7 = 0.040404040404040..._7 = \texto{3 pasos hacia adelante en } [0, 1, 2, 4, 5, 6] $$

Keep in mind, though, that as soon as you get through the first set of $n - 1$, you go back to one step but everything in the original number sequence shifts to the right by one:

$$ 9 / 81 = 0.111111111111111... = \text{9 steps forward in } [1, 2, 3, 4, 5, 6, 7, 8, 9] $$ $$ 10 / 81 = 0.123456790123456... = \text{1 step forward in } [1, 2, 3, 4, 5, 6, 7, 9, 0] $$

$$ 18 / 81 = 0.222222222222222... = \text{9 steps forward in } [2, 3, 4, 5, 6, 7, 8, 9, 1] $$ $$ 19 / 81 = 0.234567901234567... = \text{1 step forward in } [2, 3, 4, 5, 6, 7, 9, 0, 1] $$

So the fact that all the digits except for one we removed are represented is simply a consequence of the fact that the order of $k$ in the cyclic group $\mathbb{Z}_{n-1}$ is still $(n-1)$ when $k$ is relatively prime to $(n-1)$.

This doesn't quite constitute a rigorous proof (mostly because I'm too lazy to formalize it and it took quite a while for me to wrap my head around what I was saying myself), but I think you have enough of an idea now that you can figure it out yourself.

---

As an additional note, it is in fact true that the multiples of $123456789$ (note! not $12345679$ which I explained above) that are relatively prime to $9$ also result in a permutation of those digits (including 0 when you reach 10 digits):

$$1 \times 123456789 = 123456789$$

$$2 \times 123456789 = 246913578$$

$$4 \times 123456789 = 493827156$$

$$5 \times 123456789 = 617283945$$

$$7 \times 123456789 = 864197523$$

$$8 \times 123456789 = 987654312$$

$$10 \times 123456789 = 1234567890$$

$$etc.$$

Well, up until 19, anyway:

$$19 \times 123456789 = 2345678991$$

---

You also asked for a proof that if the proposition holds for $k < n$, it also holds for $n \le k \le n^2$. This is actually just a simple induction, if you've already proven the $k < n$ cases.

Suppose that we have a sequence of digits $a b c d \ldots$ that contains all distinct digits except for $n - k$ in the sequence described above (i.e. the digit increases by $k$ each time now, except when it would exceed $n - k$, in which case it increases by $k+1$.).

Then increasing each digit by $1$ (as adding $n$ to the numerator will do) will mean that all the digits are still distinct, except for one that carries over to zero, increasing the previous digit by $1$. But the one immediately before it became $n - k$ upon increasing by 1, so increasing it to $n - k + 1$ means that it's still not the same as any other digits (because the one that was $n - k + 1$ before has since increased to $n - k + 2$). And the resulting sequence also has the property that "the digit increases by $k$ each time now, except when it would exceed $n - k$, in which case it increases by $k+1$", por lo que la inducción puede seguir pasando.

Answer 2

He aquí una prueba a lo largo de las líneas de su agument.

Considere la posibilidad de su número especial (en su notación) $$S = [1, 2, 3, \dots, (n-3), (n-2), n]_{n+1}.$$ Este número ha $n$ en unidades de $(= (n+1)^0)$ lugar $n-2$ en su $n+1$ $(= (n+1)^1)$ lugar, $n-3$ $(n+1)^2$ lugar, y así sucesivamente, hasta que $1$ $(n+1)^{n-2}$ lugar. Por lo que su número es $$S = n + \sum_{i=1}^{n-2} (n-1-i)(n+1)^i = n + \sum_{k=1}^{n-2}k(n+1)^{n-1-k} = \frac{(n+1)^n-1}{n^2} = \frac{R}{n},$$ donde $R$ se define como $nS = \dfrac{(n+1)^n - 1}{n} = [1, 1, 1, \dots, 1, 1]_{n+1}$ con $n$ $1$s. (En otras palabras, $R$ es el repunit $R_n^{(n+1)}$.)

Por ejemplo, para la base de $10$ (n = $9$), tenemos $$S = 12345679 = \dfrac{111111111}{9} = \dfrac{999999999}{9^2} = \dfrac{10^9 - 1}{9^2}.$$

---

Ahora que sabemos cuál es nuestro número especial $S$ es, vamos a probar los hechos acerca de.

Considere la posibilidad de $kS$. Como $S = R/n$, también podemos calcular la $kS = kR/n$ dividiendo $kR$$n$. Para hablar acerca de los dígitos en $kR/n$, vamos a formalizar el procedimiento de división.

El resultado de dividir un número $a = [a_1, a_2, \dots, a_m]_{n+1}$ $b$ es el cociente $[q_1, q_2, \dots, q_m]_{n+1}$ y el resto a $r_m$, dada por:

• $r_0 = 0$, $q_0 = 0$, y
• $q_i = \left\lfloor (r_{i-1} (n + 1) + a_i) / b \right\rfloor$ $r_i = (r_{i-1}(n + 1) + a_i) - q_i b$ $i = 1, 2, \dots, m$.

(Básicamente, $[q_1, q_2, \dots, q_i]_{n+1}$ $r_i$ son el cociente y el resto, respectivamente, en dividir el número formado por la primera $i$ dígitos de $a$,$b$.)

Ahora, para el caso especial donde los $a = kR$$k < n$$b = n$, $m = n$ $a_i = k$ por cada $i$, por lo que

• ($i=1$): $q_1 = \left\lfloor k / n \right\rfloor$ y $r_1 = k - nq_1 \equiv k \mod n$,
• ($i=2$): $q_2 = \left\lfloor (r_1(n+1) + k) / n \right\rfloor = r_1 + \left\lfloor (r_1 + k) / n \right\rfloor$, y $r_2 = r_1(n+1) + k -nq_2 \equiv r_1 + k \equiv 2k \mod n$,
  y, en general, por inducción
• $q_i = \left\lfloor (r_{i-1}(n+1) + k) / n \right\rfloor = r_{i-1} + \left\lfloor (r_{i-1} + k) / n \right\rfloor$, e $r_i = r_{i-1}(n+1) + k - nq_i \equiv ik \mod n$.

Nos gustaría demostrar que todos los $n$ $q_i$'s son distintos (al $0 < k < n$, e $k$ es relativamente primer a $n$), que (como hay $n$ de ellos) será la afirmación de que se componen de todos los dígitos $0$ $n$a excepción de uno.

Tenga en cuenta que el $r_i$s ya se han determinado: $r_i$ es el único número en $[0, n-1)$ que es congruente a $ik$ modulo $n$, es decir, $r_i = ik - c_in$ donde $c_i = \lfloor ik / n \rfloor$. A continuación, $$\begin{align} q_i &= r_{i-1} + \left\lfloor (r_{i-1} + k) / n \right\rfloor \\ &= (i-1)k - c_{i-1}n + \left\lfloor ((i-1)k - c_{i-1}n + k) / n \right\rfloor \\ &= (i-1)k + \lfloor ik / n \rfloor - c_{i-1}(n+1) \end{align}$$ (Alternativamente, se puede calcular el $q_i$ $q_i = (r_{i-1}(n+1) + k - r_i)/n$ y obtiene la misma expresión.)

Como $q_i$ es de un dígito en base $n+1$, sabemos que $0 \le q_i < n+1$, así que echemos un vistazo a $q_i$ modulo $n+1$: a partir de lo anterior, $$q_i \equiv (i-1)k + \lfloor ik / n \rfloor \mod (n+1).$$

La distinción de la $q_i$, con lo que se reduce el siguiente

Lema. $a + \lfloor a/n \rfloor \equiv b + \lfloor b/n \rfloor \mod (n+1) \iff a \equiv b \mod n$

Prueba: Supongamos $a$ tiene más de un dígito en base $(n+1)$, decir $a = \alpha(n+1) + \beta$. Entonces, modulo $n+1$,$a + \lfloor a/n \rfloor \equiv \beta + \lfloor (\alpha(n+1) + \beta)/n \rfloor = (\alpha + \beta) + \lfloor (\alpha + \beta) / n \rfloor = a' + \lfloor a'/n \rfloor$$a' = \alpha + \beta$. Ahora si $a'$ tiene más de un dígito en base $n+1$, es decir, si $a' \ge n + 1$, podemos repetir el proceso. Por inducción, $a + \lfloor a/n\rfloor$ es la misma que la de la (repite) la suma de sus dígitos (también conocido como raíz digital), que es precisamente lo $a \bmod n$ (excepto, posiblemente, en el caso de $a \bmod n = 0$, pero tenga en cuenta que $n + \lfloor n/n \rfloor = n + 1 \equiv 0 \mod (n+1)$, por lo que está cubierto). $\Box$

Por lo tanto, si algunos de los dos $q_i$ $q_j$ son iguales, debemos tener $(i-1)k + \lfloor ik/n \rfloor \equiv (j-1)k + \lfloor jk/n \rfloor \mod (n+1)$, por lo que (añadiendo $k$ a ambos lados) $ik + \lfloor ik/n \rfloor \equiv jk + \lfloor jk/n \rfloor \mod (n+1)$, que por nuestro lema significa que $ik \equiv jk \mod n$, que a su vez (al $k$ es relativamente primer a $n$) significa que $i \equiv j \mod n$.

Esto demuestra que el $n$ dígitos de $kS = kR/n$, es decir,$q_1$$q_n$, son todas diferentes.

(Por cierto, de la $n+1$ posible dígitos, los dígitos que no se alcanza entre los $n$ $q_i$s es el que no puede aparecer como $(i-1)k + \lfloor ik/n \rfloor = ik + \lfloor ik/n \rfloor - k$. Esto es $n - k$ $n$ es el que no puede ser alcanzado como $ik + \lfloor ik /n \rfloor$: por nuestro lema, si $ik \equiv c \mod n$$0 \le c < n$,$ik + \lfloor ik/n \rfloor \equiv c + \lfloor c/n \rfloor \equiv c \mod (n+1)$.)

---

Que lo hace por $k < n$, y para $n < k < n^2$, acaba de darse cuenta de que si $k = an + b$,$kS = kR/n = aR + bR/n$. Como $aR$ tiene todos sus dígitos igual a $a$, tenemos que el $i$th dígitos de $kS$ es congruente, modulo $n+1$, $a$ $i$th dígitos de $bS$. Esto simplemente corresponde al desplazamiento de todos los dígitos por $a$, y por lo tanto no afecta a la distinción.