Representación buena de n

Primero veamos cuantas formas buenas tienen las potencias exactas

2^0 = 1 = 1 forma

2^1 = {1+1, 2} = 2 formas

2^2 = {1+1+2, 2+2, 4} = 3 formas

2^3 = {1+1+2+4, 2+2+4, 4+4, 8} = 4 formas

Las representaciones buenas de 2^i son i+1 y se forman con las sumas buenas de 2^(i-1) sumándoles 2^(i-1) a cada una y añadiendo la representación buena 2^i

Ahora tomemos un número n cualquiera. Dicho número se puede descomponer de forma única como sumas de potencias de 2 con cada una una sola vez. No es otra cosa que el típico algoritmo de cambio a base 2

n = a0·2^0 + a1·2^1 + a2·2^2 + ...+ ak·2^k

con ai € {0, 1}

Cada ai se podría poner como suma con potencias repetidas, siempre que esas potencias repetidas no se repitan en la descomposición que hagamos de los otros ai

Por ejemplo:

15 = 1+2+4+8

No admite otra representación buena. Para cualquiera de los sumandos que descompongamos habría que descomponer el anterior hasta llegar al primero que no puede descomponerse.

14 = 2+4+8

admite otras representaciones buenas

1+1+4+8

1+1+2+2+8

1+1+2+2+4+4

Voy a decir una representación buena es de tipo 1 cuando aparece la potencia de mayor grado que admite el número. Es decir, si 2^i <= n < 2^(i-1) entonces 2^i aparece en la representación

En el ejemplo anterior son de tipo 1 todas las que tienen el sumando 8. A las que no son de tipo 1 las llamaré de tipo 2.

Las representación de la suma de varias potencias se pueden poner como combinación de las representaciones posibles de los sumandos individuales siempre que no se repitan potencias.

Algunas normas sencillas de demostrar que se cumplen para un elemento 2^i son estas:

1) 2^I tiene una única representación de tipo 1 e i representaciones de tipo 2

2) Toda representación de tipo 2 de 2^i tiene el sumando 2^(i-1). Puede aparecer una o dos veces, pero una al menos.

3) Toda representación de tipo 2 de 2^i tiene repetida la potencia menor que aparece y las otras aparecen una vez.

Vamos a ver ya cuantas representaciones buenas tiene

n = a0·2^0 + a1·2^1 + a2·2^2 + ...+ ak·2^k con ai€{0, 1}

Los términos ai = 0 los quitaríamos y quedaría algo así

n = 2^(i1) + 2^(i2) + ... + 2^(ij) con i1<i2< ...< ij

Tomamos el primer sumando 2^(i1). Tendrá una representación de tipo 1 e i1 - 1 representaciones de tipo 2

Ahora tomamos 2^(i2)

Sea d = i2 - i1

Podemos representar 2^(i2) de d formas que tengan todas sus potencias mayores que i1

Y de (d+1) formas de modo que la potencia mínima sea i1

Entonces las representaciones de 2^(i1)+2(i2) son

d·[representaciones buenas de 2^(i1)] + (d+1)[representaciones buenas tipo 2 de 2^(i1)

NADA, NO ES NADA SENCILLO y lo que he escrito no es del todo correcto.

He hecho el camino inverso. Tomar todas las representaciones que puede haber, las cuales se pueden considerar como números con cifras 0, 1 y 2, o sea, números en base 3. Para cada uno de esos números he hallado su valor decimal y he llevado la cuenta de cuántas veces salía cada número decimal.

Si por ejemplo hacemos todo este recuento para 9 cifras en base 3 recontaremos 3^9-1 = 19682 representaciones y tendremos aseguradas al menos todas las representaciones de números binarios de 9 cifras 2^9-1 = 511

Todo esto se ha hecho con un programa de ordenador por supuesto, aunque a la vista del resultado quizá a mano se podría haber intuido la respuesta.

Y el resultado obtenido es este, solo aparecen los números con un número par de representaciones, luego te pongo la completa para que la veas y compruebas los números que quieras

 2 2; 5 2; 8 4; 11 2; 14 4; 17 4; 20 8; 23 2;
26 8; 29 4; 32 6; 35 4; 38 10; 41 8; 44 12; 47 2;
50 12; 53 8; 56 10; 59 4; 62 6; 65 6; 68 14; 71 4;
 74 18; 77 10; 80 14; 83 8; 86 18; 89 12; 92 16; 95 2;
 98 16; 101 12; 104 18; 107 8; 110 14; 113 10; 116 18; 119 4;
 122 14; 125 6; 128 8; 131 6; 134 16; 137 14; 140 22; 143 4;
 146 26; 149 18; 152 24; 155 10; 158 16; 161 14; 164 30; 167 8;
 170 34; 173 18; 176 22; 179 12; 182 26; 185 16; 188 20; 191 2;
 194 20; 197 16; 200 26; 203 12; 206 22; 209 18; 212 34; 215 8;
 218 30; 221 14; 224 16; 227 10; 230 24; 233 18; 236 26; 239 4;
 242 22; 245 14; 248 16; 251 6; 254 8; 257 8; 260 20; 263 6;
 266 28; 269 16; 272 24; 275 14; 278 32; 281 22; 284 30; 287 4;
 290 34; 293 26; 296 40; 299 18; 302 32; 305 24; 308 44; 311 10;
 314 36; 317 16; 320 20; 323 14; 326 36; 329 30; 332 46; 335 8;
 338 50; 341 34; 344 44; 347 18; 350 28; 353 22; 356 46; 359 12;
 362 50; 365 26; 368 30; 371 16; 374 34; 377 20; 380 24; 383 2;
 386 24; 389 20; 392 34; 395 16; 398 30; 401 26; 404 50; 407 12;
 410 46; 413 22; 416 28; 419 18; 422 44; 425 34; 428 50; 431 8;
 434 46; 437 30; 440 36; 443 14; 446 20; 449 16; 452 36; 455 10;
 458 44; 461 24; 464 32; 467 18; 470 40; 473 26; 476 34; 479 4;
 482 30; 485 22; 488 32; 491 14; 494 24; 497 16; 500 28; 503 6;
506 20; 509 8;

Ya me he cansado de decirles a los de la página que no deben suprimir los espacios en blanco sobrantes porque se desajustan las columnas, pero ellos no lo entienden y así nos va.

Aparte de eso lo que se ve más claro que el agua es que los números que tienen un número par de representaciones buenas son los de la forma 3m-1 para m€N

 0 1; 1 1; 2 2; 3 1; 4 3; 5 2; 6 3; 7 1;
 8 4; 9 3; 10 5; 11 2; 12 5; 13 3; 14 4; 15 1;
 16 5; 17 4; 18 7; 19 3; 20 8; 21 5; 22 7; 23 2;
 24 7; 25 5; 26 8; 27 3; 28 7; 29 4; 30 5; 31 1;
 32 6; 33 5; 34 9; 35 4; 36 11; 37 7; 38 10; 39 3;
 40 11; 41 8; 42 13; 43 5; 44 12; 45 7; 46 9; 47 2;
 48 9; 49 7; 50 12; 51 5; 52 13; 53 8; 54 11; 55 3;
 56 10; 57 7; 58 11; 59 4; 60 9; 61 5; 62 6; 63 1;
 64 7; 65 6; 66 11; 67 5; 68 14; 69 9; 70 13; 71 4;
 72 15; 73 11; 74 18; 75 7; 76 17; 77 10; 78 13; 79 3;
 80 14; 81 11; 82 19; 83 8; 84 21; 85 13; 86 18; 87 5;
 88 17; 89 12; 90 19; 91 7; 92 16; 93 9; 94 11; 95 2;
 96 11; 97 9; 98 16; 99 7; 100 19; 101 12; 102 17; 103 5;
 104 18; 105 13; 106 21; 107 8; 108 19; 109 11; 110 14; 111 3;
 112 13; 113 10; 114 17; 115 7; 116 18; 117 11; 118 15; 119 4;
 120 13; 121 9; 122 14; 123 5; 124 11; 125 6; 126 7; 127 1;
 128 8; 129 7; 130 13; 131 6; 132 17; 133 11; 134 16; 135 5;
 136 19; 137 14; 138 23; 139 9; 140 22; 141 13; 142 17; 143 4;
 144 19; 145 15; 146 26; 147 11; 148 29; 149 18; 150 25; 151 7;
 152 24; 153 17; 154 27; 155 10; 156 23; 157 13; 158 16; 159 3;
 160 17; 161 14; 162 25; 163 11; 164 30; 165 19; 166 27; 167 8;
 168 29; 169 21; 170 34; 171 13; 172 31; 173 18; 174 23; 175 5;
 176 22; 177 17; 178 29; 179 12; 180 31; 181 19; 182 26; 183 7;
 184 23; 185 16; 186 25; 187 9; 188 20; 189 11; 190 13; 191 2;
 192 13; 193 11; 194 20; 195 9; 196 25; 197 16; 198 23; 199 7;

Es difícil saber el porqué, pero es así. Los números de la forma 3m-1 son los que tienen un número para de representaciones buenas.

Y eso es todo.