[Phicar]

Buenas, la vaina es que necesito saber cuantos numeros octales entre 1 y 7346545000 son palindromos..obviamente por fuerza bruta demora mucho y pos lo iba a hacer por conteo cogiendo las mitades y pos viendo que son un espejo...Pero la verdad me lie totalmente....

la logica es sencilla, viendo que los palindromos primeros son

1,2,3,4,5,6,7,/11,22,33,44,55,66,77,/101,111,121,131,141,151,161,171,/202

se ve claramente que digamos el # de palindromos entre numeros de 1 y dos cifras es la misma..de tres y cuatro cifras es el mismo y asi....
 1-2  3-4   5-6    7-8         9-10
14(1+(8)+(8*8)+(8*8*8)+(8*8*8*8))

donde el 14 que se saca es el (2*7)...7 porque no se puede pedir un 8 ya que no puede haber 0 a la izquierda...y el 2 por el analisis pasado...

ese es como el maximo hacia arriba...ya que son todos los que se pueden hacer con 10 digitos
pero el sobrante no se como restarselo ...

cualquier ayuda seria Super

[cheroky]

_Un palindromo no es un objeto matemático, es una sucesión de caracteres y es trivial el tipo de la base de la representación numérica.

_Lo más sencillo y eficiente es tener este numero como secuencia de caracteres y mediante sendos punteros al inicio y al final se iteran, el primero en incremento y el segundo como decremento, se evaluan su desreferencia, si son iguales se continua con la iteración, caso contrario se sale del bucle, cuando ambos punteros coincidan en dirección el numero en cuestión es palindromo.


Un saludo.

[Phicar]

Hola, lo mas sencillo no siempre es lo mas optimo para resolver un problema ...las bases no importan para hacer un bruter....pero bruter demora mucho ...pero por conteo se puede llevar a cabo es logico, hasta donde se...Mi problema radica en que no es un numero cerrado

mira que mi post tiene alguna logica

[cheroky]

_Honestamente pensaba que necesitabas comprobar si un número N es palíndromo,. Por lo que veo necesitas comprobar una lista bastante grande, son dos problemas distintos.

_Yo en estos casos prefiero previamente utilizar un algoritmo de fuerza bruta y analizar las propiedades lineales del los elementos generados, además  siempre viene bien para cotejar posibles incongruencias.

_He podido observar que todos numero octal palíndromo tiene una suma (o diferencia) particular con su antecesor y este es un numero (en base 8) potencias de 10 y potencias de 10 con el producto de 11 e incluido el 1 y el 2. Con esto se puede generar un array de tamaño reducido de forma automática o mediante un bucle y comprobar si los incrementos forman la ocurrencia palíndromica.

_Implementación en C estandar.

Código: [Seleccionar]

#include <stdio.h>
#include <math.h>

#define LOG8(a) (log(a) / log(8.))

int is_vpal(int v)
{
int a =  pow(010, (unsigned) LOG8(v));
int b = 1;

while(a && v / a % 010 == v / b % 010)
{
a /= 010;
b *= 010;
}

return a;
}

#define MAX 12

static void proc()
{
int vec[MAX] = {
01, 02,
010, 011,
0100, 0110,
01000, 01100,
010000, 011000,
0100000, 0110000
};

int r = 0;

for(int i = 0; i < MAX && r < 07346545000L; i++)
{
if ( ! is_vpal(r + vec[i]) )
{
r += vec[i];

while( !is_vpal(r) )
{
printf("%o\n", r);
r += vec[i];    
}

r -= vec[i];
i = 0;
}
}
}

int main(void)
{
proc();

return 0;
}
_Esto genera una lista de ocurrencias (63286) palíndromicas desde 1 hasta 7346545000 (base octal) en un tiempo bastante breve. Complejidad O(n).

Un saludo.

[Phicar]

Tiene buena logica lo que haces..Muchas gracias

yo hago lo mismo que tu hago el brute...pa ver si cumplen ciertas caracteristicas..no lo vi como tu, lo vi por la parte de conteo ..

[Richard R Richard]

Mentalmente sin fuerza bruta

$$7$$ de 1 cifra
$$7$$ de 2 cifra
$$7\cdot8$$ de 3 cifras
$$7\cdot8$$ de 4 cifras
$$7\cdot8^2$$ de 5 cifras
$$7\cdot8^2$$ de 6 cifras
$$7\cdot8^3 $$de 7 cifras
$$7\cdot8^3$$ de 8 cifras
$$7\cdot8^4 $$ de 9 cifras
con 10 cifras

$$6\cdot8^4+3\cdot8^3+4\cdot8^2+6\cdot8+5$$


63283 si no sume mal

[ani_pascual]

Hola:

Mentalmente sin fuerza bruta
...
63283 si no sume mal

Sumaste bien ...😉
Si \( n  \) es impar, es decir, \( n=2k+1 \) con \( k=0,1,2,\ldots \), entonces el número de palíndromos de \( n  \) cifras es \( V_{7,1}\cdot 8^k=7\cdot 8^k \), que coincide con el número de palíndromos si el número de cifras es \( n=2(k+1) \).
Así, el número pedido es
\( 2\cdot 7\cdot (8^0+\cdots +8^3)+7\cdot 8^4+
(5\cdot 8^0+6\cdot 8^1+4\cdot 8^2+3\cdot 8^3+6\cdot 8^4)=\\8190+28672+26421=63283 \)
Saludos

[Tachikomaia]

¿Olvidaron el 0?

[Richard R Richard]

¿Olvidaron el 0?

No, del 0 al 7 hay 8 números $$0,1,2,3,4,5,6,7$$

[Tachikomaia]

Phicar dijo
"viendo que los palindromos primeros son

1,2,3,4,5,6,7"

Y dices:
"7 de 1 cifra"