Interi con $0$ e $1$

[axpgn]

Sia dato un intero $n$.
Mostrare che è sempre possibile trovare un intero contenente solo le cifre $0$ e $1$ e che sia divisibile per $n$.
Esiste un algoritmo per trovare il più piccolo di tali numeri?


Cordialmente, Alex

[hydro1]

"axpgn":Sia dato un intero $n$.
Mostrare che è sempre possibile trovare un intero contenente solo le cifre $0$ e $1$ e che sia divisibile per $n$.

Considera la successione $\{10^k\}_{k\ge 0}$. Per pigeonhole, ci sono infiniti elementi della successione congrui ad uno stesso $y\mod n$. Ne prendo $n$, li sommo e trovo un numero come vuoi tu.

"axpgn":
Esiste un algoritmo per trovare il più piccolo di tali numeri?
Cordialmente, Alex

Certo, provarli tutti. Una domanda più interessante è qual è l'ordine di grandezza del più piccolo di tali numeri.

[otta96]

Uso la base 2

[axpgn]

Ovviamente la base è dieci
Mentre penso che l'ordine di grandezza sia meno di $10^n$

[Zero87]

Ciao Alex (e ciao a voi), mi hai ricordato questa mia discussione qui di "qualche" annetto fa
https://www.matematicamente.it/forum/vi ... 7&t=146480
A naso ho idea che problemi di questo tipo siano simili.

[axpgn]

@Zero87
Il tuo era più difficile

Consideriamo i resti (modulo $n$) degli $n$ interi $(10^k-1)/9, k=1,2,...,n$.
O uno di questi è zero e quindi uno di quegli interi è divisibile per $n$ oppure ce ne sono due uguali (per pigeonhole) ed allora basta prendere la differenza fra i due.
In entrambi i casi abbiamo un numero con tanti $1$ seguiti da (eventualmente) tanti zeri.

Cordialmente, Alex

[Quinzio]

Per chi vuole divertirsi qui c'e' un algoritmo in C che cerca di trovare il numero piu' piccolo.
A titolo di esempio sotto ci sono i numeri trovati per tutti i divisori fino a 200 circa.
Nella riga c'e': il divisore, la quantita' di cifre dl numero, il numero in forma abbreviata e poi estesa.
La forma abbreviata scrive la cifre, 0 o 1 e poi quante volte e' ripetuta.
Ad es: 100110 diventa 1(1)0(2)1(2)1(1).

In breve ll'algoritmo funziona cosi':
si cerca di fare la divisione lunga $(1.0000...)/n$, poi quando i resti iniziano a diventare periodici, si introduce un 1 in un punto del periodo.
La divisione termina quando il resto e' $n-1$. Si cambia lo 0 in 1 e la divisione termina.

#include <stdio.h>
#include <stdlib.h>

#define LEN 11000

void clear(int cnt, int *ans, int *remStep) {
	int ix;
	for (ix = cnt + 1; ix < LEN; ++ix) {
		ans[ix] = 0;
		remStep[ix] = 0;
	}
}

int main(void) {
	int ans[LEN];
	int remStep[LEN];
	int remUsed[LEN];
	int cnt = 0;
	int divd = 59;
	int ix = 0;
	for (int alln = 3; alln < LEN-1; alln++) {
		if (((alln % 5) == 0) || ((alln % 5) == 0))
			continue;
		divd = alln;
		for (ix = 0; ix < LEN; ix++) {
			ans[ix] = 0;
			remStep[ix] = 0;
			remUsed[ix] = 0;
		}
		ans[0] = 0;
		remStep[0] = 0;
		remUsed[ans[0]] = 1;
		cnt = 1;
		while (1) {
			remStep[cnt] = (10 * remStep[cnt - 1]) % divd;
			if ((cnt > 1) && (remStep[cnt] == 0)) {
				break;
			}
			if (remStep[cnt] == (divd - 1)) {
				ans[cnt] = 1;
				break;
			}
			if (remUsed[remStep[cnt]] > 0) {
				// reminder already found, let's go back and fix
				for (ix = divd - 1; ix > 0; --ix) {
					if ((remUsed[ix] == 0) && (remUsed[ix - 1] > 0)) {
						break;
					}
				}
				while (!(remStep[cnt] == (ix - 1)) && (ans[cnt] == 0)) {
					cnt--;
				}
				clear(cnt, ans, remStep);
				ans[cnt] = 1;
				remStep[cnt]++;

			} else {
				ans[cnt] = 0;
			}
			remUsed[remStep[cnt]]++;
			cnt++;
		}
		printf("%d %d\t", alln, cnt);
		for (ix = 1; ix < (cnt + 1);) {
			int iy;
			for (iy = ix; iy < (cnt + 1); ++iy) {
				if (ans[ix] != ans[iy])
					break;
			}
			printf("%d(%d)", ans[ix], iy - ix);
			ix = iy;
		}
		printf("\t");
		for (ix = 1; ix < (cnt + 1); ++ix) {
			printf("%d", ans[ix]);
		}
		printf("\n");
	}
}

/*
3 3	1(3)	111
4 3	1(1)0(2)	100
6 6	1(1)0(1)1(1)0(1)1(1)0(1)	101010
7 4	1(1)0(2)1(1)	1001
8 4	1(1)0(3)	1000
9 9	1(9)	111111111
11 2	1(2)	11
12 7	1(2)0(2)1(1)0(2)	1100100
13 4	1(1)0(2)1(1)	1001
14 7	1(1)0(4)1(1)0(1)	1000010
16 5	1(1)0(4)	10000
17 9	1(1)0(7)1(1)	100000001
18 9	1(1)0(1)1(4)0(1)1(1)0(1)	101111010
19 10	1(1)0(8)1(1)	1000000001
21 12	1(1)0(4)1(1)0(5)1(1)	100001000001
22 7	1(1)0(1)1(1)0(2)1(1)0(1)	1010010
23 12	1(1)0(10)1(1)	100000000001
24 10	1(1)0(3)1(1)0(1)1(1)0(3)	1000101000
26 10	1(1)0(1)1(1)0(5)1(1)0(1)	1010000010
27 20	1(1)0(1)1(1)0(2)1(2)0(2)1(1)0(2)1(2)0(2)1(1)0(2)1(1)	10100110010011001001
28 10	1(1)0(6)1(2)0(1)	1000000110
29 15	1(1)0(13)1(1)	100000000000001
31 24	1(1)0(13)1(1)0(8)1(1)	100000000000001000000001
32 6	1(1)0(5)	100000
33 6	1(6)	111111
34 4	1(1)0(1)1(1)0(1)	1010
36 8	1(1)0(2)1(3)0(2)	10011100
37 5	1(1)0(1)1(1)0(1)1(1)	10101
38 10	1(1)0(7)1(1)0(1)	1000000010
39 18	1(1)0(2)1(3)0(5)1(1)0(5)1(1)	100111000001000001
41 20	1(1)0(3)1(1)0(4)1(1)0(4)1(1)0(4)1(1)	10001000010000100001
42 15	1(1)0(4)1(1)0(3)1(1)0(1)1(3)0(1)	100001000101110
43 31	1(1)0(8)1(1)0(20)1(1)	1000000001000000000000000000001
44 6	1(1)0(2)1(1)0(2)	100100
46 21	1(1)0(18)1(1)0(1)	100000000000000000010
47 24	1(1)0(22)1(1)	100000000000000000000001
48 7	1(1)0(2)1(1)0(3)	1001000
49 22	1(1)0(20)1(1)	1000000000000000000001
51 19	1(1)0(1)1(1)0(15)1(1)	1010000000000000001
52 10	1(1)0(7)1(1)0(1)	1000000010
53 24	1(1)0(5)1(1)0(3)1(1)0(12)1(1)	100000100010000000000001
54 15	1(1)0(1)1(2)0(2)1(1)0(2)1(1)0(3)1(1)0(1)	101100100100010
56 13	1(1)0(8)1(1)0(3)	1000000001000
57 27	1(1)0(7)1(1)0(17)1(1)	100000001000000000000000001
58 27	1(1)0(24)1(1)0(1)	100000000000000000000000010
59 30	1(1)0(28)1(1)	100000000000000000000000000001
61 31	1(1)0(29)1(1)	1000000000000000000000000000001
62 18	1(1)0(4)1(1)0(10)1(1)0(1)	100001000000000010
63 41	1(1)0(2)1(2)0(5)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(5)1(1)	10011000001000001000001000001000001000001
64 7	1(1)0(6)	1000000
66 24	1(1)0(1)1(1)0(1)1(1)0(2)1(1)0(1)1(2)0(2)1(1)0(1)1(1)0(1)1(1)0(2)1(1)0(1)1(1)0(1)	101010010110010101001010
67 65	1(1)0(30)1(1)0(32)1(1)	10000000000000000000000000000001000000000000000000000000000000001
68 14	1(1)0(11)1(1)0(1)	10000000000010
69 42	1(1)0(18)1(1)0(21)1(1)	100000000000000000010000000000000000000001
71 67	1(1)0(33)1(1)0(31)1(1)	1000000000000000000000000000000000100000000000000000000000000000001
72 9	1(1)0(3)1(2)0(3)	100011000
73 5	1(1)0(3)1(1)	10001
74 17	1(1)0(2)1(1)0(1)1(1)0(1)1(1)0(3)1(2)0(2)1(1)0(1)	10010101000110010
76 9	1(1)0(6)1(1)0(1)	100000010
77 4	1(1)0(2)1(1)	1001
78 19	1(1)0(2)1(1)0(5)1(1)0(2)1(1)0(4)1(1)0(1)	1001000001001000010
79 54	1(1)0(8)1(1)0(4)1(1)0(12)1(1)0(12)1(1)0(12)1(1)	100000000100001000000000000100000000000010000000000001
81 60	1(1)0(7)1(1)0(8)1(1)0(2)1(1)0(8)1(1)0(8)1(1)0(2)1(1)0(8)1(1)0(8)1(1)	100000001000000001001000000001000000001001000000001000000001
82 28	1(1)0(3)1(1)0(4)1(1)0(5)1(1)0(5)1(1)0(4)1(1)0(1)	1000100001000001000001000010
83 64	1(1)0(21)1(1)0(40)1(1)	1000000000000000000000100000000000000000000000000000000000000001
84 12	1(1)0(2)1(1)0(5)1(2)0(1)	100100000110
86 29	1(1)0(8)1(1)0(17)1(1)0(1)	10000000010000000000000000010
87 54	1(1)0(24)1(1)0(27)1(1)	100000000000000000000000010000000000000000000000000001
88 13	1(1)0(3)1(1)0(1)1(1)0(3)1(2)0(1)	1000101000110
89 23	1(1)0(21)1(1)	10000000000000000000001
91 4	1(1)0(2)1(1)	1001
92 10	1(1)0(4)1(1)0(1)1(2)0(1)	1000010110
93 22	1(1)0(6)1(1)0(13)1(1)	1000000100000000000001
94 9	1(1)0(6)1(1)0(1)	100000010
96 16	1(1)0(5)1(1)0(3)1(1)0(5)	1000001000100000
97 49	1(1)0(47)1(1)	1000000000000000000000000000000000000000000000001
98 25	1(1)0(22)1(1)0(1)	1000000000000000000000010
99 18	1(18)	111111111111111111
101 3	1(1)0(1)1(1)	101
102 18	1(1)0(1)1(1)0(3)1(1)0(9)1(1)0(1)	101000100000000010
103 18	1(1)0(16)1(1)	100000000000000001
104 4	1(1)0(1)1(1)0(1)	1010
106 12	1(1)0(5)1(1)0(3)1(1)0(1)	100000100010
107 75	1(1)0(20)1(1)0(52)1(1)	100000000000000000000100000000000000000000000000000000000000000000000000001
108 11	1(1)0(4)1(1)0(2)1(2)0(1)	10000100110
109 55	1(1)0(53)1(1)	1000000000000000000000000000000000000000000000000000001
111 5	1(1)0(1)1(1)0(1)1(1)	10101
112 8	1(1)0(2)1(1)0(4)	10010000
113 57	1(1)0(55)1(1)	100000000000000000000000000000000000000000000000000000001
114 43	1(1)0(7)1(1)0(15)1(1)0(16)1(1)0(1)	1000000010000000000000001000000000000000010
116 10	1(1)0(7)1(1)0(1)	1000000010
117 43	1(1)0(1)1(1)0(5)1(1)0(3)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(5)1(1)	1010000010001000001000001000001000001000001
118 56	1(1)0(53)1(1)0(1)	10000000000000000000000000000000000000000000000000000010
119 85	1(1)0(36)1(1)0(46)1(1)	1000000000000000000000000000000000000100000000000000000000000000000000000000000000001
121 12	1(1)0(10)1(1)	100000000001
122 19	1(1)0(16)1(1)0(1)	1000000000000000010
123 33	1(1)0(1)1(1)0(4)1(1)0(1)1(1)0(2)1(1)0(4)1(1)0(4)1(1)0(4)1(1)0(4)1(1)	101000010100100001000010000100001
124 24	1(1)0(10)1(1)0(10)1(1)0(1)	100000000001000000000010
126 30	1(1)0(2)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(6)1(1)0(1)	100100000100000100000100000010
127 22	1(1)0(20)1(1)	1000000000000000000001
128 8	1(1)0(7)	10000000
129 31	1(1)0(8)1(1)0(20)1(1)	1000000001000000000000000000001
131 66	1(1)0(64)1(1)	100000000000000000000000000000000000000000000000000000000000000001
132 17	1(1)0(3)1(2)0(1)1(1)0(2)1(1)0(1)1(1)0(2)1(1)0(1)	10001101001010010
133 10	1(1)0(8)1(1)	1000000001
134 62	1(1)0(30)1(1)0(28)1(1)0(1)	10000000000000000000000000000001000000000000000000000000000010
136 9	1(1)0(5)1(2)0(1)	100000110
137 5	1(1)0(3)1(1)	10001
138 45	1(1)0(18)1(1)0(15)1(1)0(7)1(1)0(1)	100000000000000000010000000000000001000000010
139 24	1(1)0(22)1(1)	100000000000000000000001
141 54	1(1)0(6)1(1)0(45)1(1)	100000010000000000000000000000000000000000000000000001
142 62	1(1)0(27)1(1)0(31)1(1)0(1)	10000000000000000000000000001000000000000000000000000000000010
143 4	1(1)0(2)1(1)	1001
144 9	1(1)0(2)1(2)0(4)	100110000
146 39	1(1)0(4)1(1)0(7)1(1)0(7)1(1)0(7)1(1)0(7)1(1)0(1)	100001000000010000000100000001000000010
147 66	1(1)0(22)1(1)0(41)1(1)	100000000000000000000001000000000000000000000000000000000000000001
148 19	1(1)0(2)1(2)0(3)1(1)0(2)1(2)0(4)1(1)0(1)	1001100010011000010
149 75	1(1)0(73)1(1)	100000000000000000000000000000000000000000000000000000000000000000000000001
151 74	1(1)0(32)1(1)0(39)1(1)	10000000000000000000000000000000010000000000000000000000000000000000000001
152 9	1(1)0(5)1(2)0(1)	100000110
153 119	1(1)0(5)1(1)0(15)1(1)0(15)1(1)0(15)1(1)0(15)1(1)0(15)1(1)0(15)1(1)0(15)1(1)	10000010000000000000001000000000000000100000000000000010000000000000001000000000000000100000000000000010000000000000001
154 30	1(1)0(3)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(1)	100010000010000010000010000010
156 17	1(1)0(7)1(1)0(6)1(1)0(1)	10000000100000010
157 40	1(1)0(38)1(1)	1000000000000000000000000000000000000001
158 46	1(1)0(8)1(1)0(4)1(1)0(12)1(1)0(11)1(1)0(3)1(2)0(1)	1000000001000010000000000001000000000001000110
159 18	1(1)0(4)1(1)0(11)1(1)	100001000000000001
161 34	1(1)0(32)1(1)	1000000000000000000000000000000001
162 41	1(1)0(7)1(1)0(2)1(1)0(8)1(1)0(8)1(1)0(9)1(1)0(1)	10000000100100000000100000000100000000010
163 158	1(1)0(75)1(1)0(80)1(1)	10000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000001
164 13	1(1)0(3)1(2)0(5)1(1)0(1)	1000110000010
166 27	1(1)0(21)1(1)0(2)1(1)0(1)	100000000000000000000010010
167 84	1(1)0(82)1(1)	100000000000000000000000000000000000000000000000000000000000000000000000000000000001
168 12	1(1)0(8)1(2)0(1)	100000000110
169 40	1(1)0(38)1(1)	1000000000000000000000000000000000000001
171 133	1(1)0(5)1(1)0(17)1(1)0(17)1(1)0(17)1(1)0(17)1(1)0(17)1(1)0(17)1(1)0(17)1(1)	1000001000000000000000001000000000000000001000000000000000001000000000000000001000000000000000001000000000000000001000000000000000001
172 19	1(1)0(5)1(1)0(10)1(1)0(1)	1000001000000000010
173 158	1(1)0(27)1(1)0(42)1(1)0(42)1(1)0(42)1(1)	10000000000000000000000000001000000000000000000000000000000000000000000100000000000000000000000000000000000000000010000000000000000000000000000000000000000001
174 60	1(1)0(24)1(1)0(21)1(1)0(10)1(1)0(1)	100000000000000000000000010000000000000000000001000000000010
176 16	1(1)0(5)1(1)0(2)1(1)0(1)1(1)0(4)	1000001001010000
177 113	1(1)0(53)1(1)0(57)1(1)	10000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000001
178 16	1(1)0(13)1(1)0(1)	1000000000000010
179 90	1(1)0(88)1(1)	100000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
181 91	1(1)0(89)1(1)	1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
182 30	1(1)0(3)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(5)1(1)0(1)	100010000010000010000010000010
183 78	1(1)0(16)1(1)0(59)1(1)	100000000000000001000000000000000000000000000000000000000000000000000000000001
184 16	1(1)0(12)1(2)0(1)	1000000000000110
186 34	1(1)0(9)1(1)0(6)1(1)0(14)1(1)0(1)	1000000000100000010000000000000010
187 39	1(1)0(6)1(1)0(15)1(1)0(14)1(1)	100000010000000000000001000000000000001
188 39	1(1)0(36)1(1)0(1)	100000000000000000000000000000000000010
189 42	1(1)0(3)1(1)0(5)1(1)0(5)1(1)0(2)1(1)0(5)1(1)0(5)1(1)0(3)1(1)0(5)1(1)	100010000010000010010000010000010001000001
191 85	1(1)0(18)1(1)0(64)1(1)	1000000000000000000100000000000000000000000000000000000000000000000000000000000000001
192 14	1(1)0(4)1(1)0(1)1(1)0(6)	10000101000000
193 97	1(1)0(95)1(1)	1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
194 40	1(1)0(37)1(1)0(1)	1000000000000000000000000000000000000010
196 27	1(1)0(24)1(1)0(1)	100000000000000000000000010
197 50	1(1)0(48)1(1)	10000000000000000000000000000000000000000000000001
198 68	1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(2)0(2)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(2)0(2)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(2)0(2)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(2)0(2)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)1(1)0(1)	10101010101100101010101011001010101010110010101010101100101010101010
199 31	1(1)0(27)1(1)0(1)1(1)	1000000000000000000000000000101